266 - Stamping Out Stamps

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

Moderator: Board moderators

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

266 - Stamping Out Stamps

Post by Observer » Sun Feb 06, 2005 5:41 pm

Yeah I know the acceptance rate of this task is low... But...

The thing that I'm most unsure about is the output format. For this input,

Code: Select all

7
2 7 14 17 22 63 98
5
0
7
2 7 14 17 22 63 98
86
2999
143
0
0
My WA program gives:

Code: Select all

STAMP VALUES 2 7 14 17 22 63 98

AMOUNT 5
STAMPS USED 2 2 2

STAMP VALUES 2 7 14 17 22 63 98

AMOUNT 86
STAMPS USED 63 14 7 2

AMOUNT 2999
NO SOLUTION EXISTS

AMOUNT 143
STAMPS USED 63 63 17

Is that correct? Please help~ :wink:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

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

Post by little joey » Sun Feb 06, 2005 6:38 pm

Yes, that output is correct.

Since I made the testset and the accept rate is indeed very low, I would be interested in your WA solution. Could you PM it to me?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Feb 06, 2005 8:55 pm

I think the low acceptance rate is because of this:
"If there's still a tie, choose the stamps as expensive as possible."
It is not clear how exactly we should choose expensive stamps. Should the stamp with the maximum value be as expensive as possible, or should the stamp with the minimum value be as expensive as possible?
So, what should be the output for:
3
5 6 7
12
0

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

Post by little joey » Sun Feb 06, 2005 11:43 pm

Hmm. I see. I never thought of it otherwise than meaning your first interpretation (7 5 in your example). But now I see it can be ambiguous. What would be the right formulation?
Also for:
6
16 7 6 5 4 3
18
0
0
You should choose 7 7 4, and not 7 6 5 or 6 6 6 (or 16 3, but that is clear enough I would think).

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Feb 06, 2005 11:58 pm

I never thought of it otherwise than meaning your first interpretation (7 5 in your example).
That was also my first thought. However, I got WA with that.
I guess it is sufficient to include one sample test case that shows the difference.

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

Post by little joey » Mon Feb 07, 2005 12:50 am

Well, it seems I made a stupid mistake while producing the testset. Please forgive me and don't submit until the new files are updated to the judge. Old submissions will be rejudged, of course.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Mon Feb 07, 2005 2:53 am

Hi I guess you don't need my code anymore~ :D
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Mon Feb 07, 2005 9:24 am

little joey wrote:Well, it seems I made a stupid mistake while producing the testset. Please forgive me and don't submit until the new files are updated to the judge. Old submissions will be rejudged, of course.
Oh yeah~~We are making the same mistake :wink:
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Mon Feb 07, 2005 6:08 pm

Haha yeah I get Accepted now~ Thanks everyone!!!

P.S. What exactly was the flaw in the I/O? :-?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

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

Post by little joey » Mon Feb 07, 2005 6:19 pm

Good for you!
Saying what the flaw was, would be too big a hint. Let's just say I payed not enough attention to detail... and implemented an algo I thought I knew well enough.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Mon Feb 07, 2005 6:42 pm

Yes, after I read the problem, I just do the following:
1. implement the dp
2. add the boundary condition
3. AC XD

Surely I have overlook something that is not obvious~ :wink:
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Tue Feb 08, 2005 10:16 am

Oh the rank of my submission has slipped down to 2nd...... Weep :(

Never mind... hope I would know how to optimize the I/O process in PASCAL. :P
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Tue Feb 08, 2005 11:45 am

Well.....
I haven't done optimization on IO now.....
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sat Mar 18, 2006 1:20 am

I keep getting WA for this, and I think I got the boundary conditions.. does anyone have a test case? Thanks.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sat Mar 18, 2006 1:23 am

Nevermind, I misspelled something. Thanks!

Post Reply

Return to “Volume 2 (200-299)”