Test Set nhỏ

Small chỉ có tối đa 10 trẻ, nên có thể thử mọi cách sắp xếp và kiểm tra vòng nào hợp lệ: với mọi tập con và mọi thứ tự vòng tròn của tập đó, kiểm tra mỗi em có ít nhất một hàng xóm là BFF; nếu có, cập nhật đáp án lớn nhất bằng kích thước vòng.

Có vài tối ưu nhỏ nhưng mạnh. Các hoán vị của một tập \(S\) luôn xuất hiện như tiền tố trong các hoán vị của mọi tập chứa \(S\). Hơn nữa, khi kiểm tra BFF, khác biệt duy nhất nằm ở cách xử lý em đầu và cuối. Vì thế chỉ cần duyệt mọi hoán vị của \(N\) em và xét mỗi tiền tố có tạo thành vòng hợp lệ không. Cách này đã tính mọi hoán vị của mọi tập con và giảm đáng kể số lần kiểm tra. Một số tập được xét nhiều lần nhưng không sao nếu vẫn kịp thời gian.

Mã Python chính thức:

import itertools
# The F parameter is the list of BFF identifiers, but 0-based (subtracting 1 from the input).
def cc(F):
  n = len(F)
  r = 0
  # Iterate over all possible orderings of the n kids.
  for O in itertools.permutations(xrange(n)):
    first = O[0]
    second = O[1]
    for i in xrange(1, n):  # Iterate over the permutation, skipping the first.
      # Check if i can be the last one by checking it and the first.
      prev = O[i - 1]
      cur = O[i]
      if ((F[cur] == first or F[cur] == prev) and
          (F[first] == cur or F[first] == second)):
        r = max(r, i + 1)
      # Check if i can be in the middle, and stop if it can't.
      if F[cur] != prev and (i == n - 1 or F[cur] != O[i + 1]):
        break
  return r

Test Set lớn

Vét cạn không đủ nhanh cho Large. Dữ liệu vào thực chất là một hàm BFF ánh xạ mỗi em sang một em khác. Biểu diễn nó bằng đồ thị của một hàm, mỗi đỉnh là một em và cạnh từ em đó đến BFF. Mỗi thành phần liên thông gồm một chu trình có hướng cùng các nhánh có cạnh hướng vào chu trình; nếu co chu trình thành một đỉnh, ta được một cây mà mọi cạnh hướng về gốc. Đặc biệt, mỗi thành phần có đúng một chu trình.

Xét dạng của một vòng hợp lệ. Nó chứa ít nhất một em \(k_1\), nên cũng phải chứa BFF \(k_2\) ngồi cạnh \(k_1\), rồi BFF \(k_3\) của \(k_2\) (có thể chính là \(k_1\)), và tiếp tục. Trên đồ thị, ta đi theo các cạnh từ \(k_1\) và cuối cùng lặp trên chu trình của thành phần chứa \(k_1\) (chu trình có thể không chứa \(k_1\)). Vì vậy, nếu vòng chọn ít nhất một em trong một thành phần, nó phải chứa toàn bộ chu trình của thành phần ấy.

Nếu chu trình có hơn 2 em, đặt chu trình đó vào vòng đã cố định cả hai hàng xóm của mỗi em, nên không còn chỗ cho ai khác. Một khả năng của đáp án là toàn bộ một chu trình đơn lẻ trong đồ thị.

Không có chu trình độ dài 1 vì không ai là BFF của chính mình. Với chu trình độ dài đúng 2 gồm \(l\) và \(r\), tình hình khác: đặt \(l,r\) cạnh nhau làm cả hai hài lòng và vẫn còn chỗ ở phía trái của \(l\) và phía phải của \(r\) (hoặc ngược lại). Ta có thể chọn \(l_1\) có BFF là \(l\) để ngồi cạnh \(l\), rồi \(l_2\) có BFF là \(l_1\), và tiếp tục. Đó là một chuỗi đi ngược cạnh ở phía \(l\); làm tương tự ở phía \(r\). Sau khi thêm không hoặc nhiều em vào mỗi phía, ta có một hàng trong cùng thành phần mà mọi em đều hài lòng, và vẫn có thể nối thêm trẻ từ thành phần khác ngay bên cạnh.

Tóm lại, từ mỗi thành phần có chu trình độ dài 2, ta lấy chuỗi dài nhất gồm chu trình cùng nhánh dài nhất ở mỗi phía, rồi nối tất cả các chuỗi ấy lại. Tổng độ dài của chúng là một ứng viên, đem so với độ dài chu trình lớn nhất ở trường hợp trước.

Hình sau minh họa ba thành phần riêng. Các đỉnh đỏ thuộc chu trình. Thành phần có chu trình độ dài 4 tạo được một vòng ở bên phải nhưng không thêm được ai. Với mỗi chu trình độ dài 2, các lựa chọn nhánh tối ưu được tô xanh lá và cam; vòng bên phải cùng các mũi tên cho thấy BFF của mỗi em ở cạnh mình. Chu trình độ dài 2 cho phép nối thêm cả các thành phần khác, còn chu trình dài hơn không để lại chỗ.

https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_a676db10.png

Có thể tìm các thành phần và chu trình bằng DFS hoặc nhiều cách khác. Cũng có nhiều cách tìm nhánh dài nhất ở mỗi phía của chu trình 2; bài phân tích để người đọc tự chọn. Quá trình ở mỗi phía thực chất rất giống tìm chiều cao của một cây.

Nguồn

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