GCJ 2015 – Qualification Problem C – Dijkstra (迪科斯彻) – 解题报告

第三题:迪科斯彻 / Dijkstra

Google Code Jam 2015 比赛记录:http://www.huangwenchao.com.cn/2015/04/gcj-2015-qual.html

顶礼膜拜 Dijkstra 祖师 Orz.. Orz.. Orz..

题意如下,介绍一种数,叫“四元数”(属于超复数的一种)

参见 Wiki: http://zh.wikipedia.org/wiki/%E5%9B%9B%E5%85%83%E6%95%B8

于是,其基本单位有 1, i, j, k 这几种。

在这里我们仅考虑其乘法运算。

其乘法满足结合律,但不满足交换律,正负号跟普通数学一样。

乘法的运算表如下图 (wikipedia 里面也有):

dijkstra

现在给出一个基本串,长度为 L,然后重复 K 次,注意 K 变态的大。

基本串仅包含字母 i, j 和 k,将 K 个基本串拼接之后连乘。

请问,通过结合律将这个连乘式拆成三段,能否将这个超级串化简为 ijk?输出是否。


解题报告:

首先大数据的数字很吓人,所以先要想想归约的办法。

定理一:整个字符串求值必须等于 -1 才可以化简为 ijk

很明显可以观察到,ijk = -1,所以如果要结果相等,整个合成字符串(后称合成串,合成之前的称为子串)运算结果必须等于 -1

定理二:任意子串的四次方必然等于 1,因而可以省略任意4的倍数的子串

这很显然,任意子串求值必然是正负 1, i, j, k,平方肯定为正负一,四次方肯定为一。

定理三:最终结果要能化简成 ijk 的充要条件是,满足定理一,而且,从前面遍历累积,找到第一个乘积为 i 的位置,比从后面遍历累积,找到第一个乘积为 j 的位置靠前

明显,按照这样遍历得到 ik 的位置是最省的,而且因为满足定理一,中间留下的当然是 j

定理四:如果能够遍历找到 i 和 k 的位置,一定可以在 4 倍子串之前找到

很显然,到了四倍子串乘积必然为 1,之后就是一个大周期循环了,如果找不到后面也必然找不到。

结论:

ok,有了上述的定理二,我们求整串乘积就可以直接将重复数 K 裁减为 K % 4,这样就可以在 O(L) 的时间空间复杂度里面验证定理一。

然后,对于遍历搜查的目标,我们也可以直接重复数减少 4 的倍数,但是原本 X 大于等于 4 的话需要保持 X 大于 4:

S = single * (X % 4 + (4 if X >= 4 else 0))

然后就按照这个简化串 S 实施定理三查找前向和后向位置,然后判断位置是否保持顺序即可。

例程:
# 对于四元数的数据结构表示,这里使用一个 python 二元组
# 第一位是符号,第二位是字符,然后用判断逻辑实现了乘法
def multiply(a, b):
    s1, c1 = a
    s2, c2 = b
    s, c = s1 * s2, '1'
    if c1 == '1':
        c = c2
    elif c2 == '1':
        c = c1
    elif c1 == c2:
        s *= -1
        c = '1'
    elif c1 == 'i' and c2 == 'j':
        c = 'k'
    elif c1 == 'i' and c2 == 'k':
        s *= -1
        c = 'j'
    elif c1 == 'j' and c2 == 'k':
        c = 'i'
    elif c1 == 'j' and c2 == 'i':
        s *= -1
        c = 'k'
    elif c1 == 'k' and c2 == 'i':
        c = 'j'
    elif c1 == 'k' and c2 == 'j':
        s *= -1
        c = 'i'
    return s, c


