#### 1043A — Elections

**Tutorial**

We can observe that result cannot exceed 201 — Awruk gets at least 101 votes from one person and Elodreip cannot get more than 100 votes from one person. So we can iterate over every possible integer from 1 to 201 and check if Awruk wins with *k* set to this integer. We have to remember that *k* — *a*_{i} is always at least 0, so we have to check this condition too. Complexity *O*(*n* * *M*), where *M* denotes maximum possible value of *a*_{i}. Try to solve it in *O*(*n*).

#### 1043B — Lost Array

**Tutorial**

First, let's observe that we can replace array *a*_{i} with array *b*_{i} = *a*_{i} - *a*_{i - 1}, because all we care about are differences between neighboring elements. Now, we can see that our lost array can have length *d* if and only if for every *j* such that *j* + *d* ≤ *n*, *b*_{j} = *b*_{j + d}. So we can iterate over every possible *d* from 1 to *n* and check if it is correct in *O*(*n*). Complexity of whole algorithm is *O*(*n*^{2}).

#### 1043C — Smallest Word

**Tutorial**

Basically in problem we are given a word in which for every *i* we can reverse prefix of first *i* elements and we want to get the smallest lexicographically word. We will show that we can always achieve word in form *a*^{jb}^{n - j}.

Let's say that we solved our problem for prefix of length *i* and for this prefix we have word *a*^{jb}^{i - j} (at the beginning it's just empty word). If our next letter is *b* then we do nothing, because we will get word *a*^{jb}^{i - j + 1} which is still the smallest lexicographically word. Otherwise we want to reverse prefix of length *i*, add letter *a* and reverse prefix of length *i* + 1, so we get a word *a*^{j + 1}*b*^{i - j}, which is still fine for us.

There is still a problem — what if we have already reversed prefix *i* and we just said that we will reverse it second time. But instead of reversing it second time, we can deny it's first reverse.

Final complexity is *O*(*n*).

#### 1043D — Mysterious Crime

**Tutorial**

Deleting prefix and suffix is nothing more than taking a subarray. If subarray is common for all permutations then it has to appear in first permutation. We renumber all permutations such that first permutation is 1, 2, ..., *n* - 1, *n*.

Now for every *i* in every permutation we count how long is subarray starting at *i* which looks like *i*, *i* + 1, ..., *i* + *k*. It can be easily done in *O*(*n*) for one permutation with two pointers technique.

Now for every element *i* we compute reach$[i]$ equal the longest subarray starting in *i* which looks like *i*, *i* + 1, ..., *i* + *k* and it apears in all subarrays. It is just minimum over previously calculated values for all permutations.

Now we can see that our result is . Final complexity *O*(*nm*).

#### 1043E — Train Hard, Win Easy

**Tutorial**

Let's compute result if there are no edges, we can add them later. If there are no edges then result for pair (*i*, *j*) is min(*x*_{i} + *y*_{j}, *x*_{j} + *y*_{i}). First let's fix *i* for which we want to compute result. Then calculate result with all pairs *j* such that *x*_{i} + *y*_{j} ≤ *x*_{j} + *y*_{i}. After some transformations we get that *x*_{i} - *y*_{i} ≤ *x*_{j} - *y*_{j}. Similarly we have that *y*_{i} + *x*_{j} < *x*_{i} + *y*_{j} if *x*_{i} - *y*_{i} > *y*_{j} - *x*_{j}.

So let's sort over differences of *x*_{i} - *y*_{i} and compute prefix sums of *x*_{i} and suffix sums of *y*_{i}. Now we can compute for every *i* result in *O*(1). Then we can iterate over every edge (*u*, *v*) and subtract min(*x*_{u} + *y*_{v}, *x*_{v} + *y*_{u}) from result of *u* and *v*.

Complexity *O*(*nlogn*).

#### 1043F — Make It One

**Tutorial**

First let's observe that if there exists valid subset then it's size is at most 7 (because product of 7 smallest primes is bigger then 3 * 10^{5}). Let's define *dp*[*i*][*j*] — number of ways to pick *i* different elements such that their gcd is equal to *j*. We can use inclusion--exclusion principle to calculate it. Then *dp*[*i*][*j*] = — , where *cnt*_{j} denotes number of *a*_{i} such that *j* | *a*_{i}. Because for *k* > 3 * 10^{5}, *dp*[*i*][*k*] = 0 we have to check only *k* ≤ 3 * 10^{5}.

Our answer is the smallest *i* such that *dp*[*i*][1] is non-zero. Since *dp*[*i*][*j*] can be quite big we should compute it modulo some big prime.

Final complexity is *O*(*logM* * (*n* + *M*)), where M is equal to maximum of *a*_{i}.