Codeforces Round #709 Basic Diplomacy - Greedy

Solution

Greedy. But the problem is how to prove.

First of all, we have two different kinds of people.

Type #1, the number of days they can join is not more than $\frac{m}{2}$. For this type of people, we can chose them as much as possible.

Type #2, the number of days is more than $\frac{m}{2}$. After we use all the type #1, the remain days don't have type #1 people. And at least one type #2 people in these remain days.

If only have one type #2. Then just use this guy as much as possible. If enough, then YES. Otherwise, NO.

If there are more than one type #2. Because all other days are covered by type #1, and the type #2 can cover more than $\frac{m}{2}$ days. So have answer. Just use two of them. One cover half, and other one cover another half.

Questionable solution

The solution above is too complex to implement. So I tried this one, and get AC.

Sort the days by the number of people. The day have lesser people comes first. And scan the days one by one, for each day, the people who have lesser number of available days come first. (The available days means $\min{(\frac{m}{2}-(already\ assign\ days), (the\ number\ of\ days\ this\ people\ can\ join) - (already\ assign\ days))}$).

So the first priority is number of people for days. The second priority is the number of available days for people.

The issue of this solution is: The second type of people can be chose before first type of people.

For example:

There are 10 days only allow 2 people. One is type one.  Another one is type 2. Other days have more people available.

Then because type 2 have more available days can join. So by this way, these 10 days will use this type 2 people first. But it should use type #1.

But anyway get AC with this solution.

Code

The code get AC. But I still think it not correct. Maybe the data is too weak.