Test Set nhỏ: DP tập con với hai cực trị

Số thứ tự có thể là \(N!\), quá lớn để thử hết, nhưng ta có thể dùng mẹo DP tập con quen thuộc để biến thừa số giai thừa thành \(2^N\): với mỗi tập thẻ, chỉ giữ lại số ít kết quả còn đáng xét thay vì mọi thứ tự của tập đó.

Chỉ giữ giá trị lớn nhất của một tập thẻ là sai: thẻ cuối * -1 biến giá trị nhỏ nhất trước đó thành lớn nhất. Với mỗi tập con \(C\), lưu cả \(lo[C]\) và \(hi[C]\). Thử mỗi thẻ \(c\) làm cuối và áp dụng nó lên cả \(lo[C\setminus\{c\}]\), \(hi[C\setminus\{c\}]\); lấy min/max của mọi kết quả. Cơ sở của tập rỗng là \(S\).

Viết chính thức hơn, \(g(C,\operatorname{max})\) và \(g(C,\operatorname{min})\) lần lượt là kết quả lớn nhất và nhỏ nhất khi áp dụng các lá trong \(C\) lên \(S\). Để tính \(g(C,m)\), thử từng lá cuối \(c\in C\) và từng \(m'\in\{\operatorname{min},\operatorname{max}\}\), áp dụng \(c\) lên \(g(C\setminus\{c\},m')\), rồi lấy cực trị \(m\) trong mọi kết quả đó. Cơ sở là \(g(\varnothing)=S\), và đáp án là \(g(C,\operatorname{max})\) với \(C\) là toàn bộ bộ bài.

Ta chứng minh định nghĩa này đúng bằng quy nạp đầy đủ theo kích thước \(C\). Với tập rỗng, kết luận đúng ngay theo cơ sở. Xét \(C\) khác rỗng, giả sử cả hai cực trị đã đúng cho mọi tập nhỏ hơn \(C\), và lấy một thứ tự tối ưu cho cực trị \(m\) của \(C\). Gọi \(c\) là lá cuối và \(T\) là kết quả sau tất cả các lá còn lại.

