10943 - How do you add?

Quantris · Post by **Quantris** » Sat Oct 22, 2005 4:54 am

I'm getting WA on this, but I fail to see why. Rather than ask for a hint, could someone with an AC just say if there was anything special you had to assume about the input that wasn't in the problem statement? As well, what is your output for 100 100?

(By special, I mean did you handle cases like 0 1 or 1 0 even though they shouldn't happen according to the statement, etc. The reason I'm not sure about the statement is because although they say the sums should be made of numbers "less than N", the example uses numbers less than or equal to N, which set off a warning bell off the bat.)

Thanks in advance!

Quantris · Post by **Quantris** » Sat Oct 22, 2005 5:36 am

never mind, I got AC, I think there are either 0 x or x 0 in the data.

Quantris · Post by **Quantris** » Sat Oct 22, 2005 6:30 am

yes, kind of

try to work out the recursion, then dp-ize it (this one is pretty straightforward in that regard)

one important thing is that sums such as 0+0+1 and 0+1+0 are counted separately (as in the sample, where 0+20 and 20+0 are both counted).

Observer · Post by **Observer** » Sat Oct 22, 2005 5:13 pm

Hi everyone,

I've just solved problem 10943 (How do you add?), with a very wrong code!!

Take this example:

Code: Select all

1 3
0 0

My Accepted code outputs 3, yet it is clearly incorrect, since one can easily find 6 solutions:

Code: Select all

So either the judge data set is too weak, or it is completely wrong! (Or does "add up to" mean that we must add positive numbers only?)

Not to mention the mistake in the problem description about "K numbers less than N"......

I would really like to see this problem revised.

Thanks for your attention.

Cho · Post by **Cho** » Sat Oct 22, 2005 5:26 pm

The description is not good enough.
"K numbers less than N" actually means "K non-negative numbers less than N".
I also noticed this point during the contest but I was thinking that this would be very easy if I don't need to consider negative numbers. So I just ignored the negative numbers and see whether it's AC or WA. It turn's out that I was right.
(Although, most of us got neither AC nor WA. We got OLE but it's another story.)

Observer · Post by **Observer** » Sat Oct 22, 2005 5:49 pm

Thanks for your reply, Cho.

I've checked my Longman Dictionary of Contemporary English, and it confirms my claim that the problem description is wrong (rather than not good enough). Sadly, the sample I/O just cannot illustrate this (since K is chosen to be 2; hope this is not deliberate!).

I'm so disappointed that we are required to solve a task quite different from what stated. (I'm a Math major student so when I first looked at this task I indeed thought about negative numbers).

Of course, we may also say that the judge solution doesn't solve the problem correctly...

P.S. Cho, your modified description is still incorrect. It should be:

"K numbers less than N" actually means "K non-negative integers not greater than N".

P.P.S. I would be happier to see the test data changed, rather than the description.

Cho · Post by **Cho** » Sat Oct 22, 2005 6:56 pm

Observer wrote:It should be:
"K numbers less than N" actually means "K non-negative numbers not greater than N".

Oops.. then I agree that the problem description is indeed wrong.

Observer wrote:P.P.S. I would be happier to see the test data changed, rather than the description.

I think this is unlikely to happen.

jan_holmes · Post by **jan_holmes** » Sat Oct 22, 2005 8:29 pm

Hi,Anyone could explain how DP worls here ??? Please Help... THx...

Larry · Post by **Larry** » Sat Oct 22, 2005 8:40 pm

The problem description is not as specific as it should've been, for which I apologize, as it is my first contest on UVa. I guess most problemsolvers have been jaded to the various trick cases people have thrown at because of the wording, but this was intended to be as a relatively simple DP problem, and no trick is intended..

Sanny · Post by **Sanny** » Sat Oct 22, 2005 9:07 pm

If you want to find how to make N with K numbers, you need to find first how to make N-i (i=0 to N) with K-1 numbers. Hope it helps.

Regards
Sanny

Bj · Post by Bj » Sat Oct 22, 2005 9:19 pm

Don't think of it is a DP-problem, think of it as a problem where you can save time by using a lookup table in the recursive function. It's way easier that way.

Quantris · Post by **Quantris** » Sun Oct 23, 2005 2:05 am

how else does one think of a DP problem?

Bj · Post by Bj » Sun Oct 23, 2005 3:11 am

Quantris wrote:how else does one think of a DP problem?

It's probably just me, but everything gets much harder when I learn there's a fancy name for the technique.

jan_holmes · Post by **jan_holmes** » Sun Oct 23, 2005 7:49 am

Thx foe the answers... Now,I'm starting to finished it....

But,could we use another way beside DP ??? Iterative maybe ???? Thx...

Per · Post by **Per** » Sun Oct 23, 2005 9:04 am

Larry wrote:The problem description is not as specific as it should've been, for which I apologize, as it is my first contest on UVa. I guess most problemsolvers have been jaded to the various trick cases people have thrown at because of the wording, but this was intended to be as a relatively simple DP problem, and no trick is intended..

All in all, I thought it was a nice contest, though a tad too easy.

One comment though: in general, things could have been more clearly defined. As it was, you had to follow your intuition rather than the problem statement on several problems. The most obvious example of this was problem D, where it is not at all stated what a hole is (i.e. that it is a set of connected squares of the same letter), much less whether grid squares are 4-connected or 8-connected. Following intuition worked for me, but I know from experience that when these things are not specified and following intuition does not work (and there are always people with a different intuition than yours

), you very easily get really frustrated.