4094 - WonderTeam

[armansuleimenov]

I have been trying to solve this problem
http://acmicpc-live-archive.uva.es/nuev ... php?p=4094
from "Asia - Tehran - 2007/2008" since early morning.

I think greedy should work. According to my observations, the wonderteam should have 0 draws not to increase its points count. Hence, we need to find the number of its victories that maximizes the number of teams with more points than wonderteam. I will demonstrate my approach on the following example: let's say n = 4. Then each team plays 6 matches. If wonderteam is represented by this triple (3,0,3) [3 victories, 0 draws, 3 losses], then the team with the higher rank should have at least 10 points. It should be represented by (2,4,0). Now I need to assign these triples to as much teams as possible. But I don't see when to stop assigning, what is the stopping condition that shows the impossibility of the current configuration.

int mpt = 2*(n-1); // matches per team
int res=0; // the maximum number of teams with higher rank than wonderteam
for(int win=0;win<=mpt;++win) // search for all possible values of victories
{
int p = 3 * win + 1; // the points count of the team T with higher rank than the wonderteam
int won = win – 1; // win count of T
int draw = p-3*won; // draw count of T
int loss=mpt-won-draw; // loss count of T

if( (won<0) || (draw<0) || (loss<0)) continue;
if( (won>mpt) || (draw>mpt) || (loss>mpt)) continue;
if((won+draw+loss)!=mpt)continue;

int cur = 0; // the current number of teams with higher rank than wonderteam
// I TRIED ALL SORTS OF THINGS HERE, NO LUCK, ANY SUGGESTIONS
// HOW TO COUNT CUR?
res = max(res,cur);
}

Is my approach right? If yes, how to count cur? If not, what are the alternative approaches? It seems that so many coders got AC in <=20 minutes.

Thanks in advance.

[MSH]

Just take it easy! there is a simple solution to this problem. Of course finding this solution is not so simple, where in the contest, the first accepted solution was after 62 minutes and there was only 14 accepted solution from about 90 teams.
for any N > 4 you can find a way that the wonder team's rank is N-1. you can try it for N = 5 and find wonder team with rank 4 and simply you will find that works for any N > 4.