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.)
Thanks in advance!
(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!
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:
My Accepted code outputs 3, yet it is clearly incorrect, since one can easily find 6 solutions:
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.
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
Code: Select all
1 0 0
0 1 0
0 0 1
-1 1 1
1 -1 1
1 1 -1
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.
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
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
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.)
"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.)
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:
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:
P.P.S. I would be happier to see the test data changed, rather than the description."K numbers less than N" actually means "K non-negative integers not greater than N".
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
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Oops.. then I agree that the problem description is indeed wrong.Observer wrote:It should be:"K numbers less than N" actually means "K non-negative numbers not greater than N".
I think this is unlikely to happen.Observer wrote:P.P.S. I would be happier to see the test data changed, rather than the description.
-
- Experienced poster
- Posts: 136
- Joined: Fri Apr 15, 2005 3:47 pm
- Location: Singapore
- Contact:
10943 - How do you add?
Hi,Anyone could explain how DP worls here ??? Please Help... THx... 

-
- Guru
- Posts: 647
- Joined: Wed Jun 26, 2002 10:12 pm
- Location: Hong Kong and New York City
- Contact:
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..
Check out http://www.algorithmist.com !
-
- Experienced poster
- Posts: 136
- Joined: Fri Apr 15, 2005 3:47 pm
- Location: Singapore
- Contact:
Thx...
Thx foe the answers... Now,I'm starting to finished it....
But,could we use another way beside DP ??? Iterative maybe ???? Thx...

All in all, I thought it was a nice contest, though a tad too easy.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..
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
