*** Sub1: \(m,n<=12\) **

Gọi \(f[i][tt]\) là khi xét xong người thứ \(i\), trạng thái các món quà đã dùng tập món quà \(tt\), \(c[i][tt]\) là tổng nguyện vọng của người \(i\) khi nhận các món quà có trạng
thái \(tt\).

• ban đầu \(f[0][0]=+oo\).
• Từ \(f[i][tt]\) ta sẽ cập nhật cho các \(f[i+1][…]\) bằng cách chọn ra các món quà
  cho người thứ \(i+1\), gọi trạng thái các món quà của người \(i+1\) là \(tt2\ (tt \&tt2=0)\),khi
  đó: \(F[i+1][tt|tt2]=max(F[i+1][tt|tt2],min(f[i][tt],c[i+1][tt2]))\);

Đpt: \(O(n * 4^m)\).

có thể giảm độ phức tạp xuống $n \times 3^m $ (Do tổng số cặp \(tt\) và \(tt2\) thỏa mãn là
\(3^m\)).

* Sub2: \(m \le 1200, n=2\).

• Thuật toán tham lam 1:

  • Khi còn có món quà chưa được phát, ta sẽ chọn ra người có tổng nguyện
    vọng nhỏ nhất (giả sử là người \(i\)), rồi phát cho người này món quà \(j\) (với \(s[i][j]\)
    là lớn nhất trong số các món quà chưa được phát). Cứ làm như vậy cho đến
    khi ko còn món quà nào.

• Thuật toán tham lam 2:

  • Mỗi lần phát quà ta ko chỉ phát cho 1 người mà có thể cho cả 2 người (mỗi
    người tối đa 1 món quà) sao cho tăng minw lớn nhất (có nhiều cách làm, có thể
    áp dụng cách làm của sub3).

Do cả 2 thuật toán đều chỉ là thuật tham lam nên ta có thể kết hợp cả 2 thuật
trên.

* Sub3: \(m=n<=1200\).

Nhận xét: Do \(n=m\) nên đáp án tối ưu mỗi bạn sẽ nhận đúng 1 món quà.

Khi đó ta có thể chia nhị phân đáp án và kiểm tra bằng cặp ghép cực đại

Để kiểm tra xem đáp án có \(>=x\) hay không thì với mỗi người \(i\) ta sẽ có 1 danh
sách những món quà có thể nhận (món quà \(j\) thỏa mãn khi \(s[i][j]>=x\)),sau đó ta
có thể dùng thuật toán cặp ghép để chia quà cho mỗi người, nếu cặp ghép cực
đại đạt \(n\) thì thỏa mãn.

Lời giải của BTC cuộc thi