On Sun, 6 Sep 2009 20:07:47 -0700 (PDT), decor <[email protected]> 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 [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
-~----------~----~----~----~------~----~------~--~---
