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.
