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

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

Post by Krzysztof Duleba » Sun Aug 08, 2004 12:13 am

zubair - if it's so than I'm sorry for this. I have to admit that I was wrong.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Re: faster algorithm?

Post by Per » Sun Aug 08, 2004 3:03 pm

Maniac wrote: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?
I did a DP solution with memoization which is roughly n^2 * k, but it's independent of the number of test cases (since answers can be reused). It took 1.1 secs, would have been a bit too slow for AC in the original contest, but it would probably be fast enough if the computations are done bottom-up instead of with memoization.

The table I used was simply a two-dimensional array indexed by n and k. Tell me if you want a bigger hint than that. :)

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

Post by Maniac » Sun Aug 08, 2004 5:27 pm

Thanks, I tried the solution you suggested and got AC in 1.203s with a bottom-up implementation. So I think it isn't much better than the solution with memorization.

Isn't 1 sec a little on the low side for a time limit then? Prefactors really start to make the difference between AC and TLE in this case, which in my humble opinion should always be avoided...

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

Post by Krzysztof Duleba » Sun Aug 08, 2004 10:48 pm

I used almost the same algorithm as Per and got AC during the contest. My solution was running for 1.082 s, so time limit in the problem statement was inaccurate.

natalya
New poster
Posts: 3
Joined: Sun Aug 15, 2004 7:55 am

Post by natalya » Fri Aug 27, 2004 3:36 pm

hi,

i'm still curious with sample input #4, n=5, k=0? how to get 22?
thanks.

-natalya-
Go Natalya!

breezechan
New poster
Posts: 4
Joined: Sun Aug 29, 2004 3:46 pm

Post by breezechan » Mon Aug 30, 2004 3:16 am

first eat #2, then eat #4

#1 : 2
#2 : 2
#3 : 2+4
#4 : 2+4
#5 : 2+4

the sum is 22.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Tue Feb 07, 2006 8:58 pm

Hi all!
I think that I don't understand the problem, albuit I understand the four first cases I can't understand the fifth one n=10 k=20 give as result 605.
Can anyone explain me it?
Thanks in advance!

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Sun Jun 03, 2007 10:47 pm

hmm...that's a big case... :-P

It's too hard to explain with human.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sun Jun 03, 2007 10:56 pm

OK. But maybe, could you explain me the problem?
Any hint that you may think that it is important, or whatever to understand the problem, or the method to solve it, ...

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Sun Jun 03, 2007 11:06 pm

Wow, it has been a while (1 year+?) and you're still keep tap on this, that's great!

Well, from my understanding, you have a bunch of apples of weight k+1...k+n.

Now, you want to eat some apples in order and identify the sweet apple (exaclt one of that). Any apple with less weight than the sweet one is bitter and any apple with more weight is sour, as a result, suppose your apples have weight in the range [i,j], if you eat some apple of weight x, i<=x<=j, then you will know (1) the weet apple is x and you found it, (2) apple x is bitter and the actual sweet apple is thus in range [x+1,j], (3) apple x is sour and the actual sweet apple is in range[i,x-1].

The problem with the problem statement is you don't know where the apple is exactly, and that's not what we're after. You want a cost function that is the sum of all the cost considering all possible locations of the sweet apple. So, basically you need to come up with a decision tree of eating apples such that if apple A k+1<=A<=k+n is the sweet apple, that decision tree will give you cost(A), and you want the decision tree such that Sum(cost(x), x=k+1..k+n) is minimized.


Heh, I think this is even more confusing then the problem statement...lol

So, basically in general you have a bunch of apples with weight in the range [i,j], and you eat some apple x. You then need to calculate the cost of eat x given range[i,j], and split the problem into [i,x-1] and [x+1,j].

This is a typical type of DP where you store a range (i,j) of your problem.

Similar problems are: Matrix Chain Multiplication, Minimum Perimeter Triangulation, Bitonic TSP, Cutting Stick (some problem in vol 1), and a lot of others.

Learn this and you can get +50 in problems solved :D

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Mon Jun 04, 2007 5:44 pm

Thanks ;). I understood the problem and I solved it. Although a bit slow, around 5 secs. I used a recursive method with memoization. And to pass the time limit I used a dirty tricky :-? Although I am not proud of that, I have passed it and I have learnt something else about DP. A good problem for that :)

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Re: 10688 - The Poor Giant

Post by yiuyuho » Mon Mar 01, 2010 5:41 pm

Is there a way to prevent those spams? :evil: :x

forthright48
New poster
Posts: 37
Joined: Wed Mar 14, 2012 11:57 am
Location: Bangladesh
Contact:

Re: 10688 - The Poor Giant

Post by forthright48 » Sat May 03, 2014 1:51 pm

Seems like the problem statement has not been fixed yet. I was so confused seeing this:
1+3+3+3=13
I kept on checking my code over and over again, until I realized, the equation is just plain wrong. 1+3+3+3 = 10, not 14. Can't believe it took me so long to see the arithmetic error :lol:
What ever happens, happens for good. Even when we get WA :p
http://www.forthright48.com

Post Reply

Return to “Volume 106 (10600-10699)”