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.
