Editorial for Bedao Regular Contest 07 - ARRAYGAME


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Với ~n~ lẻ, ~illya~ có thể chọn hết tất cả ~\left\lfloor \frac{n}{2} \right\rfloor~ số ở các vị trí chẵn nếu muốn, vì vậy cách tối ưu nhất là sắp xếp sao cho ~\left\lfloor \frac{n}{2} \right\rfloor~ số lớn nhất của dãy ~a~ nằm ở các vị trí chẵn, số điểm cuối cùng của ~illya~ là tổng ~\left\lfloor \frac{n}{2} \right\rfloor~ số lớn nhất đó.

Cụ thể cách ~illya~ lấy tất cả các số ở vị trí chẵn như sau: nếu lượt ngay trước đó ~nkwn~ chọn số đầu dãy thì ~illya~ cũng chọn số đầu dãy, ngược lại nếu ~nkwn~ chọn số cuối dãy thì ~illya~ cũng chọn số cuối dãy.

Với ~n~ chẵn:

Nhận xét: ~nkwn~ có thể lấy toàn bộ các số ở vị trí chẵn hoặc toàn bộ các số ở vị trí lẻ nếu muốn.

Gọi ~A~ là tập các số ở vị trí lẻ, ~B~ là tập các số ở vị trí chẵn.

Theo nhận xét bên trên, nếu ~nkwn~ chơi tối ưu, số điểm ~nkwn~ đạt được sẽ không nhỏ hơn ~max(sum(A), sum(B))~.

Có thể chứng minh được(*): Nếu ~illya~ cũng chơi tối ưu, số điểm ~nkwn~ đạt được là ~max(sum(A), sum(B))~, và điểm của ~illya~ là ~min(sum(A), sum(B))~.

Do đó, ~illya~ cần tìm cách chia dãy ~a~ ban đầu thành 2 dãy con có số phần tử bằng nhau (tất nhiên không cần liên tiếp) sao cho tổng của dãy có tổng nhỏ hơn là lớn nhất có thể.

Sử dụng kĩ thuật quy hoạch động tương tự bài toán cái túi để giải các subtask đầu, kết hợp kiểu dữ liệu bitset để giải được subtask cuối cùng.

(*): ~illya~ sắp xếp dãy ~a~ sao cho:

  • Dãy con chỉ gồm các số ở vị trí lẻ của dãy ~a~ là dãy không giảm.
  • Dãy con chỉ gồm các số ở vị trí chẵn của dãy ~a~ là dãy không tăng.

~illya~ thực hiện các lượt chơi theo chiến thuật giống với trường hợp ~n~ lẻ: nếu lượt ngay trước đó ~nkwn~ chọn số đầu dãy thì ~illya~ cũng chọn số đầu dãy, ngược lại nếu ~nkwn~ chọn số cuối dãy thì ~illya~ cũng chọn số cuối dãy.

Theo chiến thuật trên, giả sử có ~x~ lượt trong ~n/2~ lượt ~nkwn~ chọn số đầu dãy, và ~y = n/2 - x~ lượt ~nkwn~ chọn số cuối dãy.

Gọi ~A~ là tập các số ở vị trí lẻ, ~B~ là tập các số ở vị trí chẵn, số điểm ~nkwn~ đạt được ~d~ là tổng ~x~ phần tử nhỏ nhất trong ~A~ và ~y~ phần tử nhỏ nhất trong ~B~.

Có ~2~ trường hợp:

  • Nếu tổng ~y~ phần tử lớn nhất trong ~A~ lớn hơn tổng ~y~ phần tử nhỏ nhất trong ~B~, suy ra ~d < sum(A)~.
  • Nếu tổng ~y~ phần tử lớn nhất trong ~A~ nhỏ hơn hoặc bằng tổng ~y~ phần tử nhỏ nhất trong ~B~, suy ra tổng ~x~ phần tử nhỏ nhất trong ~A~ nhỏ hơn hoặc bằng tổng ~x~ phần tử lớn nhất trong ~B~, vậy ~d \leq sum(B)~

Vì vậy, trong mọi trường hợp, số điểm của ~nkwn~ không vượt quá ~max(sum(A), sum(B))~.

Lưu ý: ~sum(A)~ là tổng các phần tử của dãy/tập hợp ~A~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.