**Div-2. 124A - The number of positions**

Let's iterate through the each item and check whether it is appropriate to the conditions

The author's solution

*a*≤*i*- 1 and*n*-*i*≤*b*(for*i*from 1 to*n*). The first condition can be converted into*a*+ 1 ≤*i*, and the condition*n*-*i*≤*b*in*n*-*b*≤*i*, then the general condition can be written*max*(*a*+ 1,*n*-*b*) ≤*i*and then our answer can be calculated by the formula*n*-*max*(*a*+ 1,*n*-*b*) + 1.The author's solution

Div-2. 124B - Permutations

Div-2. 124B - Permutations

Let's try all possible ways to rearrange digits in the numbers and check the difference between maximum and minimum number.

The author's solution

The author's solution

Div-1. 123A - Prime Permutation

Div-2. 124C - Prime Permutation

Div-1. 123A - Prime Permutation

Div-2. 124C - Prime Permutation

All positions except the first and those whose number is a prime greater |

Let's find the symbol which occurs the most and try to place the symbol on the position in which the characters have to be equal. If this symbol for all positions is not enough then the answer will be "NO", otherwise arrange the remaining characters by any way at other positions.

The author's solution

*s*| / 2 have to have the same symbol. Remaining positions can have any symbol. Consider positions that should be the same for*p*= 2 is 2,4,6,8 ... Now let's take a position with the number*x*≤ |*s*| / 2, this position should have the same character as the position of 2 as the symbol*x*must be equal to the character at position 2 **x*, which is equal to the character at position 2. Now consider the position whose number is more than |*s*| / 2. If this position is not a prime then there is a prime number*p*to divide the number at our positions and*p*≤ |*s*| / 2. So character at position*p*is equal the character at position 2 and so a symbol at our position is also consistent to the character at position 2. The remaining positions are not combined with any other positions so it does not matter which symbol is situated here.Let's find the symbol which occurs the most and try to place the symbol on the position in which the characters have to be equal. If this symbol for all positions is not enough then the answer will be "NO", otherwise arrange the remaining characters by any way at other positions.

The author's solution

Div-1. 123B - Squares

Div-1. 123B - Squares

**Div-2. 124D - Squares**

Let's turn the field on 45

Let's transform the coordinates of the initial and final cells as described rule above. Then find sectors which contain our cells and calculate answer with formula above.

The author's solution

^{o}transforming cells coordinates (*x*,*y*) in (*x*+*y*,*x*-*y*). Then the cell (*x*,*y*) will be bad if one of the conditions occurs*x*≡ 0 (*mod*2*a*) or*y*≡ 0 (*mod*2*b*). So good cells will be divided into sectors by vertical and horizontal lines. For each sector, it is possible to determine the coordinates of a pair of numbers, the first number that will rise during the transition to the next right sector, and the second pair number will increase during the transition to the next upper sector. From the sector with coordinates (*x*,*y*) can go to any nearby on the side of the sector, visiting at least one bad cell, ie in (*x*- 1,*y*), (*x*+ 1,*y*), (*x*,*y*- 1) and (*x*,*y*+ 1). Since the numbers 2*a*and 2*b*have the same parity, then from the sector (*x*,*y*) can also go to the sector on the diagonal, and visiting a bad cell, ie in (*x*- 1,*y*+ 1), (*x*+ 1,*y*- 1), (*x*- 1,*y*- 1) and (*x*+ 1,*y*+ 1). Then it turns out that the minimum number of bad cells, which should be visited on the way out of from the sector (*x*1,*y*1) to sector of (*x*2,*y*2) equals*max*(|*x*1 -*x*2|, |*y*1 -*y*2|).Let's transform the coordinates of the initial and final cells as described rule above. Then find sectors which contain our cells and calculate answer with formula above.

The author's solution

Div-1. 123C - Brackets

Div-1. 123C - Brackets

