Turns out that wrong proof was not too far from the correct one, which is
written down below:
Suppose we process [a, pa] on the intervals [0,0], [qa, ra]. We have p, r/q >=
sqrt(2). The resulting intervals are [0,0], [a, pa], [qa, ra], [(q+1)a, (r+p)a]
If 1 <= q <= sqrt(2) then [a, pa] and [qa, ra] has an intersection.
If q >= sqrt(2) + 1, then [qa, ra] and [(q+1)a, (r+p)a] has an intersection
because
r >= sqrt(2) * q
= q + (sqrt(2) - 1) * q
>= q + (sqrt(2) - 1) * (sqrt(2) + 1)
= q + 1
Now the induction part. Now we processed some intervals (cuts), and we have k
distinct resultant intervals. Let these intervals be [l_1, r_1], [l_2, r_2],
... [l_(k-1), r_(k-1)], 0 where l_1 >= l_2 >= ... >= l_(k-1). Note that l_i /
l_(i+1) > sqrt(2), otherwise the intervals have overlaps.
Now we process the extra interval (cut) [l, r] to get 2k intervals. Assume
l_(k-1) >= l. Since (sqrt(2) + 1) / sqrt(2) < sqrt(2), there is at most one of
the l_i can lie within the range (sqrt(2), sqrt(2) + 1), to produce intervals
without overlap. So there are at least k-2 overlaps.
And the resulting number of intervals is at most 2k - (k-2) = k+2, or at most 2
extra distinct intervals.
Finally the induction. Arrange the k intervals to be processed in descending
order of the lower bounds. Such sorting do not change the final 2^k intervals
before considering overlaps.
After processing first interval we make 2 distinct intervals. And for every
subsequent interval processed (the assumption stated in the previous paragraph
always hold because of the sorting), we have at most 2 more distinct intervals.
Hence |S(K)| <= 2K. (No +1 here, unless I made another mistake.)
--
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/1b6e030c-2084-4512-a5eb-975432ec627e%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
