10786 - Qualify for the Champions League
Posted: Fri Dec 10, 2004 9:50 am
I'm getting WA 
Input:
Deleted
My Output:
Input:
Deleted
My Output:
Code: Select all
League 1: 21
League 2: 11
League 3: 21
League 4: 41
League 5: 78
OJ Board
The Online Judge board
https://onlinejudge.org/board/
10786 - Qualify for the Champions League
Page 1 of 1
Posted: Fri Dec 10, 2004 1:43 pm
The right answer is
I think now you will get AC.
Posted: Fri Dec 10, 2004 2:54 pm
thanks Eduard
I think it's a nice example of sleep of mind. I missed that tricky part while coding
i have also deleted the I/O. cause it's vey easy to generate formula
I think it's a nice example of sleep of mind. I missed that tricky part while coding
i have also deleted the I/O. cause it's vey easy to generate formula
Posted: Sat Feb 19, 2005 7:38 pm
Should I report achievable score or just a minimum over sorted ranklist?
E.g. consider the case N=2, V=1, Q=1.
Possible outcomes are:
0 3
3 0
1 1
So, 2 is minumum, but it's not achievable. Achievable minimum is 3. There is no correction program and I didn't yet make a code to check it on the sample output. Please tell me if the answer should be 2 or 3 for this case.
BTW, is there really a formula?? (just YES/NO). I thought those AC with 0.002 sec were precalculated tables over 320 possible cases.
E.g. consider the case N=2, V=1, Q=1.
Possible outcomes are:
0 3
3 0
1 1
So, 2 is minumum, but it's not achievable. Achievable minimum is 3. There is no correction program and I didn't yet make a code to check it on the sample output. Please tell me if the answer should be 2 or 3 for this case.
BTW, is there really a formula?? (just YES/NO). I thought those AC with 0.002 sec were precalculated tables over 320 possible cases.
Posted: Sat Feb 19, 2005 7:41 pm
In case there IS a formula, have you proven it or just tried the luck based on deleted input?
Posted: Sat Feb 19, 2005 11:17 pm
Well, got AC with heuristical formula based on generated tests for V=1,2,3. Got nothing to prove it anyway.
By the way, there is some lack of logic in the problem statement. First is that you actually have to output achievable score, not just minimal value greater than previous standing. This is arguable.
Also, as long as the team knows its score, it also knows outcome of games it played to achieve this score. This puts some limits on game outcomes to consider. E.g. if we wonder if our score of 3 might be winnable in some case for other teams, we already know by that time how we achieved this score. Either by 3 wins (so no team will gain extra point in case of 4 teams) or by 3 draws (all 3 other teams will gain one extra point). But we check all cases even for our own games, like we know our score after playing own games but we know nothing about goals we scored and even which games we have won.
This correlates nicely with:
By the way, there is some lack of logic in the problem statement. First is that you actually have to output achievable score, not just minimal value greater than previous standing. This is arguable.
Also, as long as the team knows its score, it also knows outcome of games it played to achieve this score. This puts some limits on game outcomes to consider. E.g. if we wonder if our score of 3 might be winnable in some case for other teams, we already know by that time how we achieved this score. Either by 3 wins (so no team will gain extra point in case of 4 teams) or by 3 draws (all 3 other teams will gain one extra point). But we check all cases even for our own games, like we know our score after playing own games but we know nothing about goals we scored and even which games we have won.
This correlates nicely with:
But this phrase:we are interested to find the minimum point that a team can score and be lucky enough to qualify.
sounds like they will definitely become qualified based on games between other teams. The wording "they are to have any hope" implies that they use all the information they have. And games played to get the score is part of that information (not provided in the input).This 5-point difference is the minimum bar that a team should reach if they are to have any hope of moving on.
Posted: Tue Apr 05, 2005 8:21 pm
Please help me! I don't know how can I solve this problem. It seems easy but I have a lot of doubts about it.
Thx in advance.
I don't know how can I solve this problem. It seems easy but I have a lot of doubts about it.Thx in advance.
Posted: Tue Apr 05, 2005 9:41 pm
As you may see in my previous message, try to guess the formula. It's much easier than all simulation code behind it... It appears like sin(asin(sqrt(x^2))) = (?) = x. Not that easy formula, but close.
Posted: Tue Apr 05, 2005 11:55 pm
I considered 3 possible cases in my program: 2 special cases, and a general case. For each case, there is an easy formula that can be derived with logic. Basic idea: the fewest points are needed, if a lot of teams play draws (because then, a game gives overall two points instead of three if one team wins).
Posted: Wed Apr 06, 2005 2:23 am
Adrian,
My thoughts told that it is better to give wins to teams who are above us to ensure most zeroes behind. Kinda greedy method. Then distribute draws as much as possible. Give as much wins to yourself as possible, and so, and so... I tried to write this 4 times, and each time threw everything away, and rewrote... until complete simualation Yes, it showed that draws are the best case, but that wasn't so obvious to me... and still isn't.
My thoughts told that it is better to give wins to teams who are above us to ensure most zeroes behind. Kinda greedy method. Then distribute draws as much as possible. Give as much wins to yourself as possible, and so, and so... I tried to write this 4 times, and each time threw everything away, and rewrote... until complete simualation
Yes, it showed that draws are the best case, but that wasn't so obvious to me... and still isn't.