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

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

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

Any idea on how to solve this problem?

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
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
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
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';
``````

Code: Select all

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

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
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?
Self judging is the best judging!

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
Yes, that's correct (the proof is not dificult, too), except that the second part is not trivial.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
thanks for ur reply.
Self judging is the best judging!

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
some test case plz, getting WA
Self judging is the best judging!

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
AC
Self judging is the best judging!

annhy
New poster
Posts: 40
Joined: Sun May 27, 2007 1:42 am
Location: Taiwan
sclo wrote: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
New poster
Posts: 1
Joined: Wed Apr 08, 2009 12:18 pm

### Re: 11041 - Quarter-Finals with Brazil!? No!!!

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 !!