## 10656 - Maximum Sum (II)

Moderator: Board moderators

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

### 22.05.04 Contest Problem F, 10656

What the heck does it mean? The wording of the problem is so bad ...
Last edited by brianfry713 on Tue Jan 28, 2014 3:04 am, edited 1 time in total.

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:
Thats right... its seems confusing and sometimes senseless, like the phrase: A valid sequence must have a single number in it.

Hmm... in the output example, the sequence has two numbers on it....

The other possibility is that I completely misunderstood the problem....

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am
A more complex example would have helped, as the problem statement is now it's just like: "Guess what the problem setter had in mind". I hope I'll never see such bad statements again.

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
It sounds totally ambiguous, as it doesn't specify what the ordering of the numbers in the sequence [an ordered set of mathematical objects which is denoted using braces (mathworld)] should be.. (strictly/weakly) increasing, (strictly/weakly) decreasing, as ordered by the input.. etc..

I tried all three possibilities, none of which seemed to work.

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am
I tried consecutive numbers, numbers different from 0, and I also tried to assume that the numbers were also negative so a question of maximum sum sequence would make sense ... None of them worked.

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

### solved

After a couple of trials I managed to solve this one. Here's what you should do to get AC:

- print all non-zero input numbers in their original order
- but if all input numbers are zero, print just one zero

That's it. Great problem huh? So many programming skills and algorithms combined in just one problem....

Erik

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
But if you do that, isn't your output sequence actually a subsequence of the original input (heck, any output that doesn't have the same number of elements is actually a subsequence, since you have removed some elements)

And by that logic, shouldn't the answer just mirror the input exactly?
Last edited by UFP2161 on Sat May 22, 2004 5:17 pm, edited 1 time in total.

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am
Wow nice one, sorry for what I said before, I hope next programming contests will have a lot more problems like this, it's nice to play guessing games instead of programming

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland
UFP2161, yes the output sequence is a subsequence of the input. But it isn't a mirror since all zeroes have been removed.

Cosmin.ro I couldn't agree with you more. Next time, just avoid all problems of Shahriar Manzoor.

Dumitru
New poster
Posts: 1
Joined: Sat May 22, 2004 5:33 pm
What type of incompetent description was it at problem F ???

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
Maniac: Then, doesn't that violate the second sentence in the problem:
Note that I am asking for a sequence, not sub sequence.

nealzane
New poster
Posts: 23
Joined: Tue Dec 10, 2002 2:13 am
Location: China
Contact:
what a twisted hobby of making simple things into vague descriptions. a problem setter at his position shall know lots of other ways to make hard problems, which are worth practicing and enjoyable. but problems like this are just like dream-murmuring ... sigh...

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

### Re: solved

Maniac wrote: - print all non-zero input numbers in their original order
- but if all input numbers are zero, print just one zero
If you skip the zeroes, you are printing a sub sequence.
If you print more than one number, you break the rule which says that a sequence should have just ONE number (hhuehuehue)
If you print one zero instead of all zeroes you are printing a sub sequence.

I believe that there is no solution, therefore everyone who DID NOT submit should get AC?

I was going to try to trim all left and right side zeroes, and the print the remaining subsequence. Then it would be the smallest subsequence which preserves the order of the elements and wont skip any numbers (zeroes). That wouldnt be the same as Erics solution and wouldnt get ac...

Unfortunately I woke up too late for trying it...

Guilherme Silveira

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland
I only provided you guys with a solution, I didn't make the problem statement! I totally agree that this problem couldn't have been much more ill-stated.

Technobug, I actually tried your suggested solution and it indeed gave WA as you predicted.

EriK (<- note the K)

P.S. Does anyone know why so many people tend to write my name in the wrong way when there's no reason to assume I mistyped my own name in previous messages?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
While we have it, let's have a mindreading contest! First to read Manzoor's mind wins!

I have to say, the contestants that did solve F must have known that Manzoor doesn't actually follow his contest descriptions..