## 10943 - How do you add?

Moderator: Board moderators

### 10943 - How do you add?

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

Quantris
Learning poster

Posts: 75
Joined: Sat Dec 27, 2003 4:49 am

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

Posts: 75
Joined: Sat Dec 27, 2003 4:49 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).
Quantris
Learning poster

Posts: 75
Joined: Sat Dec 27, 2003 4:49 am

### 10943 - How do you add?

Hi everyone,

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

Take this example:
Code: Select all
`1 30 0`

My Accepted code outputs 3, yet it is clearly incorrect, since one can easily find 6 solutions:
Code: Select all
`1 0 00 1 00 0 1-1 1 11 -1 11 1 -1`

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.

Last edited by Observer on Sat Oct 22, 2005 6:11 pm, edited 1 time in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Observer
Guru

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

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

Cho
A great helper

Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

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.
Last edited by Observer on Mon Oct 24, 2005 2:16 am, edited 1 time in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Observer
Guru

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

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.

Cho
A great helper

Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

### 10943 - How do you add?

jan_holmes
Experienced poster

Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore

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..
Larry
Guru

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

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
Sanny
Learning poster

Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET

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.
Bj
New poster

Posts: 24
Joined: Mon Oct 17, 2005 1:39 am
Location: Sweden

how else does one think of a DP problem?
Quantris
Learning poster

Posts: 75
Joined: Sat Dec 27, 2003 4:49 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.
Bj
New poster

Posts: 24
Joined: Mon Oct 17, 2005 1:39 am
Location: Sweden

### Thx...

Thx foe the answers... Now,I'm starting to finished it.... But,could we use another way beside DP ??? Iterative maybe ???? Thx...
jan_holmes
Experienced poster

Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore

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.
Per
A great helper

Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Next