... Which would give the correct answer if each production block of toys
could only match up with one production block of boxes and vice versa.
However, a case like
4 x 1, 4 x 3, 4 x 1, 4 x 3, 4 x 1, 4 x 3, 4 x 1, 4 x 3, 4 x 1
5 x 1, 5 x 2, 5 x 1, 5 x 2, 5 x 1, 5 x 2, 5 x 1
(for which the solution is obviously 20) shows that you may want to combine
a given block with blocks arbitrarily far back.
The solution which I used (which takes time O(K^4) where there are K
blocks, but with a small constant) is:
Let f[i,j] be the Longest Common Subsequence of
Block[A,1]Block[A,2]...Block[A,i] and Block[B,1]Block[B,2]...Block[B,j].
Then f[i,0] = f[0,j] = 0 for all i,j.
Further if i,j>0 and Block[A,i] and Block[B,j] are made up of different
elements, then f[i,j] = max(f[i-1,j],f[i,j-1])
Finally, if i,j>0 and Block[A,i] and Block[B,j] are made up of the same
element (e), then
f[i,j] = max(f[i-1,j],f[i,j-1],
max(f[i',j']+min( # of e's in
Block[A,i'+1]Block[A,i'+2]....Block[A,i], # of e's in
Block[B,j'+1]Block[B,j'+2]...Block[B,j] ): Block[A,i'+1] and Block[B,j'+1]
are made of e's ) )
Here is my code:
http://ideone.com/0QS8B
On 9 May 2012 08:56, "Satyajit Bhadange" <[email protected]>
wrote:
> Thank Luke, Atleast i know the Algorithm to solve the problem.
>
> I implemented the solution and it gives correct answer for small cases,
> but failed for memory error for large data.
>
> I tried to implement the algorithm that you have given at the end and
> played with it to get correct answers...but stuck again...no idea on how to
> move ahead.
>
> On Wed, May 9, 2012 at 12:17 PM, Luke Pebody <[email protected]>wrote:
>
>> Problem C is the Longest Common Subsequence problem. It has a well known
>> easy to understand solution:
>>
>> Let A1A2...An and B1B2...Bm be two sequences. Define f(i,j) for 0<=i<=n
>> and 0<=j<=m to be the length of the longest common subsequence of A1...Ai
>> and B1...Bj (A1...A0 is the empty sequence, which has longest common
>> subsequence of length 0 with everything). Then f(0,j)=f(i,0). For all
>> positive I and j with Ai not equal to Bj, f(i,j) is the maximum of f(i-1,j)
>> and f(i,j-1). On the other hand if Ai is equal to Bj, f(i,j) is the maximum
>> of f(i-1,j), f(i,j-1) and f(i-1,j-1)+1.
>>
>> You can therefore compute all of the f's in time and space O(nm).
>>
>> However, here, n and m can be 10^18, so this method would be too slow and
>> take up too much memory.
>>
>> What we need to do is find a way of dealing with 1 block at a time,
>> rather than 1 element at a time.
>>
>> An easy, but wrong, thing to do is to set
>> f(0,j)=0
>> f(i,0)=0
>> f(i,j)=max(f(i-1,j),f(i,j-1)) if block Ai and Bj are made of different
>> elements
>> f(i,j)=max(f(i-1,j),f(i,j-1),f(i-1,j-1)+min(length of block Ai,length of
>> block Bj) if block Ai and Bj are made of the same element.
>>
>> ... To be continued.
>> On 9 May 2012 07:01, "Satyajit Bhadange" <[email protected]>
>> wrote:
>>
>>> Problem C ?
>>>
>>> On Wed, May 9, 2012 at 11:15 AM, Luke Pebody <[email protected]>wrote:
>>>
>>>> Problem A:
>>>>
>>>> Performing a Depth First Search or Breadth First Search for each
>>>> vertex, stopping once you have a repetition takes time at most O(N^2).
>>>> Quicker ways exist.
>>>>
>>>> Problem B:
>>>>
>>>> Let us suppose there exists any method of getting you to your home (at
>>>> distance D) at time T, and let us suppose that at time t you are at
>>>> position x(t). Then D must be at most aT^2/2. Suppose that y(t) is where
>>>> you would be if you waited for time T-sqrt(2D/a) and then just accelerated
>>>> at full acceleration until you reached home.
>>>>
>>>> Then you can show y(t) <= x(t) for all t and y(t)=D. Thus, since x(t)
>>>> doesn't bump into the car, nor does y(t).
>>>>
>>>> So there is an optimal solution that just waits at the start for a
>>>> while, and then accelerates full throttle.
>>>>
>>>> Each given location of the other car (before your house) and the time
>>>> it takes the other car to reach your house, all give you lower bounds on
>>>> how long you must wait. Wait the longest of those.
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Google Code Jam" group.
>>>> To post to this group, send email to [email protected].
>>>> To unsubscribe from this group, send email to
>>>> [email protected].
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/google-code?hl=en.
>>>>
>>>>
>>>
>>>
>>> --
>>>
>>> Thanks & Regards,
>>> *Satyajit Bhadange
>>> Software Programmer*
>>>
>>> *Problems & Solutions* <http://www.satyajit-algorithms.com>
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Google Code Jam" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> For more options, visit this group at
>>> http://groups.google.com/group/google-code?hl=en.
>>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Google Code Jam" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/google-code?hl=en.
>>
>
>
>
> --
>
> Thanks & Regards,
> *Satyajit Bhadange
> Software Programmer*
>
> *Problems & Solutions* <http://www.satyajit-algorithms.com>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Google Code Jam" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/google-code?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
