[Codejam] Q-Round 2015-C. Dijkstra

출처 : Google Codejam Qualification Round 2015 C. Dikstra 

(https://code.google.com/codejam/contest/dashboard?c=6224486#s=p2)

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:



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, jijwould 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 ≤ 10¹².
1 ≤ L * X ≤ 10¹⁶.

Sample

Input	Output
5 2 1 ik 3 1 ijk 3 1 kji 2 6 ji 1 10000 i	Case #1: NO Case #2: YES Case #3: NO Case #4: YES Case #5: NO

---

영어로된 문제를 접할때마다 새삼스레 내가 영어를 못하고, 싫어했다는 사실을 다시금 깨닫는다.

이문제는 결국 X의 i,j,k로 이루어진 문자열(X)이 L번 반복될 때(즉, 총 길이는 X*L) 위 박스의 연산을 이용하여 이 문자열들을 압축하여 ijk 로 만들수 있는가의 문제이다.

연산은 교환법칙은 성립하지않고, 결합법칙은 성립한다.

associate, not comm을 보면 대수학의 추억이 살짝 들기도하고, i,j,k의 연산을보면 outer product가 생각나는, 뭔가 대학시절의 향수를 느끼게 만들법도 하지만, 이런 기호나 연산을 처음접한사람도 충분히 풀만한 문제라고생각한다. (적어도 내 풀이에선)

같이 푼 사람들은 대부분 앞에서부터 i,j,k를 만드는 식으로 접근을 했고, 나 역시 비슷하긴 했지만 먼저 전체를곱해서 -1이 되는지를보고, 앞에서부터 곱해서 i가 만들어지는지, 나머지를 연산하면서 j가 만들어지는지를 확인했다. 즉 굳이 분류를 하자면 패턴을 이용한 조금 어려운 구현문제라고 생각된다.