BONGDA - Lịch thi đấu bóng đá

Problem

https://vn.spoj.com/problems/BONGDA

https://oj.vnoi.info/problem/BONGDA

Một giải thi đấu bóng đá được tổ chức theo thể thức thi đấu vòng tròn, ở đó hai đội bóng bất kỳ sẽ được thi đấu với nhau đúng một trận.

Trong mỗi trận đấu, đội thắng được 3 điểm, còn đội thua được 0 điểm. Không có kết qủa hòa (nếu hòa trong hai hiệp chính thì hai đội sẽ phải thi đấu luân lưu để phân định thắng thua).

Kết thúc mùa giải, đội vô địch là đội có số điểm cao nhất. Trong trường hợp có nhiều hơn một đội được điểm cao nhất thì các đội này đồng đoạt chức vô địch.

Giải đã diễn ra được một thời gian. Lúc này một bài toán nảy sinh: người ta cần biết mỗi đội bóng còn có khả năng đoạt chức vô địch nữa hay không?

Yêu cầu

Biết kết qủa các trận đấu đã diễn ra, bạn hãy cho biết mỗi đội bóng còn có khả năng đoạt chức vô địch mùa giải nữa hay không?

Dữ liệu

Dòng 1: chứa số nguyên dương N là số đội bóng tham gia giải đấu. Các đội bóng được đánh số thứ tự từ 1 đến N.
N dòng tiếp theo, dòng i chứa N số nguyên dương ai1, ai2, … , aiN, trong đó aij cho biết trạng thái của trận đấu giữa đội i và đội j:
- aij = 0, nếu đội j thắng.
- aij = 1 nếu đội i thắng
- aij = 2 nếu trận đấu chưa diễn ra.
- Nếu i khác j, dữ liệu vào đảm bảo aij= aji = 2 hoặc aij + aji = 1. Dữ liệu vào đảm bảo aii = 0 với mọi i

Kết qủa

Gồm 1 dòng duy nhất, là một dãy nhị phân độ dài N, ở đó bit thứ i bằng 1 nếu đội bóng i còn khả năng vô địch mùa giải, và bằng 0 nếu đội bóng i không còn khả năng vô địch mùa giải.

Giới hạn

N là số nguyên dương trong phạm vi [1, 30]

Ví dụ

Tutorial

Với mỗi i, muốn i vô địch, trước hết những trận còn lại của i phải thắng. Sau đó tối ưu hoàn toàn những người còn lại để điểm của họ là thấp nhất có thể. Dễ thấy một thuật toán tham lam đơn giản, chính là ưu tiên những người thấp điểm nhất để họ thắng những trận của họ cho đến khi hoặc điểm bằng điểm của i, hoặc đã thắng hết những trận còn lại.

Tuy nhiên thuật tham lam này vẫn chưa hoàn toàn đúng, cũng dễ hiểu vì N <= 30 mà mình chỉ mới dùng tồi nhất chỉ là O(N^3), tối ưu hơn chỉ là O(NlogN + N^2) thôi.

Nhận thấy khi cho j (người có điểm thấp nhất hiện tại) thắng k (người chưa đấu với j) thì ta ưu tiên k có điểm lớn nhất (để tránh trường hợp j thắng những đứa tồi, nhưng lại phải thua những đứa mạnh như k vậy). Do đó thuật toán tồi nhất của ta O(N^4), có thể tối ưu hơn nhưng với N <= 30 thì thuật này là hoàn hảo

Submission

BONGDA.cpp

Tutorial SPOJ