Hi. I am a participant of Code Jam 2018.
I have a question about the analysis of round 1A problem edge baking.
There already is another thread about problem 1A, but this is a different
question. (This question is not about DP)
The analysis ends with the line
"It can also be shown that |S(K)| ≤ 2K + 1. We leave this as an exercise to the
reader!"
("Let S(K) be the list of intervals we can reach after processing the first K
cookies. We start with S(0) = {[0, 0]}.")
I cannot come up with a proof.
I have been thinking about it for a few days... still I see no way of proving
it.
Would you kindly tell me the proof?
Or at least give me some hint?
Thank you in advance!
--
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/eac31430-cf45-4aaf-9b3f-bcefa5859283%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
