Page 1 of 1

10997 - Medals

Posted: Sat Mar 25, 2006 3:34 pm
by DongJoo Kim
What I can think for 10997 is putting all the possible values.

It gives AC. However, I am thinking that there should be faster way to solve this kind of problem. Any idea?

Posted: Sat Mar 25, 2006 6:03 pm
by Krzysztof Duleba
Only very few values of j,k,l have to be checked.

Posted: Mon Mar 27, 2006 7:37 am
by lonelyone
"Only very few values of j,k,l have to be checked."

how to do this problem

could you please describe your method in detail

thanks a lot

Posted: Mon Mar 27, 2006 11:02 am
by Krzysztof Duleba
There's not much to describe.

Keep in mind that n is big. If j > k > l, then if you sort triples (g,s,b) by the value of g/n^j + s/n^k + b/n^l, the order you get doesn't depend on the actual values of j,k,l.

10997 - Medals

Posted: Sat Apr 01, 2006 8:50 am
by bluebird
Hi,

I can't think of the real/intended way to solve this problem. I managed to make an AC solution by trying the vectors

(n,1,1) (n,2,1) .... (n,n,1).....(n,n,n)

so basically, I try to change each component from 1 to n. This means I try a total of n^3 different vectors.

Clearly, this wasn't the intended solution, since some of the vectors may not be in the form (1/n^j, 1/n^k, 1/n^l). Can someone please point me in the right direction?

Posted: Sat Apr 01, 2006 1:21 pm
by Krzysztof Duleba
What do you mean? Problem statement clearly says that you should only consider vectors of that form.

Posted: Sat Apr 01, 2006 6:59 pm
by bluebird
Yes, but I guess the test data wasn't that comprehensive--even though my solution was wrong, it somehow got AC.

Regardless, I still get this problem. In your earlier posts, you said that if

j > k > l

and n is large enough, then the actual values of j k and l don't matter. Why is that?

Posted: Sat Apr 01, 2006 8:17 pm
by Krzysztof Duleba
Take two countries with (g1,s1,b1) and (g2,s2,b2) medals. If j > k > l and g1 > g2 (regardless the actual values), can the second coutry be ranked above the first one? Now let g1 = g2 and s1 > s2. Again, can the second coutry be ranked above the first one?

Posted: Thu Apr 27, 2006 4:31 pm
by C
I got WA. But I don't know why.
I generally sorted the g,s,b in all possible order(3!=6), if there is a way so that Canada rank frist,exists also i,j,k. Or else Canada cannot win.

Can someone give me some I/O data. PLZ ! Thanks in advance.

Posted: Thu Apr 27, 2006 4:40 pm
by mf

Posted: Fri Apr 28, 2006 6:40 pm
by C
Thanks mf! I found my mistake. My algorithm is wrong...