4094 - WonderTeam

Do you want to discuss about these problems? Go now!
Users are shared (no need to re-register).

Moderator: Board moderators

Post Reply
New poster
Posts: 15
Joined: Tue Sep 25, 2007 3:07 am
Location: Astana, Kazakhstan

4094 - WonderTeam

Post by 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;

int cur = 0; // the current number of teams with higher rank than wonderteam
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.

New poster
Posts: 5
Joined: Sat Aug 23, 2008 8:25 am
Location: Iran

Re: 4094 - WonderTeam

Post by 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.
Mohammad Shokri

Post Reply

Return to “ACM ICPC Archive Board”