Test Set 1

Trong Test Set 1, ta cần tìm đúng một đoạn nếp gấp sao cho khi gấp chiếc khăn qua đoạn đó, các miền ở hai phía của đoạn thẳng chồng khít hoàn toàn lên nhau. Vì đoạn nếp gấp phải chia chiếc khăn thành hai miền đối xứng, ta có thể chứng minh rằng mỗi đầu mút của đoạn nếp gấp hoặc trùng với một đỉnh của đa giác biểu diễn chiếc khăn, hoặc là trung điểm của một cạnh đa giác. Nếu thử tạo một đoạn nếp gấp nối bất kỳ hai điểm nào khác, hai phần của cạnh bị chia không thể nào chồng khít hoàn toàn. Vì vậy, ta chỉ cần thử mọi đoạn thẳng nối một cặp điểm bất kỳ là đỉnh hoặc trung điểm cạnh của đa giác. Sau đó, với mỗi đoạn nếp gấp tiềm năng, ta kiểm tra tính hợp lệ bằng cách bảo đảm đoạn đó nằm hoàn toàn trong đa giác và hai miền mà nó tạo ra đối xứng qua chính đoạn nếp gấp ấy.

Có thể kiểm tra giao nhau giữa các đoạn thẳng chỉ bằng số nguyên. Phép phản xạ điểm qua một đường thẳng hoặc việc lấy trung điểm của một cạnh thông thường có thể tạo ra các điểm có tọa độ không nguyên. Tuy nhiên, ngay từ đầu ta có thể nhân tỉ lệ các điểm sao cho nếu phép phản xạ tạo ra một điểm có tọa độ không nguyên thì điểm đó chắc chắn không thể là một đầu mút hợp lệ của đoạn nếp gấp. Tất nhiên, ta cũng có thể chọn làm việc với phân số.

Với \(N\) điểm trong đa giác, ta có \(2N\) điểm để chọn làm đầu mút của đoạn nếp gấp. Mỗi đoạn nếp gấp tiềm năng có thể được kiểm tra trong thời gian \(O(N)\). Vì có \(O(N^2)\) đoạn thẳng khả dĩ cần kiểm tra, độ phức tạp thời gian tổng thể là \(O(N^3)\).

Lưu ý rằng để kiểm tra tính đối xứng qua một đoạn nếp gấp, ta không thể chỉ kiểm tra xem hai tập đỉnh của các đa giác biểu diễn hai miền có đối xứng hay không. Thay vào đó, ta phải chứng minh rằng với mọi cạnh của đa giác thuộc một miền, tồn tại đúng một cạnh trong đa giác biểu diễn miền thứ hai đối xứng với cạnh đó qua đoạn nếp gấp. Nói cách khác, thứ tự xuất hiện của các điểm ở mỗi phía là quan trọng.

Cuối cùng, nếu một đường thẳng thực sự là trục đối xứng của đa giác thì chắc chắn nó không giao với đa giác quá hai lần. Điều này có nghĩa là trong mã nguồn, ta không cần kiểm tra riêng rằng đoạn nếp gấp không giao với đa giác ở ngoài hai đầu mút của nó. Có thể áp dụng một cách đơn giản hóa tương tự cho lời giải Test Set 2 dưới đây.

Test Set 2

Vì cần vẽ một mẫu nếp gấp gọn gàng gồm \(K-1\) đoạn thẳng không giao nhau, ta phải chia chiếc khăn thành \(K\) miền có cùng kích thước và hình dạng; mỗi miền đều đối xứng với các miền khác có chung đoạn thẳng. Mỗi miền trong \(K\) miền này là một đa giác có các cạnh được tạo thành từ các đoạn nếp gấp và/hoặc các cạnh hay một phần cạnh của đa giác biểu diễn chiếc khăn. Có thể chứng minh rằng ít nhất hai miền trong số đó chỉ kề với một đoạn thẳng của mẫu nếp gấp, còn các cạnh khác xác định đa giác của miền đều thuộc đa giác ban đầu. Ta gọi các miền này là miền góc.