**Div-2. 124E - Brackets**

Let's reduce the problem to a one-dimensional matrix. Consider a monotonous path (1, 1), (1, 2), ..., (1,

Let's iterate through the positions, starting with the highest priority. Let's put in this position the bracket "(" and consider how many ways can complete the remaining brackets to get the correct bracket sequence. If the number of ways of not less than

The author's solution

*m*- 1), (1,*m*), (2,*m*), ..., (*n*- 1,*m*), (*n*,*m*) which has correct bracket sequence. Now, in this way a cell (1,*m*) can be replaced on (2,*m*- 1) and still be a monotonous way and will form the correct sequence of the bracket. So in the cells of (1,*m*) and (2,*m*- 1) is one type of bracket. Proceeding further (eg to replace (1,*m*- 1) on (2,*m*- 2) or (2,*m*) on (3,*m*- 1)) can be seen that in cells (*i*,*j*) and (*i*- 1,*j*+ 1) is one type of bracket. Then we get not two-dimensional array*n*×*m*, a one-dimensional size*n*+*m*- 1. For each position can be determined what her highest priority, ie for cell*i*(1 ≤*i*≤*n*+*m*- 1), the priority will be equal to the minimum value of*p*_{x, y}where 1 ≤*x*≤*n*, 1 ≤*y*≤*m*and*x*+*y*- 1 =*i*.Let's iterate through the positions, starting with the highest priority. Let's put in this position the bracket "(" and consider how many ways can complete the remaining brackets to get the correct bracket sequence. If the number of ways of not less than

*k*, then leave in this position "(", or reduce the*k*on the number of ways and put in this positions bracket ")". And so let's iterate through all items. In order to calculate the number of ways each time dynamics is calculated on two parameters*f*_{i, j}, where*i*is the number of processed positions, and*j*is the number of opened brackets. If the position of*i*+ 1 bracket is not defined yet then you can go to*f*_{i + 1, j + 1}or*f*_{i + 1, j - 1}, if defined then only*f*_{i + 1, j + 1}or only*f*_{i + 1, j - 1}, depending on opening or closing bracket respectively.The author's solution

Div-1. 123D - String

Div-1. 123D - String

Sort all suffixes of the string (denoted by an array of strings

The author's solution

*c*_{i}). Then the answer to the problem is the amount of 1 ≤*i*≤*j*≤ |*s*| and 1 ≤*k*, that the prefixes of length*k*in all*c*_{i..j}are equal. Options when*i*=*j*, and 1 ≤*k*≤ |*c*_{i}| can calculate at once, it is the number of substrings in the string, ie |*s*| * (|*s*| + 1) / 2. Now let's count the LCP (longest common prefix) for adjacent suffixes, ie*a*_{i}=*LCP*(*c*_{i},*c*_{i + 1}) for 1 ≤*i*< |*s*|. Then let's count the number of 1 ≤*i*≤*j*< |*s*| and 1 ≤*k*, that*k*≤*min*(*a*_{i..j}). This task is to count the number of rectangles if there is a limit to the height of each column, ie*a*_{i}the maximum height of the rectangle in the column*i*. Solve by a stack or list.The author's solution

Div-1. 123E - Maze

Div-1. 123E - Maze

Consider what is the expected value for a given entrance and exit vertexes. It is clear that there will be only one path from the entrance to the exit, which in any case will be passed. Also, you can still go in the wrong direction. Consider the case when the chosen vertex from which there is

Let's run dfs and consider of the vertex as exit vertex. Then, if in some subtree defined entrance, the expected value equal to the size of the subtree. Calculate how much of each subtree is the number of entrance and calculate the number of moves, if the exit is in the current vertex. It is necessary not to forget to count cases where the current vertex is an exit and entrance is higher in the tree traversal.

The author's solution

