10786 - Qualify for the Champions League

[unknown_error]

I'm getting WA

Input:

Deleted

My Output:

[Eduard]

The right answer is

Code: Select all

League 1: 21 
League 2: 11 
League 3: 21 
League 4: 41 
League 5: 78

I think now you will get AC.

[unknown_error]

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

[Destination Goa]

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.

[Destination Goa]

In case there IS a formula, have you proven it or just tried the luck based on deleted input?

[Destination Goa]

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:

we are interested to find the minimum point that a team can score and be lucky enough to qualify.

But this phrase:

This 5-point difference is the minimum bar that a team should reach if they are to have any hope of moving on.

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).

[Antonio Ocampo]

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.

[Destination Goa]

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.

[Adrian Kuegel]

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).

[Destination Goa]

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.