Page 1 of 2
266 - Stamping Out Stamps
Posted: Sun Feb 06, 2005 5:41 pm
by Observer
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~
Posted: Sun Feb 06, 2005 6:38 pm
by little joey
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?
Posted: Sun Feb 06, 2005 8:55 pm
by Adrian Kuegel
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
Posted: Sun Feb 06, 2005 11:43 pm
by little joey
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).
Posted: Sun Feb 06, 2005 11:58 pm
by Adrian Kuegel
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.
Posted: Mon Feb 07, 2005 12:50 am
by little joey
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.
Posted: Mon Feb 07, 2005 2:53 am
by Observer
Hi I guess you don't need my code anymore~
Posted: Mon Feb 07, 2005 9:24 am
by ..
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
Posted: Mon Feb 07, 2005 6:08 pm
by Observer
Haha yeah I get Accepted now~ Thanks everyone!!!
P.S. What exactly was the flaw in the I/O?
Posted: Mon Feb 07, 2005 6:19 pm
by little joey
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.
Posted: Mon Feb 07, 2005 6:42 pm
by ..
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~
Posted: Tue Feb 08, 2005 10:16 am
by Observer
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.
Posted: Tue Feb 08, 2005 11:45 am
by ..
Well.....
I haven't done optimization on IO now.....
Posted: Sat Mar 18, 2006 1:20 am
by Larry
I keep getting WA for this, and I think I got the boundary conditions.. does anyone have a test case? Thanks.
Posted: Sat Mar 18, 2006 1:23 am
by Larry
Nevermind, I misspelled something. Thanks!