But please tell me how are u varying length? On Tue, Sep 8, 2009 at 3:08 AM, <gis...@utumno.pl> wrote:
> > On Sun, 6 Sep 2009 20:07:47 -0700 (PDT), decor <avdb...@gmail.com> wrote: > > Can anyone explain How to solve 2008 Practice Round "Square Fields" > > Problem? I m not getting even the slightest of idea of how to go about > > it?? > > Since no one replied I'll give you my solution. It's probably > overcomplicated, but that's the first thing that came to my mind and it > works ;-) > > First, observation: It's enough to consider only squares that have at least > one point on their left and top edges (possibly same point if it's a > corner). Other squares can be moved to such position without "uncovering" > any points. So each square can be described by this pair of points. > > Now let's write a function that checks if given length is enough to cover n > points with k squares. First, sort all points (top-bottom, left-right). > Then we can use recursion: > [parameters: > left - number of squares left > cover[] - which points have been covered already > ] > 0. If every point is covered return 1, if left = 0 return 0 > 1. Out of all free (not covered) points pick top one as UP > 2. For each free point as LEFT > 1. If UP and LEFT can't be covered with same square -> continue > 2. Copy cover[] to newcover[] > 3. Mark all points that are covered by square(UP, LEFT) with given > length > in newcover[] > 4. Run same function with parameters (left-1, newcover[]) > 5. Return 1 if (4) returned 1 > 3. Return 0 > > This can take a lot of time, but cover has only 2^16-1 possible states and > left has only 15 states, so we can remember results of this function, which > will give us huge speed boost. > > Now that we know how to check if given length is sufficient we can perform > simple binary search for smallest possible value (~16 runs of check for > each test case, so it's very quick). > > I'm not really good at explaining stuff like that, but I hope it helps. > > Adam > > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
