~mhb On May 9, 2012 2:48 AM, "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. > -- 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.