Nếu có một miền góc, ta có thể phản xạ miền đó qua đoạn nếp gấp duy nhất của nó để tìm ra miền bắt buộc phải kề với nó. Nếu tiếp tục phản xạ các miền này qua những cạnh của các đa giác tương ứng, đồng thời cẩn thận không tạo ra các miền giao nhau hay đi ra ngoài đa giác biểu diễn chiếc khăn, ta có thể tái dựng mẫu nếp gấp gọn gàng. Do đó, mọi mẫu nếp gấp gọn gàng đều có thể được xác định duy nhất chỉ bởi một đoạn nếp gấp nối hai điểm trên biên đa giác biểu diễn chiếc khăn. Đoạn thẳng ấy cắt ra một miền góc có thể được phản xạ liên tiếp để tạo nên toàn bộ mẫu nếp gấp.

Ta cần xét các cặp điểm trên biên khăn để xác định một đoạn nếp gấp. Với một đoạn nếp gấp ứng viên cho trước, ta có thể phản xạ liên tiếp miền góc vừa tạo để thu được toàn bộ mẫu nếp gấp. Nếu dùng nhiều hơn \(K-1\) phép phản xạ, hoặc nếu sau khi phản xạ xong ta không tạo lại được đa giác ban đầu, thì đoạn thẳng đã chọn không tạo ra một mẫu nếp gấp gọn gàng.

Bây giờ chỉ còn việc chọn tất cả các cặp điểm trên biên khăn. Rõ ràng ta không thể thử mọi cặp điểm có tọa độ hữu tỉ vì có vô hạn điểm như vậy. Thay vào đó, ta có thể chứng minh rằng đầu mút của các đoạn thẳng trong mẫu nếp gấp gọn gàng phải là đỉnh hoặc là điểm trên cạnh đa giác nằm tại vị trí bằng \(X/Y\) quãng đường giữa hai đỉnh liên tiếp, trong đó \(1 \le X \le Y-1\) và \(2 \le Y \le K\) (chứng minh ở bên dưới). Do đó, ta có thể tạo tất cả các điểm ứng viên này và kiểm tra mọi cặp. Với \(K \le 10\) và \(N \le 200\), có nhiều nhất \(6400\) điểm ứng viên có thể làm đỉnh của các đoạn thẳng trong mẫu nếp gấp gọn gàng. Như vậy số cặp có thể cần kiểm tra có cận trên là \(6400^2\). Tuy nhiên, ta có thể giảm đáng kể con số này bằng cách chỉ xét các cặp tạo ra một miền góc có diện tích bằng \(1/K\) diện tích chiếc khăn. Mỗi điểm có thể ghép với nhiều nhất \(2\) điểm khác để tạo thành một đoạn thẳng nằm hoàn toàn trong đa giác và cắt ra một miền góc có diện tích thích hợp. Vì vậy, ta chỉ cần kiểm tra những cặp này.

Ta có thể kiểm tra trong thời gian \(O(N)\) xem một đoạn thẳng tạo bởi một cặp điểm có cho ta một mẫu nếp gấp hợp lệ hay không, nếu cẩn thận dừng ngay khi một phép phản xạ tạo ra một điểm không nằm trên biên của bất kỳ đoạn cạnh nào thuộc đa giác. Ta có thể tính trước tất cả các điểm hợp lệ và dùng bảng băm để thực hiện phép kiểm tra này. Vì mọi điểm đều có dạng \(X/Y \times p\), trong đó \(p\) là một điểm có tọa độ nguyên và \(Y\) nằm trong khoảng từ \(2\) đến \(K\), ngay từ đầu ta có thể nhân mọi thứ với \(\operatorname{lcm}(2,3,\ldots,K)\) rồi làm việc bằng số nguyên; chỉ chia và rút gọn phân số khi xuất kết quả.

Tóm lại, thuật toán gồm các bước sau:

1. Tính tất cả các đầu mút khả dĩ. Độ phức tạp \(O(NK^2)\).
2. Tìm các đoạn ứng viên tạo ra một miền góc. Độ phức tạp \(O(NK^2)\).
3. Với mỗi ứng viên, gấp tối đa \(K-1\) lần và kiểm tra rằng mọi thứ đều hợp lệ.

