Phân tích

Bài toán này có thể được giải quyết bằng phương pháp mô phỏng.

Đầu tiên, chúng ta cần lưu trữ các nguyên tố nào kết hợp để tạo ra nguyên tố khác. Một cấu trúc dữ liệu dạng ánh xạ (map), chẳng hạn như hash map, là cách tuyệt vời để thực hiện việc này. Tiếp theo, chúng ta cần theo dõi các cặp nguyên tố xung khắc, lưu ý rằng một nguyên tố có thể xung khắc với nhiều nguyên tố khác; một tập hợp các cặp (set of pairs), dù không phải là cách hiệu quả nhất, vẫn có thể giải quyết được vấn đề.

Cuối cùng là quá trình mô phỏng. Đối với mỗi ký tự được triệu hồi:

1. Kiểm tra xem nó có kết hợp được với phần tử cuối cùng hiện tại trong danh sách hay không. Nếu có, thực hiện kết hợp.
2. Nếu không thể kết hợp, duyệt qua tất cả các phần tử đã có trong danh sách để xem ký tự mới này có xung khắc với bất kỳ phần tử nào không. Nếu có, xóa sạch danh sách.
3. Nếu cả hai điều kiện trên đều không thỏa mãn, thêm ký tự đó vào cuối danh sách.

Cách cài đặt

Dưới đây là mã giả theo phong cách Python để giải quyết bài toán:

# Let combo_list contain all the combinations as 3-letter strs.
# Let opposed_list contain all the opposed elements as 2-letter strs.
# Let invoke be a str containing the elements to invoke.
combos = dict()
opposed = dict()
for x in combo_list:
  combos[x[0] + x[1]] = x[2]
  combos[x[1] + x[0]] = x[2]
for x in opposed_list:
  opposed.add(x[0] + x[1])
  opposed.add(x[1] + x[0])
# Now combos contains a mapping from each pair to the thing it
# creates.  If one of the combinations was "ABC", then
# combos["AB"] = "C" and combos["BA"] = "C".
# opposed is filled in a similar way.

element_list = []
for element in invoke:
  # If element_list isn't empty, the last element might combine
  # with the element being invoked.
  if element_list:
    last_two = element_list[-1] + element
    if last_two in combos:
      element_list[-1] = combos[last_two]
    continue

  # Now we iterate through element_list to see if anything there
  # is opposed to the element being invoked.
  wipe_list = False
  for e in element_list:
    if (e + element) in opposed:
      wipe_list = True
  if wipe_list:
    element_list = []
    continue

  # There was no combination and no erasing: just append the
  # element to the list.
  element_list.append(element)

Độ phức tạp

Với \(N\) là số lượng nguyên tố được triệu hồi, \(C\) là số quy tắc kết hợp và \(D\) là số cặp xung khắc:

• Với mỗi nguyên tố được triệu hồi, việc kiểm tra kết hợp mất \(O(1)\) (nếu dùng map).
• Việc kiểm tra xung khắc mất tối đa \(O(N)\) bằng cách duyệt qua danh sách hiện tại.
• Tổng độ phức tạp cho mỗi bộ dữ liệu là \(O(N^2)\). Với \(N \le 100\), cách tiếp cận này hoàn toàn khả thi.

Dựa trên phân tích chính thức của Google Code Jam.