10997 - Medals

All about problems in Volume 109. 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
DongJoo Kim
New poster
Posts: 20
Joined: Tue Sep 20, 2005 9:20 am
Location: Daejeon, Korea

10997 - Medals

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?

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

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

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

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

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

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

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
New poster
Posts: 12
Joined: Mon Oct 17, 2005 2:35 am
Location: Canada

10997 - Medals

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?

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

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
New poster
Posts: 12
Joined: Mon Oct 17, 2005 2:35 am
Location: Canada

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?

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

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
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 pm

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

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


C
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 pm

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

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

Post Reply

Return to “Volume 109 (10900-10999)”