10688 - The Poor Giant

[zubair]

can any body explain this

If he eats apple #1, then he east total weight of 1, 3, 3, 3 when apple #1, #2, #3 and #4 are sweet respectively.

if #3 and #4 is sweet the the total weight eaten by him should be 6 and 6 respectively..

but its 3 and 3 according to the problem...
The sample input is also wrong (

3
2 0
3 0
4 0
5 0
10 20

Case 1: 2
Case 2: 6
Case 3: 13
Case 4: 22
Case 5: 605

[Faizur]

During the contest it was one of the hottest problem. But unfortunately i can't understand the prroblem description well.
In the question there is a line like:

On a table, there are n apples, the i-th apple has the weight k+i(1<=i<=n).

On another line

For examples, n=3, k=0, the apples are of weight 1, 2, 3, 4.

According to the previous statement here n shoud be 4 not 3.
Again if he eat #1 first then the example shows he eats total weight 1,3,3,3. But as i understand the problem i think it should be 1,3,6,6.
I think i misunderstood the problem because plenty of solved the problem during the contest hours.
Can someone explain me the question .
____________________________
Regards
Faizur

[Krzysztof Duleba]

Why do you think that the problem is wrong? You just can't understand it and it's not the same.

if 1 is sweet - 1
if 1 is bitter, go for 3
if 3 is sweet - 1 + 3
if 3 is bitter, 4 is the sweet one, and giant has eaten 1 + 3
if 3 is sour, 2 is the sweet one, and giant has eaten 1 + 3

The sum is 13.

[Krzysztof Duleba]

It seems that you are right with the first remark. I didn't read the problem careful enough to notice it - I just made a function on the basis of example.

I answered your second question in the other thread.

[abishek]

the problem description and the sample input was wrong during the contest.
but then most of it was inferable!
thats why many solved it i supos
bye
abi

[little joey]

Why do you think that the problem is wrong? You just can't understand it and it's not the same.

Don't be so blunt, please. The problem description contains (at least) three stupid errors, which makes it quite hard to understand.

For examples, n=3, k=0, the apples are of weight 1, 2, 3, 4.

makes no sense; n should be 4.

If he eats apple #1, then he east total weight of 1, 3, 3, 3 when apple #1, #2, #3 and #4 are sweet respectively. This yields a solution of 1+3+3+3=13, beating 14.

The numbers are wrong and there is not enough explanation. It should read someting like: "If he eats apple #1 and then, if it's bitter, apple #3, the total weight is 1+4+4+4=13, beating 14."

The first line of input contains a single integer t(1<=t<=100), the number of test cases.
...
Sample Input
3
2 0
3 0
4 0
5 0
10 20

Sample Output
Case 1: 2
Case 2: 6
Case 3: 13
Case 4: 22
Case 5: 605

I guess you can spot the error.

Looks like the problemsetter was in great hurry to finish the description in time. He is a great problemsetter. I think his companion 'Elites' should have saved him for this blunders. (But who am I to judge. I never set a decent problem...)

[Krzysztof Duleba]

Don't be so blunt, please.

I just don't like when people are trying to find the reason of their failure everywhere but in themselves. What's blunt in that? And what blunt is supposed to mean (except "thick marijuana cigarette")?

Quite a lot of people solved this problem during the contest (including me), so it can't be that bad as you say.

I didn't notice wrong value of n in the statement and the fact that it was different in the sample input. You're right there.

[little joey]

You can look up the meaning of that word in a dictionary http://www.webster-dictionary.org/definition/blunt for example.

Zubair just asked if someone could explain the example and then pointed to the fact that the sample input was wrong. Perfectly alright, IMO. Then telling him (or her, I don't know) "You just can't understand it" is saying he's too stupid to understand, and that's what I call blunt (or crude, or insensitive, whatever you like). I just would like that people respect each other on this board, even if they are less perfect than oneself.

[Larry]

Don't be so blunt, please.

I just don't like when people are trying to find the reason of their failure everywhere but in themselves. What's blunt in that? And what blunt is supposed to mean (except "thick marijuana cigarette")?

Quite a lot of people solved this problem during the contest (including me), so it can't be that bad as you say.

I didn't notice wrong value of n in the statement and the fact that it was different in the sample input. You're right there.

Just because a lot of people solve it during the contest doesn't mean the problem isn't bad. (Anyone remember "Maximum Sum II"?)

The forum should be used to help people understand better, and if you're unhappy with that, then you should just ignore it. If it is indeed trivial and clear to you, then, I apologize as a lesser mind.

If you meant to flame, then.. I'll stop right there..

[Krzysztof Duleba]

Just because a lot of people solve it during the contest doesn't mean the problem isn't bad.

I agree that there are some mistakes that makes it harder to understand. But hey, if people were able to solve it, then one should think twice before calling the problem wrong.

The forum should be used to help people understand better, and if you're unhappy with that, then you should just ignore it.

What made you to think so? I like helping others. Read my other posts if you don't believe. Read again what I wrote and what started this discussion:

Why do you think that the problem is wrong? You just can't understand it and it's not the same.

Well, am I wrong? For me the statement was clear enough, for number of other coders too.

If you meant to flame, then.. I'll stop right there..

Again, I don't know what made you to think so. But I agree that this thread seams to lead to nowhere, if that's what you mean.

[Maniac]

Hi all,

I've solved this problem with C++ using DP and my algorithm is of order n^3. My solution took about 5 seconds, but I see a lot of much faster solutions. Can anyone hint me about a faster solution?

Thanks, Erik

PS
- Java programmers beware, exactly the same algorithm in Java will give TLE
- I was also surprised to see that the same DP algorithm, but with memorization, in C++ gave TLE as well...

[Larry]

Not everyone can read the problemsetter's mind. Mistakes are there, and they impede understanding.

A great problem is one where everyone can understand it, not necessarily solve it. A broken clock is right twice a day, it doesn't matter that people solve it. There shouldn't be any guesswork.

It's easy for anyone to make a mistake, both for the programmer and the problemsetter, it is imperative that there is a check and balance of sort..

[windows2k]

[quote="Maniac"]Hi all,

I've solved this problem with C++ using DP and my algorithm is of order n^3. My solution took about 5 seconds, but I see a lot of much faster solutions. Can anyone hint me about a faster solution?
[quote]
Hello, I don't think any good idea about DP.
Could someone give me some hints? Thx

[Maniac]

I could give you some hints on my DP solution, although it's not the fastest one probably....

[zubair]

to Krzysztof Duleba i didn't say that the problem is wrong
i told that the sample input was not correct.i think u misunderstood
me. i asked for an explanation of that problem as i could
not understand the problem.....
but thnx for ur help any way.....

and many many thnx to little joey,Larry for their exclusive help and support..