Let me introduce an editorial to Codeforces Beta Round #13. If you have any questions or propositions - feel free to post them in the comments.

**Problem A.**

It is sufficient to iterate over all bases from 2 to A-2 and find the sum of digits in them. Then one should find the greatest common divisor of found sum and A-2 (which is equal to number of bases in which we found the sums). The numerator of the answer is equal to founded sum divided by this GCD and the denominator is equal to A-2 divided by this GCD.

The complexity is O(A).

**Problem B.**

This problem appeared to be quite unpleasant to code, but all what one need to do is to check whether all three statements are true. It is recommended to perform all computations using integer arithmetics and to use scalar and vector product instead of computing cosines of angles or angles itself.

**Problem C.**

Note, that there exists a non-decreasing sequence, which can be obtained from the given sequence using minimal number of moves and in which all elements are equal to some element from the initial sequence (i.e. which consists only from the numbers from the initial sequence).

Suppose {a

_{i}} is the initial sequence, {b_{i}} is the same sequence, but in which all elements are distinct and they are sorted from smallest to greatest. Let f(i,j) be the minimal number of moves required to obtain the sequence in which the first i elements are non-decreasing and i-th element is at most b_{j}. In that case the answer to the problem will be equals to f(n,k), where n is the length of {a_{i}} and k is the length of {b_{i}}. We will compute f(i,j) using the following recurrences:f(1,1)=|a

_{1}-b_{1}|f(1,j)=min{|a

_{1}-b_{j}|,f(1,j-1)}, j>1f(i,1)=|a

_{i}-b_{1}|+f(i-1,1), i>1f(i,j)=min{f(i,j-1),f(i-1,j)+|a

_{i}-b_{j}|}, i>1, j>1The complexity is O(N

^{2}). To avoid memory limit one should note that to compute f(i,*) you only need to know f(i-1,*) and the part of i-th row which is already computed.**Problem D.**

We will solve the problem using the following algorithm:

- Fix some red point.
- Find the number of triangles with vertices in the red points which don't contain any blue points inside and which have the fixed red point as one of the vertices.
- Remove the fixed red point and go back to statement 1, if there remain any red point.

The first and third statements are obvious, so the main part of the solution is statement 2.

Suppose the red point A is fixed (in the first statement). Also suppose we have all other points which are still not removed (blue and red together) sorted by angle around the point A. We will iterate over all red points B, which will be the second vertice of triangle. Now, we need to find the number of triangles with vertices in red points which have points A and B as two vertices and which don't contain any blue point inside.

To solve this problem we will iterate over all unremoved points C in the increasing order of angle ABC starting from the point after the point B (in the same order). To avoid double counting we will stop when the angle between vectors AB and AC become greater than 180 degrees or when we reach the point which was already considered. Then we will perform such actions:

- If C is red then we will check whether there are blue points inside triangle ABC and if not - we will increase the answer by 1. Note, that to perform this check we don't need to iterate over all blue points. It is sufficient to maintain such point D from the ones which we have already seen for which the angle ABD is the smallest possible. If D doesn't lies inside the triangle ABC, then there is no blue point which lies inside it.
- If C is blue, then we will compare the angle ABC with ABD and if ABC is smaller, we will replace old D with C.

Note, that after choosing new B we consider that there is no point D and there will be no blue points inside triangles ABC until we reach the first blue point.

The complexity is O(N

^{2}(N+M)).**Problem E.**

Let's divide all row into blocks of length K=sqrt(N) of consecutive holes. If N is not a complete square, then we will take K=sqrt(N) rounded down. For each hole we will maintain not only it's power (let's call it power[i]), but also the number of the first hole which belongs to other block and which can be reached from the current one with sequence of jumps (let's call it next[i]). Also, for each hole we will maintain the number of jumps required to reach the hole next[i] from the current one (let's call it count[i]). We will consider that there is a fictious hole, which lies after the hole N and it belongs to it's own block.

To answer the query of the first type (when the ball is thrown) we will jump from the hole i to hole next[i] and so on, until we reach the fictious hole. Each time we will add count[i] to the answer. We will jump not more than N/K times.

To maintain the query of the seqond type (when the power of hole i is changed) we will change power[i], next[i] and count[i]. Then for each hole which belongs to the same block as i and has smaller number than i we will update next[i] and power[i] in decreasing order of number of the hole. We will perform not more than K updates.

The complexity is O(Nsqrt(N)).

There is another way to solve problem D. You can count the amount of points (

x,y) below each segment (a_{x},a_{y}) - (b_{x},b_{y}) witha_{x}≤b_{x}such thata_{x}<x≤b_{x}inO(N^{2M}) and store these values in a table. Then you can compute the result by iterating over all triangles and counting the points inside the triangle inO(1) using the values stored in this table.Can you explain the following statement? ThanksAbout Problem C.

_{i}}. If the elements with numbers i-1 and i+1 are not equal to element i, then we can move it closer to ai and the answer will decrease. So there is a block of equal elements and all of them are not equal to any of the elements of the initial sequence. Note, that we can increase all block by 1 or decrease it by 1 and one of this actions will not increase the answer, so we can move this block up or down until all its elements will be equal to some element from the initial sequence.But i think following statement is not true.Do you agree with me?

