### 660A - Co-prime Array

The problem was suggested by Ali Ibrahim New_Horizons.

Note that we should insert some number between any adjacent not co-prime elements. On other hand we always can insert the number 1.

**С++ solution**

Complexity: *O*(*nlogn*).

### 660B - Seating On Bus

The problem was suggested by Srikanth Bhat srikkbhat.

In this problem you should simply do what was written in the problem statement. There are no tricks.

**C++ solution**

Complexity: *O*(*n*).

### 660C - Hard Process

The problem was suggested by Mohammad Amin Raeisi aminra.

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).

**C++ solution**

Complexity: *O*(*n*).

### 660D - Number of Parallelograms

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 *cnt*_{c} for each middle. *cnt*_{c} is the number of segments *a*, *b* with the middle *c*. Easy to see that the answer is .

**C++ solution**

Complexity: *O*(*n*^{2}*logn*).

### 660E - Different Subsets For All Tuples

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 *m*^{n} 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 *x*_{1}, *x*_{2}, ..., *x*_{k} be the fixed subsequence. In the original sequence before the element *x*_{1} can be some other elements, but none of them can be equal to *x*_{1} (because we want to count the subsequence exactly one time). So we have *m* - 1 variants for each of the elements before *x*_{1}. Similarly between elements *x*_{1} and *x*_{2} can be other elements and we have *m* - 1 choices for each of them. And so on. After the element *x*_{k} 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 *x*_{1}, between *x*_{1} and *x*_{2}, \ldots, between *x*_{k - 1} and *x*_{k}. Easy to see that we have choices to do that (it's simply binomial coefficient with allowed repititions). The number of sequences *x*_{1}, *x*_{2}, ..., *x*_{k} equals to *m*^{k}. 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.

**C++ solution**

Complexity: *O*((*n* + *m*)*log* *MOD*), где *MOD* = 10^{9} + 7.

### 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 *a*_{L}·*x*_{R} + *b*_{L} where *a*_{L} and *b*_{L} depend on *L*, and *x*_{R} depends on *R* only.

For each *L* we should find a linear function *f*_{L}(*x*) = *a*_{L}·*x* + *b*_{L} where *a*_{L}, *b*_{L} 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 *x*_{R} and *const*_{R} to fit equation ( * ) again. With value of *x*_{R} we can iterate over functions *f*_{L} to find the one maximizing value of *b*_{L} + *a*_{L}·*x*_{R}. And (still for fixed *R*) we should add *const*_{R} 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 *f*_{L} 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*(*n*^{2}). 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 (*x*_{R}, *const*_{R}) and then use the two pointers method — check the implementation in my solution below. It gives complexity because we sort by *x*_{R} 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 *x*_{R}. 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*(*nlog*^{2}*n*).

We don't need divide and conquer in F. We can use only convex hull trick. This way the solution has better complexity and is easier to implement.

Let's say that S1 is a normal prefix sum array, that is S1[i]=A[1]+A[2]+...+A[i] and S2 is again a prefix sum array but this time every element is multiplied by its index, that is S2[i]=A[1]+2*A[2]+3*A[3]+...+i*A[i]. Let's choose some R which will be the right end of our chosen interval. Now we are looking for the L that minimizes S2[R]-S2[L-1]-(L-1)*(S1[R]-S1[L-1]) which is a standard use of CHT — http://codeforces.com/contest/660/submission/17245184.

The complexity is O(NlogN).

Nice! And is it possible to implement it with integers only?

Ah yes, since we need to compare A1/B1 and A2/B2 where A1, B1, A2 and B2 are integers. Thanks if you asked to make me think about it, I will know that in future! :)

But I think your

Bmay be up toN^{2}·10^{7}andAis up toN·10^{7}so long long's won't be enough to multiply them. So maybe the intended solution was valuable anyway because it allowed to use integers only.Oh yeah, they are too big, sorry. But don't think that I want to say it's not valuable, of course it is.

In a previous educational round we've learnt how to compare fractions of long longs in integers http://codeforces.com/blog/entry/21588?#comment-262867

sum_so_far can be

N* 10^{7}score_so_far can be

N^{2}* 10^{7}When we will calculate f.a*f.b it can be

N^{3}* 10^{7}, which is bigger than 10^{22}.Am I missing something?

f.ais up toNandf.bis up toN^{2}·10^{7}but we don't multiply some random values. Values off.aincrease by 1 and values off.bincrease byN·10^{7}, as we move fromf_{i}tof_{i + 1}(and we multiply differences likef1.a-f2.a). I came up with a proof that it amortizes but I don't see that proof right now. I will try to get it again (and I hope it exists).sorry

My approach for

`Problem F`

is as follow (It didn't work, but I can't find the bug in this algorithm):We can determine the stop point (deleted suffix) by looping back from

`n`

to`1`

:then I implemented this for loop to get the best stop point for every

`i`

:So now