*k*false paths and one right (it is always). Then before going in the right direction it can be 2^{k}equiprobable way around false paths. Every false way occurs the 2^{k - 1}ways and to increase the number of moves in 2 × <*amount**of**vertexes**in**false**subtree*> ie expectation of a false path to increase by 2 × <*amount**of**vertexes**in**false**subtree*> × 2^{k - 1}/ 2^{k}= <*amount**of**vertexes**in**false**subtree*> . Then expectation in vertex is equal to sum of <*amount**of**vertexes**in**false**subtrees*> + 1 (a move in the right direction) + expectation of the vertex if to go the right direction. The result is that the expected value equal to the number of edges reachable from the entrance, without passing through the exit.Let's run dfs and consider of the vertex as exit vertex. Then, if in some subtree defined entrance, the expected value equal to the size of the subtree. Calculate how much of each subtree is the number of entrance and calculate the number of moves, if the exit is in the current vertex. It is necessary not to forget to count cases where the current vertex is an exit and entrance is higher in the tree traversal.

The author's solution

LCP(c_{i},c_{i + 1}) quickly? Some solutions use a binary search for that part, I don't understand why it works that way.I used Suffix Automaton to solve this problem. & I think Suffix Automaton is very much easier than implementing Suffix array here.

Can you please tell what is the intuition behind suffix automaton & how it will be used to solve D here ? Any help will be appreciated.

I've solved the A with min(n — a, b + 1)

sir can you give me the reason please

Maths are not my strongest point, so I can't provide a mathematical explanation.

My logic is (was):

If there are at least A people in front of me, I am sure that I would never be on any of those positions. So, I'll be in some position between the last one of them and the end of the queue. This leaves me in a range of N — A positions, at most.

If I have, at most, B people between me and the end of the queue, I'll be in a position in the range b — 1 (just ahead of the first person of the B group) to the end of the queue. This is a range of B + 1 positions, at most (as from the statement "not more than B", means that may be less than that quantity).

So, if we put together those two requirements ("N — A positions, at most") and ("B + 1 positions, at most"), we have to get the lowest of the two values (based on the "at most" part on both of them. This means taking the min function of both.

The result comes from min(n — a, b + 1)

Hope my explanation is clean enough and it helps you understand my approach.

Happy coding!

thank you very much

Thank you so much for the explanation Darkmaster

Can we solve Div2-B with faster algorithm ?

I think yes.

so how !?

Did not quite understand how "max(a + 1, n - b) ≤ i and then our answer can be calculated by the formula n - max(a + 1, n - b) + 1." takes place. Would anyone like to explain the +1 part?

igreater than orequaltomax(a+ 1,n-b).In A the problem text says that "...and no more than b people standing behind him."

So, there are 0 up to b people behind him. Not more, but maybe zero. If it is zero people behind him, then literaly no position get occupied by them. So b can and must be simply ignored.

Is it a translation error?

I see you have accepted the task. Still have a question?

I think I understood.

The sentence "...and no more than b people standing behind him." implies that at least a given numer of people are standing in front of him. So b cannot be ignored.

Since this is the key observation it would have helped to state that in the tutorial text. Thanks anyway.

i am getting Unable to parse markup error ? wtf ?

Fixed. Thanks MikeMirzayanov.

Can someone explain the solution of problem D squares in more details ? I can't figure out the rotation and the sectors in the editorial.

Pretty old problem but I solved it recently.

In A, we can just find the min of n-a and b+1, right? aropan Here is the submission for the same.Solution

How does it make sense? Care to elaborate?

According to the problem statement, there are at least (a) people in front of him and at most (b) people behind him.

Note: It's possible to have no people behind him at all, in that situation the position he can occupy is equal to (n-a) This works fine if (b) is exactly before (a) Formally (a+b = n)

But what if that is not the case (a+b!=n) :

According to the statement, His pos should be exactly after b, as people in front of him can be more than (a) which is not the case with b (people behind him must equal to (b) or less) so you can use min(n-a, b+1)