def solve():

    for t in range(int(input())):

        L, X = map(int, input().split())
        single = str(input())

        # 先按照定理一判断整体乘积:
        val = (1, '1')
        for c in single * (X % 4):
            val = multiply(val, (1, c))

        result = val == (-1, '1')

        if result:

            # 生成简化串
            S = single * (X % 4 + (4 if X >= 4 else 0))

            # 记录查找位置
            p1 = p2 = -1

            # 从前往后
            n1 = (1, '1')
            for i in range(len(S)):
                n1 = multiply(n1, (1, S[i]))
                if n1 == (1, 'i'):
                    p1 = i
                    break

            # 从后往前
            n2 = (1, '1')
            for i in range(len(S)-1, -1, -1):
                n2 = multiply((1, S[i]), n2)
                if n2 == (1, 'k'):
                    p2 = i
                    break

            # 必须都找到,而且 p1 在 p2 前面,但是记得加上忽略掉的长度
            result = (p1 > -1 and p2 > -1) and p1 < p2 + (X * L - len(S))

        print('Case #%d:' % (t + 1), ('YES' if result else 'NO'))

solve()

原题内容:

题目链接:https://code.google.com/codejam/contest/6224486/dashboard#s=p0

Problem

The Dutch computer scientist Edsger Dijkstra made many important contributions to the field, including the shortest path finding algorithm that bears his name. This problem is not about that algorithm.

You were marked down one point on an algorithms exam for misspelling “Dijkstra” — between D and stra, you wrote some number of characters, each of which was either i, j, or k. You are prepared to argue to get your point back using quaternions, an actual number system (extended from complex numbers) with the following multiplicative structure:

dijkstra

To multiply one quaternion by another, look at the row for the first quaternion and the column for the second quaternion. For example, to multiply i by j, look in the row for i and the column for j to find that the answer is k. To multiply j by i, look in the row for j and the column for i to find that the answer is -k.

As you can see from the above examples, the quaternions are not commutative — that is, there are some a and b for which a * b != b * a. However they are associative — for any a, b, and c, it’s true that a * (b * c) = (a * b) * c.

Negative signs before quaternions work as they normally do — for any quaternions a and b, it’s true that -a * -b = a * b, and -a * b = a * -b = -(a * b).

You want to argue that your misspelling was equivalent to the correct spelling ijk by showing that you can split your string of is, js, and ks in two places, forming three substrings, such that the leftmost substring reduces (under quaternion multiplication) to i, the middle substring reduces to j, and the right substring reduces to k. (For example, jij would be interpreted as j * i * j; j * i is -k, and -k * j is i, so jij reduces to i.) If this is possible, you will get your point back. Can you find a way to do it?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with two space-separated integers L and X, followed by another line with L characters, all of which are i, j, or k. Note that the string never contains negative signs, 1s, or any other characters. The string that you are to evaluate is the given string of L characters repeated X times. For instance, for L = 4, X = 3, and the given string kiij, your input string would be kiijkiijkiij.

Output

For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is either YES or NO, depending on whether the string can be broken into three parts that reduce to i, j, and k, in that order, as described above.

Limits

1 ≤ T ≤ 100. 1 ≤ L ≤ 10000.

Small dataset

1 ≤ X ≤ 10000. 1 ≤ L * X ≤ 10000.

Large dataset

1 ≤ X ≤ 1012. 1 ≤ L * X ≤ 1016.

Sample
Input 

5
2 1
ik
3 1
ijk
3 1
kji
2 6
ji
1 10000
i

Output 

Case #1: NO
Case #2: YES
Case #3: NO
Case #4: YES
Case #5: NO

In Case #1, the string is too short to be split into three substrings.

In Case #2, just split the string into i, j, and k.

In Case #3, the only way to split the string into three parts is k, j, i, and this does not satisfy the conditions.

In Case #4, the string is jijijijijiji. It can be split into jij (which reduces to i), iji (which reduces to j), and jijiji (which reduces to k).

In Case #5, no matter how you choose your substrings, none of them can ever reduce to a j or a k.


【转载请附】愿以此功德,回向 >>

原文链接:https://www.huangwenchao.com.cn/2015/04/gcj-2015-qual-c.html【GCJ 2015 – Qualification Problem C – Dijkstra (迪科斯彻) – 解题报告】

发表评论

电子邮件地址不会被公开。 必填项已用*标注