11041 - Quarter-Finals with Brazil!? No!!!

[sclo]

Any idea on how to solve this problem?

[little joey]

It's not easy to give hints without spoiling the problem.
Use psychology: if you were playing in a knock-out competition, what kind of teams would you like to meet in which stage of the competition? The strongest teams first? Or maybe the weaker, in the hope another team knocks out the stronger teams?
Run a few simulations with a small number of teams, either by hand or write a BF program.
Getting the output right is the hardest part of the problem, IMO.

[sclo]

I can see the pattern for n=3, but for n=4, that is 16, it becomes too messy, I'll need to think about what happens more carefully. Good hint though.

Now, I finally got AC, after I fix my tie breaking rules.

[Krzysztof Duleba]

Nice problem!

My code seemed to be ok right away - it passed a set of 10^7 test cases, but still was getting WA. It took me 10 hours to find the error: using

Code: Select all

me -= 'A';

instead of

Code: Select all

if(isupper(me))me -= 'A';
else me = (me - 'a') + 26;

[shanto86]

well... can any one ensure me this greedy strategy?

we will try to select weak teams in my group. now in case of tie for weak, we will select such a team so that our answer becomes lex smallest.

is my approach right?

[Krzysztof Duleba]

Yes, that's correct (the proof is not dificult, too), except that the second part is not trivial.

[shanto86]

thanks for ur reply.

[shanto86]

some test case plz, getting WA

[shanto86]

AC

[annhy]

Now, I finally got AC, after I fix my tie breaking rules.

AC..

This problem contains two parts.

The first part can be solve by the GREEDY strategy posted above.
And the second part is to rearrange the round tree to minimize the string.

I found that the second part is more difficult than the first part.
(It really needs a good tie breaking rule)

[kangbb]

I first set s(our team) = 0, and sort the teams with smallest lex order.
But how can I rearrange the teams in second part? Can anyone give me some hints?
Thanks a lot !!