660A - Взаимнопростый массив
The problem was suggested by Ali Ibrahim C137.
Note that we should insert some number between any adjacent not co-prime elements. On other hand we always can insert the number 1.
Complexity: O(nlogn).
660B - Рассадка в автобусе
The problem was suggested by Srikanth Bhat bharsi.
In this problem you should simply do what was written in the problem statement. There are no tricks.
Complexity: O(n).
660C - Сложный процесс
The problem was suggested by Mohammad Amin Raeisi Smaug.
Let's call the segment [l, r] good if it contains no more than k zeroes. Note if segment [l, r] is good than the segment [l + 1, r] is also good. So we can use the method of two pointers: the first pointer is l and the second is r. Let's iterate over l from the left to the right and move r while we can (to do that we should simply maintain the number of zeroes in the current segment).
Complexity: O(n).
660D - Количество параллелограммов
The problem was suggested by Sadegh Mahdavi smahdavi4.
It's known that the diagonals of a parallelogram split each other in the middle. Let's iterate over the pairs of points a, b and consider the middle of the segment 
: 
. Let's calculate the value cntc for each middle. cntc is the number of segments a, b with the middle c. Easy to see that the answer is 
.
Complexity: O(n2logn).
660E - Различные подмножества по всем кортежам
The problem was suggested by Lewin Gan Lewin.
Let's consider some subsequence with the length k > 0 (the empty subsequences we will count separately by adding the valye mn at the end) and count the number of sequences that contains it. We should do that accurately to not count the same sequence multiple times. Let x1, x2, ..., xk be the fixed subsequence. In the original sequence before the element x1 can be some other elements, but none of them can be equal to x1 (because we want to count the subsequence exactly one time). So we have m - 1 variants for each of the elements before x1. Similarly between elements x1 and x2 can be other elements and we have k - 1 choices for each of them. And so on. After the element xk can be some elements (suppose there are j such elements) with no additional constraints (so we have m choices for each of them). We fixed the number of elements at the end j, so we should distribute n - k - j numbers between numbers before x1, between x1 and x2, \ldots, between xk - 1 and xk. Easy to see that we have 
choices to do that (it's simply binomial coefficient with allowed repititions). The number of sequences x1, x2, ..., xk equals to mk. So the answer is 
. Easy to transform the last sum to the sum 
. Note the last inner sum can be calculating using the formula for parallel summing: 
. So the answer equals to 
. Also we can get the closed formula for the last sum to get logarithmic solution, but it is not required in the problem.
Complexity: O((n + m)log MOD), где MOD = 109 + 7.
660F - Медведь и боулинг 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.
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.
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?
Complexity: O(nlog2n).
