Joseph, That's not the DP approach. That's the smarter-than-DP approach as described in the analysis page.
On Mon, Apr 16, 2018, 11:31 Joseph DeVincentis <[email protected]> wrote: > 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 <[email protected] > > 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 [email protected]. >> To post to this group, send email to [email protected]. >> 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 [email protected]. > To post to this group, send email to [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/CAMAzhzharAkByV%3D3Z1dw0AWLtM08A9CkUh%3DVXOjrZEDV2Hz8sA%40mail.gmail.com > <https://groups.google.com/d/msgid/google-code/CAMAzhzharAkByV%3D3Z1dw0AWLtM08A9CkUh%3DVXOjrZEDV2Hz8sA%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > 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 [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CANrP2_N_mY0CTozzj7Z7_1BBvC4gT_qM_-e9bVEVnKZXBxU1xA%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
