Hi Luke, I am following you until the easy but wrong solution. I think i am understanding why it is wrong. (because if A and B matches but are not of the same quantities there are still some elements (toys or boxes) that could be matched)
I cannot understand the last and more important formula : 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 ) ) Could you please explain further? @Satyajit How could you implement the solution for the small subset? If you use "single element" LCS you have complexity O(nm) like luke said. How could you solve test case #4? On 9 Mag, 19:20, Luke Pebody <[email protected]> wrote: > ... 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.
