As I solved this problem, I noted that the range of dimensions for the
cookies was limited to 1 to 250. This interval is less than sqrt(2)^16, and
I realized it meant that if you keep track of the intervals, merging them
as they overlap, you will never have too many different intervals.

Start with a single interval, [P,P] where P is the sum of the perimeters of
all uncut cookies.
Now process the cookies in turn, from smallest to largest.
Suppose your smallest cookie is 1x1. Then you end up with two intervals,
[P,P] and [P+2,P+2sqrt(2)].
Now if the next cookie has min(W,H) < sqrt(2) (that is, since the
dimensions are integers, if it has either dimension 1), then the range it
creates will overlap with this one. So it if was 1x2, then you would have a
range [P+2,P+2sqrt(5)] which overlaps with the previous one completely,
eliminating it, and a new range [P+4,P+2sqrt(2)+2sqrt(5)], which also
overlaps since 4 < 2sqrt(5), so after this step you only have [P,P] and
[P+2,P+2sqrt(2)+sqrt(5)].

It is possible for the number of intervals to grow if the cookie sizes are
more different. For instance, if the second-smallest cookie was 2x2, then
you'd get an interval of [P+4, P+4sqrt(2)] from it, as well as [P+6,
P+6sqrt(2)] when both offsets are applied. 4sqrt(2) is about 5.66 so none
of these intervals overlap, and we have 4 intervals for the next cookie.

However, if you want to keep your intervals from crashing with these, the
next cookie's smaller dimension must be at least 3sqrt(2), and since they
are integers, it must be at least 5. Even so, if it is 5, and you add the
interval [P+10, P+10sqrt(2)], when you add the other intervals when this
cut and some of the others are made, the [P+12, P+12sqrt(2)] and [P+14,
P+14sqrt(2)] crash with the P+10 interval, and those crash with the [P+16,
P+16sqrt(2)] interval, so we have actually only added one more interval
[P+10,P+16sqrt(2)] in this step.

For your next cookie to not stomp on the intervals you have already made,
the next cookie has to have minimum dimension larger than 8sqrt(2), or as
an integer at least 12. And this again makes a new interval which does not
overlap the 5 existing ones, but the other intervals it makes when it
combines with the other existing intervals will all overlap, so you'll get
one new interval [P+24, P+40sqrt(2)].

Because the other intervals are quite close together compared with the size
of the new interval we are adding, this will happen no matter how large we
make the next interval. If we instead add more small intervals, we will
quickly fill in the gaps between the intervals and just have one large
interval. And because we can only grow to 250 times the size of the
smallest cookie, we can only do a few of these steps, each of which more
than doubles the size of the previous cookie, before we reach the size of
the largest allowed cookie.

In my example, the next cookie size that will not overlap with the existing
intervals is 29x29, making an interval [P+58, P+98sqrt(2)]. The next is 70,
making an interval [P+140, P+238sqrt(2)]. The next is 169, making an
interval [P+338, P+576sqrt(2)]. And the next required size is too large. As
a result, you never actually have more than 9 intervals! It doesn't matter
that you can have 100 different-sized cookies, because you will only ever
have a handful of separate reachable intervals of perimeter, and you can
maintain the list of these intervals until one of them includes the
solution - at which point you stop and give the exact desired perimeter as
your solution - or none of them ever does, and when you get through the
whole list you can report the maximum of the largest interval less than the
goal.

This is exactly what my solution does, keeping track of a list of intervals
of accessible perimeters after adding a cut in each cookie to the possible
solutions, inserting the new interval properly in the list (after the
interval which starts before it), checking to see if it overlaps the
previous interval and any number of following intervals, and merging all
such overlapping intervals into one new one. Because the list of intervals
actually never exceeds length 9, you don't even need to program a binary
search to efficiently find the right place to insert each new interval.
You'll be inserting fewer than 900 intervals in a list that, due to
merging, never gets longer than 9, and you can traverse the whole list of
intervals each time looking for the right insertion point.




On Sat, Apr 14, 2018 at 2:51 PM, Artem Voronin <artemvoronin1...@gmail.com>
wrote:

> Hey,
>
> Can someone clarify this description of dp approach?
>
> "For each cookie, we are deciding whether to leave it as is, or cut it,
> which adds L to our total perimeter and gives us up to R - L units of
> additional "slack". Once we have finished deciding which cookies to cut, we
> can include as much or as little of this "slack" as we want. All other
> things being equal, having more slack is always better for us."
>
> What is the state of dp here ?
> if it's (remaning_p, index, slack) then how to deal with fact that slack
> has double type and it seems it can have exponential number of different
> values?
> if it's (remaning_p, index) then it seems we need to iterate in range [0;
> R - L] inside each state as we can't be greedy and use R-L value only for
> example.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Google Code Jam" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to google-code+unsubscr...@googlegroups.com.
> To post to this group, send email to google-code@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/
> msgid/google-code/3becee14-154f-4646-87e8-61697359cdd7%40googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/CAMAzhzharAkByV%3D3Z1dw0AWLtM08A9CkUh%3DVXOjrZEDV2Hz8sA%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.

Reply via email to