Let f(i,j) be the minimal number of moves required to obtain the sequence in which the first i elements are non-decreasing and i-th element is equal to b_{j}I think it must be like that:f(i,j) is the minimal number of moves required to obtain the sequence in which the first i elements are non-decreasing and i-th element is

at mostb_{j}.(can be equal to any of b_{k, }while k=1,2,...,j-1,j)Note that:

f(i,j)=min{

f(i,j-1),f(i-1,j)+|a_{i}-b_{j}|}, i>1, j>1.In Problem E: lets save for each hole the answer , number of jumps after ball leaves this hole and the last hole for it. Then for each query we have answer in o(1) and for each update of strength we can look the hole which will be after this hole . ((new strength)+i) and rewrite its answer to this hole and increase the first answer (number of jumps ) by 1 and second answer (last hole) will be same. This is o(M) solution . Any mistake ?

Do you really think that problem E can be that easy? After updating the strength of the hole number

Xthe answer will change not only for the holeX, but also for all holesY_{i}from whichXis reachable by 1 or more jumps. The number of such holesY_{i}isO(N).Problem C :in which all elements are equal to some element from the initial sequence

Why? to get the min step , the final sequence 's every number is same to the initial sequence?? why is this optimal? Thanks.

Well, to be more precise, we can say that there IS an optimal final sequence whose numbers are all from the original sequence, which can be proved by contradiction. Take the original sequence "3 1" for example. Although "2 2" is an optimal one whose numbers are not from the original sequence, "1 1" or "3 3" is optimal and their numbers are from the original one.

kadar not able to visualize the solution can you please help me do that ?

Can someone please give me a good link for square root decomposition.

i found various links on google but don't know which one is good and contains all details on sqrt decomposition.

https://cp-algorithms.com/data_structures/sqrt_decomposition.html

Problem E can also be solved using the Link-cut tree in .

Anyone noticed that Problem E also required

the number of the last hole the ball visited?So we'll have to jump to the block before we jump to the fictious hole and jump to the last hole before we jump to the fictious hole. So I had to add another while loop.

But it seems that the complexity is the same? Well, I'm just here to say that the type 1 query is not that easy(probably still easy for great coder,but not for this noob)

And I've got a TLE on test 13.Anyone help me?

I am also facing a similar issue, please help TLE at test case 13.

278983183

solve C

In problem E,

`but also the number of the first hole which belongs to other`

, do the number here refer to the smallest index of hole in which are residing in different segment and also could be hopped on through a series of jump ?I did E using square root decomposition (Divided the array into blocks of size sqrt(n), then for each element stored only the last index within its block after which it jumps to an element in another block or out of the array).

My O(n * sqrt(n)) solution is getting TLE on testcase 16. Can anyone help? 285297411

I'm getting a Wrong Answer (WA) on test case 3 while using Square Root Decomposition. Can anyone help me figure out why? For the problem E **** //

## include<bits/stdc++.h>

## define ll long long

## define endl "\n"

using namespace std;

vector<map<ll, pair<ll, ll>>> mp; ll flg[100005]; ll arr[100005]; ll n, k; vector<pair<ll,ll>>combi;

void findd() { ll l; cin >> l; ll val = 0; while (1) { ll com = flg[l]; val += mp[com][l].second; if (mp[com][l].first == l || com == 0) { cout << mp[com][l].first << " " << val << endl; break; } else l = mp[com][l].first; } }

void update(ll i) { ll e = combi[i].first; ll s = combi[i].second; map<ll, pair<ll, ll>> mm; for (ll j = e; j >= s; j--) { ll p = arr[j] + j; if (p > n) p = j; mm[j] = {p, 0}; if (flg[j] == flg[p]) { mm[j].second = mm[p].second + 1; mm[j].first = mm[p].first; } else mm[j].second = 1; } mp[i] = mm; }

void out() { ll i=0; for (auto v : mp) { cout<<"block "<<i<<endl;i++; for (auto p : v) { cout << p.first << " = " << p.second.first << " " << p.second.second << endl; } cout << endl; } }

int main () { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> k; for (ll i = 1; i <= n; i++) cin >> arr[i]; ll x = sqrt(n); mp.resize(x+2); ll cnt = 0; ll s = 0; pair<ll,ll>pp; for (ll i = n; i > 0; i--) { if(cnt==0)pp.first=i; cnt++; flg[i] = s; if (cnt == x || i==1) {pp.second=i;combi.push_back(pp); cnt = 0; s++; } }

} // ****