Well... I didn't read that part |S(K)| <= 2K + 1... good question.
It's not that hard anyway...
Consider the intervals [a, pa], [qa, ra], where a, p, q and r are real numbers.
From the questions (ignore the integers), you have p >= sqrt(2), and r/q >=
sqrt(2).
Considering the cases q >= sqrt(2) and q < sqrt(2), either the intervals
[a, pa], [qa, ra] have an intersection or [qa, ra], [(q+1)a, (r+p)a] have an
intersection. So the power set of that two intervals can be rewritten at most 3
intervals.
The rest of the proof can be done by mathematical induction. Mixing k+1
intervals with one extra will get 2k+2 intervals, but at least k overlaps.
P.S. I didn't manage to solve the problem or got all these during the
competition. Super bummer. Still got to round 2 with my worst performance in my
lifetime though.
On Tuesday, April 24, 2018 at 1:38:08 PM UTC, lokuvo wrote:
> 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/5faace80-c3ee-4f4d-b601-269e6ca40bff%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
