I actually considered a dynamic programming type of approach very briefly during the competition, but discarded my half-formed idea when I realized just tracking the intervals would be possible.
The badly written analysis (which perhaps glosses over this idea because they consider it an inferior solution) suggests it is similar to the knapsack problem, and gives a Wikipedia link. The knapsack problem is how to maximize value if you have a set of items with various values and weights and you have a limit on the weight you can carry. I think the analogy here is that for each cookie, the minimum added perimeter for cutting it (L in the analysis) is the weight, and the difference between maximum and minimum added perimeter (R-L or "slack" in the analysis) is the value. We'll optimize the slack for each value of the minimum added perimeter, and in doing so, either find an exact solution, or find the solution (using the full value of the slack at one of these weights) which is closest. Note that it is the 0/1 knapsack problem which applies (since we can only cut each cookie once), so the DP approach would need to consider one cookie at a time and compute the best slack at each weight using cookies up to the currently considered one. This means that you would have to copy values for each possible weight up to the limit when iterating for each cookie. Since P can go up to 10^8, this is a lot of copying, but that is an excessive value. We can at most get 1000+500sqrt(2) from each cookie or 170710 from 100 maximum-sized cookies, and a maximum possible weight as I've defined it (when adding all cookies) of 500*100=50000. This is a lot easier to copy potentially 100 times! The code for this approach should consider the possibility that the desired perimeter is larger than the minimum perimeter when cutting all cookies, and skip ahead to that condition when it is, rather than suffering through a lot of calculations for nothing. You can also write code to handle this data sparsely, so you only store, say, three values where the possible slack changes, and use a function which scans the list for the appropriate value. So if your cookies are 1x1, 1x3, 3x3, and 5x12, so the minimum perimeter added when cutting them (weight) is 2, 2, 6, and 10 respectively, and the slack is 2sqrt(2)-2, 2sqrt(1)-2, 6sqrt(2)-6, and 16. Define m(w,i) as the maximum slack available when considering the first i cookies and up to w "weight". Then you'd have: m(any,0)=0 m(0,any)=0 m(2,1)=2sqrt(10)-2 [Cutting the 1x3 cookie first provides more slack] m(2,2)=2sqrt(10)-2 m(4,2)=2sqrt(2)+2sqrt(10)-4 m(2,3)=2sqrt(10)-2 m(4,3)=2sqrt(2)+2sqrt(10)-4 m(6,3)=6sqrt(2)-6 m(8,3)=6sqrt(2)+2sqrt(10)-8 m(10,3)=8sqrt(2)+2sqrt(10)-10 m(x,4)=m(x,3) for x<10 m(10,4)=16 [Cutting the 5x12 cookie provides more slack than cutting all the others] m(x,4)=16+m(x-10,3) for x>10 Then you need to check the maximum perimeter (weight + slack + the perimeter we started with) for each weight up to the allowed limit and either return the target perimeter, if we can reach it, or return the maximum otherwise. Having worked this out, I can say it is definitely an inferior solution to the other one, but using the other one relies on having the insight that you won't get exponentially many intervals as the number of cookies grows. If you do not see that, you are likely to try the dynamic programming method. On Tue, Apr 17, 2018 at 1:47 AM, Artem Voronin <[email protected]> wrote: > Hey /dev/joe/ > > Thanks for your explanation it's by magnitude better than one in analyses. > > But there are two approaches mentioned in analyses: > 1) "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". ..." > 2) "However, the problem can also be solved in a different way. As in the > previous solution, each cookie corresponds to a range [L, R] by which we > can increase the total perimeter if we decide to cut that cookie. Let S(K) > be the list of intervals we can reach after processing the first K cookies. > We start with S(0) = {[0, 0]}. .." > > you explained the second one (again thx for explaining it in more > details), but I initially interested in first approach, as I really have > zero ideas/understanding how to use DP (they mentioned knapsack, so this > must be some DP definitely). > > So if someone can explain or give a hint (like what is the state) for DP > approach it would be very nice too. > > -- > 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/7ea2f3f4-690e-47e1-a5ef-fc282dc93423%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/CAMAzhzicwV7STW8oeX0NJVsZGyebeBKR0bFr1GPLwMo-3pfn_A%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