Có tối đa \(O(NK^2)\) đầu mút khả dĩ. Nếu cố định một đầu mút \(P\) và duyệt đầu mút còn lại, ta có thể cập nhật diện tích trong quá trình duyệt và tìm tối đa \(2\) đoạn có một đầu mút tại \(P\) trong thời gian \(O(NK^2)\). Vì vậy, tổng thời gian của bước 2 là \(O(N^2K^4)\). Trong bước 3, mỗi lần mở nếp gấp cần phản xạ miền hiện tại và tìm các đoạn nếp gấp mới. Tất cả công việc đó tuyến tính theo kích thước miền; tổng kích thước của mọi miền không vượt quá tổng số đầu mút cộng thêm \(2K\) đầu mút dùng chung, nên tổng thời gian là \(O(NK^2)\). Kết hợp lại, độ phức tạp thời gian tổng cộng của thuật toán là \(O(N^2K^4)\). Có thể làm thuật toán hiệu quả hơn đáng kể, nhưng phần cài đặt hiện tại vốn đã đủ phức tạp.

Phụ lục

Để chứng minh rằng mọi đầu mút đoạn nếp gấp đều nằm tại vị trí bằng \(X/Y\) quãng đường giữa hai đỉnh liên tiếp, với \(1 \le X \le Y-1\) và \(2 \le Y \le K\), ta có thể chứng minh rằng số đoạn nếp gấp kề với một điểm không phải đỉnh của đa giác đầu vào là số lẻ hoặc bằng \(0\). Nếu điều đó đúng, gọi \(P\) là một đầu mút, còn \(Q\) và \(R\) là hai đỉnh và/hoặc đầu mút đoạn nếp gấp gần \(P\) nhất về mỗi phía trên cùng cạnh đa giác \(E\) chứa \(P\). Khi đó, do tính đối xứng, \(PQ=PR\). Lặp lại lập luận này dọc theo \(E\), ta thấy mọi điểm là đầu mút đoạn nếp gấp chia \(E\) thành các đoạn có độ dài bằng nhau.

Bây giờ ta chứng minh số đoạn nếp gấp kề với một điểm không phải đỉnh của đa giác là số lẻ hoặc bằng \(0\). Giả sử \(P\) là một điểm trên cạnh \(E\) của đa giác và có \(I>1\) đoạn nếp gấp kề với nó. Gọi \(Q_i\), với \(i=1,2,\ldots,I\), là đầu mút khác \(P\) của từng đoạn thẳng đó, theo thứ tự chiều kim đồng hồ. Gọi \(Q_0\) là ảnh phản xạ của \(Q_2\) qua \(PQ_1\), và \(Q_{I+1}\) là ảnh phản xạ của \(Q_{I-1}\) qua \(PQ_I\). Lưu ý rằng cả hai điểm này đều phải nằm trên \(E\). Khi đó, \(I+1\) góc \(Q_iPQ_{i+1}\) với \(i=0,1,\ldots,I\) đều bằng nhau. Gọi \(R_i\) là ảnh phản xạ của \(Q_i\) qua \(E\). Vì \(Q_i\) phải được phản xạ thành \(Q_{i+2}\), các độ dài \(PQ_0,PQ_2,PQ_4,\ldots,PQ_I\) đều bằng nhau và cũng bằng các độ dài \(PR_2,PR_4,\ldots,PR_I\). Các góc giữa hai đoạn liên tiếp trong số đó cũng đều bằng nhau, nên \(Q_0Q_2Q_4\ldots Q_IR_IR_{I-2}\ldots R_2\) là một đa giác đều. Mọi điểm đều có tọa độ hữu tỉ vì chúng là điểm đầu vào, đầu mút của đoạn nếp gấp hoặc ảnh phản xạ được tính từ các điểm khác có tọa độ hữu tỉ. Ta biết rằng đa giác đều duy nhất trong mặt phẳng có mọi đỉnh mang tọa độ hữu tỉ là hình vuông. Do đó, \(I/2+1+I/2=4\), suy ra \(I=3\), là một số lẻ.

Hình sau minh họa chứng minh trên cho trường hợp \(I=4\). \(P\) là điểm ở giữa, và các đoạn thẳng cùng màu chắc chắn có cùng độ dài.

Một hệ quả của chứng minh này là với mọi điểm không phải đỉnh trên đa giác ban đầu, điểm đó phải kề với đúng \(0\), \(1\) hoặc \(3\) đoạn nếp gấp.

Nguồn

Phần phân tích này được dịch đầy đủ từ lời giải chính thức của Google Code Jam 2019, Vòng 3 — Napkin Folding.