Yes, it's actually a little more complicated that 11x11. Five cells on the right edge of that 11x11 square do not need to be recomputed because squares whose bottom-right corners are in one of those 5 cells come lexicographically earlier than the 6x6 square we are removing. I thought it would just cause more confusion if I explained all of these details. Recomputing a 12x12 square does not hurt and is easy to explain. But if you want to be more precise, then you can recompute the 11x11 square whose middle cell is (i, j). That works, too.
igor On Sun, May 23, 2010 at 11:09 AM, Seabiscuit <[email protected]> wrote: > Shouldn't the region to examine after cutting a 6x6 board be 11x11, > rather than 12x12? In fact, a 12x12 board has no center. > > I just want to be sure that I understand the solution correctly. I'm > going to code it up myself. Very interesting DP structure. > > -- > You received this message because you are subscribed to the Google Groups > "google-codejam" 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-codejam" 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.
