Editorial of Educational Codeforces Round 11

Revision en1, by Edvard, 2016-04-09 00:38:15

660F - Bear and Bowling 4

The problem was prepared by Kamil Debowski Errichto. The problem analysis is also prepared by him.

The key is to use divide and conquer. We need a recursive function f(left, right) that runs f(left, mid) and f(mid+1, right) (where mid = (left + right) / 2) and also considers all intervals going through mid. We will eventually need a convex hull of lines (linear functions) and let's see how to achieve it.

For variables L, R (, ) we will try to write the score of interval [L, R] as a linear function. It would be good to get something close to aL·xR + bL where aL and bL depend on L, and xR depends on R only.

For each L we should find a linear function fL(x) = aL·x + bL where aL, bL should fit the equation ( * ):

Now we have a set of linear functions representing all possible left endpoints L. For each right endpoint R we should find xR and constR to fit equation ( * ) again. With value of xR we can iterate over functions fL to find the one maximizing value of bL + aL·xR. And (still for fixed R) we should add constR to get the maximum possible score of interval ending in R.

Brute Force with functions

Now let's make it faster. After finding a set of linear functions fL we should build a convex hull of them (note that they're already sorted by slope). To achieve it we need something to compare 3 functions and decide whether one of them is unnecessary because it's always below one of other two functions. Note that in standard convex hull of points you also need something similar (but for 3 points). Below you can find an almost-fast-enough solution with a useful function bool is_middle_needed(f1, f2, f3). You may check that numbers calculated there do fit in long long.

Almost fast enough

Finally, one last thing is needed to make it faster than O(n2). We should use the fact that we have built a convex hull of functions (lines). For each R you should binary search optimal function. Alternatively, you can sort pairs (xR, constR) and then use the two pointers method — check the implementation in my solution below. It gives complexity because we sort by xR inside of a recursive function. I think it's possible to get rid of this by sorting prefixes in advance because it's equivalent to sorting by xR. And we should use the already known order when we run a recursive function for smaller intervals. So, I think is possible this way — anybody implemented it?

Intended solution with two pointers

Complexity: O(nlog2n).

Tags education round 11, editorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English Edvard 2016-04-10 18:47:25 66 Tiny change: ' we have $k-1$\nchoic' -> ' we have $m-1$\nchoic'
en6 English Edvard 2016-04-09 22:13:28 3481
ru7 Russian Edvard 2016-04-09 21:38:53 202
en5 English Edvard 2016-04-09 21:36:44 1097
en4 English Edvard 2016-04-09 21:31:11 1280
en3 English Edvard 2016-04-09 21:28:04 856
en2 English Edvard 2016-04-09 21:17:51 847
ru6 Russian Edvard 2016-04-09 21:09:43 50 Мелкая правка: 'ость: $O(n+k)$.\n\n###' -> 'ость: $O(n)$.\n\n###'
ru5 Russian Edvard 2016-04-09 21:07:54 56
ru4 Russian Edvard 2016-04-09 02:22:21 3780 Мелкая правка: ' log^{2}{n})$.' -
ru3 Russian Edvard 2016-04-09 01:05:26 3539 Мелкая правка: 'mits_{s=1} m^s (m-1)^(n-s) \sum_{k=0' -
en1 English Edvard 2016-04-09 00:38:15 9069 Initial revision for English translation
ru2 Russian Edvard 2016-04-09 00:33:39 1030 Мелкая правка: 'cnt_c-1)}2.\n\n 'cnt_c-1)}2$.\n\n
ru1 Russian Edvard 2016-04-09 00:03:25 2956 Первая редакция (опубликовано)