Ta giải bài bằng hai nhận xét. Thứ nhất, tích của toàn chuỗi phải bằng \(-1=i\times j\times k\). Thứ hai, chỉ cần kiểm tra một số nhỏ bản sao của chuỗi đầu vào. Ta có thể tìm tiền tố ngắn nhất có tích \(i\), rồi tiền tố ngắn nhất của phần tiếp theo có tích \(j\). Nếu tìm được, phần còn lại có tích \(k\) nhờ tính kết hợp. Phần dưới chứng minh hai nhận xét và đưa ra cài đặt mẫu.

Không có nghiệm nếu toàn chuỗi không rút gọn thành -1

Gọi \(S\) là chuỗi đầy đủ gồm chuỗi đầu vào lặp \(X\) lần. Nếu \(S=A+B+C\) với ba phần không rỗng có tích lần lượt \(i,j,k\), thì tích của \(S\) là tích của ijk, tức \(-1\). Vì vậy, nếu nhân toàn bộ ký tự mà kết quả khác \(-1\), chắc chắn không có nghiệm.

Chiều ngược lại không đúng: nhiều chuỗi như ii, jj cũng có tích \(-1\) nhưng không thể là ba đoạn có tích lần lượt \(i,j,k\).

Hai chuỗi con đầu phải rút gọn thành i và j

Từ đây chỉ xét chuỗi có tổng tích \(-1\). Ta chỉ cần tìm hai đoạn đầu \(A,B\) có tích \(i,j\). Khi ấy phần còn lại \(C\) được bảo đảm có tích \(k\); đồng thời phải bảo đảm \(C\) không rỗng.

Cũng có thể tìm tiền tố ngắn nhất có tích \(i\) và hậu tố ngắn nhất có tích \(k\). Nếu chúng không chồng nhau, phần giữa có tích \(j\); phải cẩn thận vì phép nhân không giao hoán. Bài tập của editorial: liệu tiền tố và hậu tố có thể chồng nhau trong khi toàn chuỗi vẫn rút gọn thành ijk không? Câu trả lời là không.

Để tìm đoạn đầu, bắt đầu từ đầu \(S\), nhân lần lượt cho đến khi được \(i\). Từ vị trí hiện tại, làm tương tự đến khi được \(j\). Nếu tổng tích là \(-1\), phần còn lại không rỗng sẽ thành \(k\). Cách này quét \(O(LX)\) ký tự và giải được bộ nhỏ.

M = [[ 0,  0,  0,  0,  0 ],
     [ 0,  1,  2,  3,  4 ],
     [ 0,  2, -1,  4, -3 ],
     [ 0,  3, -4, -1,  2 ],
     [ 0,  4,  3, -2, -1 ]]

def mul(a, b):
  sign = 1 if a * b > 0 else -1
  return sign * M[abs(a)][abs(b)]

def multiply_all(S, L, X):
  value = 1
  for i in range(X):
    for j in range(L):
      value = mul(value, S[j])
  return value

def construct_first_two(S, L, X):
  i_value = 1
  j_value = 1
  for i in range(X):
    for j in range(L):
      if i_value != 2:
        i_value = mul(i_value, S[j])
      elif j_value != 3:
        j_value = mul(j_value, S[j])
  return i_value == 2 and j_value == 3

for tc in range(input()):
  L, X = map(int, raw_input().split())
  # maps 'i' => 2, 'j' => 3, 'k' => 4
  S = [(ord(v) - ord('i') + 2) for v in raw_input()]
  ok1 = multiply_all(S, L, X) == -1
  ok2 = construct_first_two(S, L, X)
  print "Case #%d: %s" % (tc + 1,
    "YES" if ok1 and ok2 else "NO")

Ma trận \(M\) là ma trận \(5\times5\): hàng/cột 0 không dùng, hàng/cột 1 ứng với đơn vị \(1\), còn 2, 3, 4 lần lượt biểu diễn \(i,j,k\) đúng như bảng nhân quaternion.

Tối ưu cho bộ lớn

Độ dài toàn chuỗi có thể tới \(10^{16}\), nên phải tối ưu cả multiply_all() và construct_first_two().

Tối ưu multiply_all()

Nhờ tính kết hợp, trước hết nhân một bản chuỗi dài \(L\) thành một giá trị, rồi nâng giá trị đó lên lũy thừa \(X\):

def multiply_all(S, L, X):
  value = 1
  for i in range(L):
    value = mul(value, S[i])
  return power(value, X) # computes value^X

Có thể dùng lũy thừa bằng bình phương trong \(O(\log X)\):

def power(a, n):
  if n == 1: return a
  if n % 2 == 0: return power(mul(a, a), n // 2)
  return mul(a, power(mul(a, a), (n - 1) // 2))

Khi đó multiply_all() tốn \(O(L+\log X)\), nhiều nhất khoảng 10040 phép nhân với giới hạn đề. Có thể cải thiện thành \(O(L)\) vì lũy thừa của mọi giá trị quaternion lặp lại sau bốn lần nhân; chỉ cần \(X\bmod4\) phép nhân:

def power(a, n):
  value = 1
  for i in range(n % 4):
    value = mul(value, a)
  return value

Tối ưu lời gọi construct_first_two()

Khi tìm tiền tố \(i\), ta bắt đầu bằng \(1\) và nhân từng ký tự. Nếu hết một bản mà chưa được \(i\), giá trị hiện tại thuộc \(1,j,k,-1,-i,-j,-k\). Nếu nó là \(1\), các bản tiếp theo lặp lại y hệt nên có thể kết luận thất bại; nếu không, tiếp tục.

Do chu kỳ lũy thừa dài tối đa 4, nếu sau bốn bản vẫn chưa gặp \(i\) thì không bao giờ gặp. Sau khi gặp \(i\), cùng lập luận cho đoạn \(j\) cần nhiều nhất bốn bản nữa. Vì thế có thể thay

  ok2 = construct_first_two(S, L, X)

bằng

  ok2 = construct_first_two(S, L, min(8, X))

Việc kiểm tra tổng tích \(-1\) bảo đảm logic về đoạn cuối, còn cách dựng phải giữ cho đoạn \(k\) không rỗng. Độ phức tạp của construct_first_two() giảm từ \(O(LX)\) xuống \(O(L)\), nên toàn thuật toán chạy \(O(L)\) mỗi test.

Nguồn

Bản dịch dựa trên phân tích chính thức Google Code Jam 2015 - Qualification Round - Dijkstra, kho Google Coding Competitions (Apache-2.0).