Nếu \(c\) là + v hoặc - v, phép tịnh tiến bảo toàn thứ tự. Vì vậy \(T\) phải chính là \(g(C\setminus\{c\},m)\): nếu không, thay phần thứ tự trước \(c\) bằng thứ tự đạt cực trị ấy sẽ cho \(g(C\setminus\{c\},m)+v\) hoặc \(g(C\setminus\{c\},m)-v\), tốt hơn kết quả được cho là tối ưu. Lập luận y hệt áp dụng cho * v và / v khi \(v\) không âm, vì chúng cũng bảo toàn thứ tự. Khi \(v\) âm, phép nhân hoặc chia đảo thứ tự, nên cực đại sau \(c\) phải lấy từ cực tiểu trước \(c\), và ngược lại. Vì công thức thử cả hai giá trị của \(m'\), mọi trường hợp đều được bao phủ; không một giá trị nội bộ nào có thể tốt hơn hai cực trị đã giữ.

Chứng minh còn cho thấy thực ra không cần thử cả hai \(m'\) cho mỗi lá cuối: dấu và loại phép toán xác định duy nhất phải lấy cực trị cùng loại hay cực trị đối diện. Tuy nhiên, thử cả hai đơn giản hơn và không làm thay đổi đáng kể thời gian chạy.

Có \(2^N\) tập, mỗi tập thử \(O(N)\) thẻ, tức \(O(2^NN)\). Nếu toán hạng có tối đa \(D\) chữ số, số trung gian có \(O(ND)\) chữ số và phép toán có cận \(O(ND^2)\), cho cận tổng được editorial nêu là \(O(2^NN^2D^2)\).

Chuẩn hóa cho Test Set lớn

Bỏ cộng/trừ \(0\) và đổi dấu phép toán để mọi toán hạng cộng/trừ dương. Trong một biểu thức cố định, phân phối để đưa mọi cộng/trừ về cuối: giá trị của một thẻ cộng/trừ được nhân/chia bởi toàn bộ thẻ nhân/chia nằm bên phải nó. Ví dụ

Coi \(S\) như thẻ +S, tác động của nó luôn là \(S\) nhân với tích mọi toán hạng nhân rồi chia cho tích mọi toán hạng chia, độc lập với thứ tự.

Với thứ tự nhân/chia cố định, mỗi khe có hệ số \(F\). Đặt mọi phép cộng tại khe có \(F\) lớn nhất, mọi phép trừ tại khe có \(F\) nhỏ nhất. Vì các phép cùng loại giao hoán, gộp chúng thành một thẻ cộng có toán hạng là tổng và một thẻ trừ là tổng.

Gộp các thẻ nhân/chia

Giữ thứ tự hai thẻ cộng/trừ, mỗi thẻ nhân/chia chỉ cần vào một trong ba vùng: trước cả hai, giữa hai thẻ, hoặc sau cả hai. Ba vùng lần lượt tác động lên \(S\); lên \(S\) cùng đúng một trong hai tổng; hoặc lên toàn biểu thức.

Sau khi cố định các thẻ âm, đặt mọi phép nhân dương cùng vùng có giá trị hiện tại lớn nhất và mọi phép chia dương cùng vùng có giá trị nhỏ nhất; do đó mỗi loại gộp thành một thẻ. Mọi *0 chỉ có thẻ nằm bên phải nhất ảnh hưởng, nên gộp thành nhiều nhất một thẻ.

Hai phép nhân âm ở cùng vùng cho hệ số dương và có thể chuyển cả cặp về vùng tối ưu. Mỗi vùng không tối ưu chỉ cần giữ nhiều nhất một thẻ âm; để đổi dấu với thiệt hại nhỏ nhất, giữ thẻ có trị tuyệt đối nhỏ nhất. Có hai vùng không tối ưu, nên ngoài nhóm đã gộp chỉ cần giữ hai thẻ nhân âm nhỏ nhất; tương tự cho chia âm.

Cuối cùng còn nhiều nhất \(11\) thẻ:

• một cộng, một trừ;
• một nhân \(0\), một nhân dương, một chia dương;
• tối đa ba nhân âm và ba chia âm.

Chạy DP Small trên tối đa \(11\) thẻ. Một lựa chọn khác là thử hai thứ tự cộng/trừ và gán tối đa tám thẻ nhân/chia vào ba vùng, chỉ \(2\cdot3^8\) cấu hình; mỗi cấu hình dùng số lớn có tổng chi phí \(O(N^2)\) theo phân tích. Có thể suy luận thêm để hạ cận \(11\) lá xuống nữa; ngược lại, cũng có những hướng lập luận khác chỉ thu được cận hơi lớn hơn nhưng vẫn đủ nhỏ để DP tập con chạy được.

Vì sao phép phân phối giúp thu gọn

Giả sử mọi lá đã được sắp thành biểu thức \(E\). Ta có thể lần lượt phân phối nhân/chia để chuyển từng phép cộng và trừ sang bên phải, tạo biểu thức \(E'\) gồm phần nhân/chia trước rồi mới đến các số hạng cộng/trừ. Để giá trị không đổi, toán hạng của mỗi phép cộng/trừ phải được nhân với mọi phép nhân và chia cho mọi phép chia nằm bên phải nó trong \(E\).

Chẳng hạn,

Lá + 1 trở thành + 2 vì bị nhân 4 rồi chia 2; lá - 6 thành - 3 vì chỉ có phép chia 2 ở bên phải. Nếu coi giá trị ban đầu là một lá cố định + S, ta cũng chuyển nó sang cuối và bắt đầu biểu thức từ 0. Vì vậy, bất kể thứ tự, đóng góp của \(S\) luôn bằng \(S\) nhân tích mọi toán hạng nhân rồi chia cho tích mọi toán hạng chia.

Với một thứ tự cố định của các phép nhân/chia, mỗi khe chèn có một hệ số hữu tỉ \(F\): mọi phép cộng/trừ đặt ở đó đều được nhân với \(F\). Trong tổng cuối, phép cộng cần hệ số lớn nhất, còn phép trừ cần hệ số nhỏ nhất. Nếu có nhiều khe cùng hệ số thì gom ở bất kỳ một khe nào vẫn tối ưu. Đây là lý do đầy đủ để thay tất cả phép cộng bằng một phép cộng tổng và tất cả phép trừ bằng một phép trừ tổng.

Chi tiết các phép nhân và chia âm

Sau khi cố định thứ tự của hai lá tổng, ba vùng có ý nghĩa khác nhau: vùng trước cả hai chỉ biến đổi \(S\); vùng giữa biến đổi \(S\) cùng tổng đứng trước; vùng sau biến đổi toàn bộ giá trị. Khi đã cố định vị trí các lá âm, một phép nhân dương phải tác động lên giá trị lớn nhất trong ba giá trị này, còn một phép chia dương phải tác động lên giá trị nhỏ nhất. Bởi vậy từng loại dương có thể đặt cùng nhau rồi gộp toán hạng.

Phép nhân 0 xóa sạch mọi thứ đứng bên trái; trong nhiều lá * 0, chỉ lá nằm xa nhất bên phải có tác dụng cuối cùng, nên giữ nhiều nhất một lá. Với phép nhân âm, hai lá ở cùng vùng tạo thành hệ số dương và có thể cùng chuyển tới vùng tốt nhất dành cho phép nhân dương. Sau khi chuyển hết các cặp, mỗi vùng không tối ưu chỉ còn tối đa một lá lẻ; nếu cần để lại một lá đổi dấu thì lá có trị tuyệt đối nhỏ nhất gây thiệt hại ít nhất. Có hai vùng không tối ưu, nên chỉ cần tách riêng hai trị tuyệt đối nhỏ nhất và gộp phần còn lại. Lập luận đối xứng áp dụng cho phép chia âm, dù vùng tối ưu của phép chia có thể khác.

Như vậy danh sách rút gọn gồm tối đa 11 lá và bảo toàn chính xác đáp án, không chỉ tạo một cận. DP tập con đã chứng minh cho Test Set 1 vì thế giải được Test Set 2. Mọi phép so sánh và phép tính phải dùng phân số/số nguyên lớn chính xác; cuối cùng chia tử và mẫu cho gcd rồi đổi đồng thời dấu nếu mẫu âm.

Phần trình bày dựa trên phân tích chính thức của Google Code Jam 2017, World Finals.