10656 - Maximum Sum (II)

Cosmin.ro · Post by **Cosmin.ro** » Sat May 22, 2004 4:37 pm

What the heck does it mean? The wording of the problem is so bad ...

technobug · Post by **technobug** » Sat May 22, 2004 4:42 pm

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 · Post by **Cosmin.ro** » Sat May 22, 2004 4:47 pm

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 · Post by **UFP2161** » Sat May 22, 2004 4:51 pm

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 · Post by **Cosmin.ro** » Sat May 22, 2004 4:58 pm

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 · Post by **Maniac** » Sat May 22, 2004 5:06 pm

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 · Post by **UFP2161** » Sat May 22, 2004 5:16 pm

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?

Cosmin.ro · Post by **Cosmin.ro** » Sat May 22, 2004 5:17 pm

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 · Post by **Maniac** » Sat May 22, 2004 5:30 pm

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 · Post by **Dumitru** » Sat May 22, 2004 5:36 pm

What type of incompetent description was it at problem F ???

UFP2161 · Post by **UFP2161** » Sat May 22, 2004 5:43 pm

Maniac: Then, doesn't that violate the second sentence in the problem:

Note that I am asking for a sequence, not sub sequence.

nealzane · Post by **nealzane** » Sat May 22, 2004 5:46 pm

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 · Post by **technobug** » Sat May 22, 2004 6:08 pm

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 · Post by **Maniac** » Sat May 22, 2004 6:18 pm

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 · Post by **Larry** » Sat May 22, 2004 6:46 pm

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

OJ Board

10656 - Maximum Sum (II)

22.05.04 Contest Problem F, 10656

solved

Re: solved