10688 - The Poor Giant

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

Moderator: Board moderators

zubair
New poster
Posts: 17
Joined: Fri Apr 18, 2003 2:22 pm

10688 - The Poor Giant

Post by zubair » Wed Aug 04, 2004 8:56 am

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 :-((
:evil: :evil: :evil: :evil:

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
zubair-CUET old sailor

Faizur
New poster
Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm

10688

Post by Faizur » Wed Aug 04, 2004 9:02 am

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

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Wed Aug 04, 2004 6:12 pm

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.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Wed Aug 04, 2004 6:19 pm

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.

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

Post by abishek » Wed Aug 04, 2004 8:47 pm

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Aug 05, 2004 9:26 am

Krzysztof Duleba wrote: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...)

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Thu Aug 05, 2004 2:24 pm

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Aug 05, 2004 6:01 pm

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Aug 05, 2004 6:54 pm

Krzysztof Duleba wrote:
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..

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Thu Aug 05, 2004 9:38 pm

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
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

faster algorithm?

Post by Maniac » Fri Aug 06, 2004 11:25 am

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Fri Aug 06, 2004 3:12 pm

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
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Re: faster algorithm?

Post by windows2k » Fri Aug 06, 2004 5:00 pm

[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
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

Post by Maniac » Sat Aug 07, 2004 10:17 am

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

zubair
New poster
Posts: 17
Joined: Fri Apr 18, 2003 2:22 pm

Post by zubair » Sat Aug 07, 2004 7:52 pm

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..
zubair-CUET old sailor

Post Reply

Return to “Volume 106 (10600-10699)”