266 - Stamping Out Stamps

Observer · 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~

little joey · 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 · 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

little joey · 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 · 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.

little joey · 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 · Post by **Observer** » Mon Feb 07, 2005 2:53 am

Hi I guess you don't need my code anymore~

.. · 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

Observer · 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?

little joey · 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.

.. · 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~

Observer · 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.

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

Well.....
I haven't done optimization on IO now.....

Larry · 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 · Post by **Larry** » Sat Mar 18, 2006 1:23 am

Nevermind, I misspelled something. Thanks!