10943 - How do you add?

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

10943 - How do you add?

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
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

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
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

10943 - How do you add?

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

1 0 0
0 1 0
0 0 1
-1 1 1
1 -1 1
1 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.

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

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

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

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

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
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

10943 - How do you add?

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

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

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

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
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

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
New poster
Posts: 24
Joined: Mon Oct 17, 2005 1:39 am
Location: Sweden

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
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

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

how else does one think of a DP problem? :)

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

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
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Thx...

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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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.

Post Reply

Return to “Volume 109 (10900-10999)”