### 4094 - WonderTeam

Posted:

**Mon Sep 01, 2008 11:54 pm**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.

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.