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

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

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

Post by sclo » Sat Jun 10, 2006 6:15 pm

Any idea on how to solve this problem?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sat Jun 10, 2006 7:29 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:

Post by sclo » Sun Jun 11, 2006 6:06 am

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.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Wed Jun 14, 2006 5:11 pm

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
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Fri Aug 25, 2006 7:27 am

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!

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Fri Aug 25, 2006 8:23 am

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

Post by shanto86 » Fri Aug 25, 2006 12:20 pm

thanks for ur reply.
Self judging is the best judging!

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Sat Aug 26, 2006 6:07 am

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

Post by shanto86 » Sat Aug 26, 2006 6:12 am

AC
Self judging is the best judging!

annhy
New poster
Posts: 40
Joined: Sun May 27, 2007 1:42 am
Location: Taiwan

Post by annhy » Sun May 27, 2007 8:52 am

sclo wrote:Now, I finally got AC, after I fix my tie breaking rules.
AC.. :D

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

Post by kangbb » Mon Mar 01, 2010 7:46 pm

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

Post Reply

Return to “Volume 110 (11000-11099)”