On Wednesday, 25 April 2018 21:54:56 UTC+3, Wing-chung Leung wrote: > 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.)
what happens if q < 1 ? -- 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/1947dbe0-f5e0-4bfb-b6f5-cfa1480e46d8%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
