10997 - Medals

DongJoo Kim · Post by **DongJoo Kim** » Sat Mar 25, 2006 3:34 pm

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?

Krzysztof Duleba · Post by **Krzysztof Duleba** » Sat Mar 25, 2006 6:03 pm

Only very few values of j,k,l have to be checked.

lonelyone · Post by **lonelyone** » Mon Mar 27, 2006 7:37 am

"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

Krzysztof Duleba · Post by **Krzysztof Duleba** » Mon Mar 27, 2006 11:02 am

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.

bluebird · Post by **bluebird** » Sat Apr 01, 2006 8:50 am

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?

Krzysztof Duleba · Post by **Krzysztof Duleba** » Sat Apr 01, 2006 1:21 pm

What do you mean? Problem statement clearly says that you should only consider vectors of that form.

bluebird · Post by **bluebird** » Sat Apr 01, 2006 6:59 pm

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?

Krzysztof Duleba · Post by **Krzysztof Duleba** » Sat Apr 01, 2006 8:17 pm

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?

C · Post by C » Thu Apr 27, 2006 4:31 pm

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.

mf · Post by mf » Thu Apr 27, 2006 4:40 pm

http://plg.uwaterloo.ca/~acm00/060225/data/C.1.dat
http://plg.uwaterloo.ca/~acm00/060225/data/C.1.diff

C · Post by C » Fri Apr 28, 2006 6:40 pm

Thanks mf! I found my mistake. My algorithm is wrong...