will be the deleted suffix for item`go[i]+1`

--->`n`

`i`

.I think if this part of code works , I think this problem can be solved in

`O(n)`

Complexity, And if it doesn't work, my approach will fail entirely.So, what is wrong with my code?

In C problem, why complexity

O(n+k)? even ifk>nit will beO(n).Well technically you are right.

Anyway considering the fact, that (by the statement) K<=N, then O(n+k) == O(n) (the complexities are equal)

So → you are right, but so is Edvard (at least in asymptote) ^_^

But I agree that it might be slightly misleading, considering, that the "k" really does not have to be used for counting of the complexity :)

Thanks. Fixed.

For D, another interpretation is to count pairs (dx, dy) for all pairs of points and then for each such pair add to answer

count* (count- 1) / 2. Since the parallel sides are parallel and has same length. But we will count each parallelogram twice, so divide the answer by 2.It's just a building vectors on each parallelogram's side, isn't it?

an easier aproach and easy to implement is to find miidle of each line then use the fact that in every parallogram diagonals intersect at the middle.

It will be not working if more than 3 points can lie on the same line. For example, {(2,2),(4,4),(-2,-2),(-4,-4)} is not a parallelogram. Yes, I know, following by problem statement it`s impossible, but the fact remains.

exactly as you say!

Build vectors, merge them (count number of same vectors) and use Gauss's formula!

^_^

How can you solve Problem E?

I could not understand the editorial. Can someone please explain?

Out of A,B,C,D guess which one I found the hardest? That's right! A. FML ;_;

There is another method of solving B with sorting. Some people might find it easier and shorter to code

17235532

For Problem F you can just make a form of slope such that (p[j] — p[k]) / (j — k) <= s[i], where p[i] = i * sigma(a[i]) — sigma(i * a[i]), s[i] = sigma(a[i]). then you can make a convex hull, for each i, you just to use binary search to find the best choice and update the answer. this complexity is O(nlogn)

for E ,in 5th line ,there should be m - 1 choices for each of them but not k-1 choices.

Thanks. Fixed.

Here's just a funny story I want to tell you guys.

I solved problem F by a weird O(N) algorithm, which is not correct.

http://codeforces.com/contest/660/submission/17264773 (Accepted)

Maybe test cases are weak, so my solution passed 52/54 tests (failed on 2 tests, I had to write "if n=... cout..." in order to AC). Seem crazy right ?

An O(n) alternative for E:

This is more direct from the statement of the problem. We build the set of all sequences, element by element, from left to right, and

`current`

tracks the count of distinct subsequences within all the sequences (visualise a different room for each sequence maybe). At each step for each room we create`m`

new rooms. Also, in each room, each subsequence splits into two: one with the newly added element, and one without. Except we have just created some subsequences that were already there; all of them, in fact (except the empty ones), so we subtract them (the number of empty ones is`powr`

, which is`m**i`

).Seems to work: 17242031.

It seems I forgot how to solve recurrences. But Wolfram Alpha hasn't. Edit: for some reason that link doesn't work. Here it is: https://www.wolframalpha.com/input/?i=solve+recurrence+a%5Bi%5D+%3D+a%5Bi-1%5D*K+%2B+M%5E%28i-1%29

So there's a O(lg (n+m+MOD)) solution. Logarithmic time means we can solve it in Python!

Complete solution:

Apparently it works: 17273456

Hey,this may be a bit naive question but please can you explain how the answer for n=2 & m=2 for this problem is 14.

There are 4 sequences and in each we need to count unique subsequences:

00: [], [0], [0,0]

01: [], [0], [1], [0,1]

10: [], [0], [1], [1,0]

11: [], [1], [1,1]

That's 3+4+4+3.

For B, you say "There are no tricks." What about 17246985?

Check my solution as suggested in tags

binary search, dp(pre calculation)17283567

Can u explain how to solve it using binary search and dp?

I don't understand why the problem D is complexity O(n^2*logn), I know that the n^2 is there because we have to compare every segment with every other segment but I don't understand why the log(n).

The

log(n) comes up from the complexity of the data structure needed to handlecnt, such as a C++ map. Note that you need to count how many times a point appears as a middle point.Okey, thank you!

I didnt understand the samples in the question for E, could someone help me out here?

Can someone elaborate on the following from problem E's editorial?

I think the test cases of 660C - Сложный процесс are weak. There is a similar problem 676C - Вася и строка. I tried my accepted submission 49270641 of 660C - Сложный процесс for 676C - Вася и строка but it got WA on test 12 49757559.

The closed formula being referred to in problem E is:

$$$ans = m^n + \frac{m}{m-1}((2m-1)^n - m^n)$$$.

It doesn't work when $$$m = 1$$$ (because of division by 0). But in that case, since there is only a single sequence of length $$$n$$$ comprising of all $$$1$$$-s, the answer is simply $$$(n + 1)$$$.