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.
