Hi Codeforces,

We are happy to announce a London meet-up on July 13!

My friend Nadya (from Luna Park) asked me about any competitive programming/math alumni events here in London, and it seemed there weren't any. So we decided we should probably host one ourselves, asked a bunch of friends to come, and now it's happening!

This is by all means an informal meeting — just a picnic in a park to meet both new people and old friends and talk about stuff.

So yess, chances are you may find out that the people you met at ICPC finals a million years ago are living in London too! Or just discuss AI, burnout, taxes and whatever you will feel like discussing and eat some strawberries.

The date is 13th of July, the location will be revealed soon. Here’s the registration link, and we will share a group chat link later.

And feel free to share this post with your friends — here, on Linkedin or on Telegram!

Sorry for my poor English. If you find a mistake, write me a private message, I'll fix it. Some problems have not been translated yet, now you can try to read the Russian version of editorial with Google Translate.

408A - Line to Cashier

In this problem you were to find waiting the time for every queue by summing up the purchases of all the people, and return the minimum.

408B - Garland

In this problem it is necessary to find the garland with the maximal length, which can be composed of elements that we have.
First, if you need some color, but you don't have it, then the answer is -1
Otherwise, answer is always exists.
Let's sum the answers for all the colors separately.
Suppose we have a pieces of a garland of some color, and we need b pieces. Then we have to add min(a, b) to the answer: if a >  = b we will use b 1 meter pieces, in the other case if a < b we will use all a pieces.

407A - Triangle

In this problem you have to locate the right triangle with cathetuses a, b on a plane with its vertices in integer points.
If the required layout exists, then cathetus a always can be represented as a vector with integer coordinates A{x;y}, and a² = x² + y². Iterate over all possible x (1 ≤ x ≤ a - 1), check, that y = sqrt(a² - x²) is integer.
Vector, ortogonal to vector {x;y}, is { - y;x}. Take vector B{ - y / g;x / g}, where g = gcd(x, y). The triangle can be located on the plane if and only if b % |B| = 0, where |B| — length of vector B. The candidate for the answer — triangle (0;0)(x;y)( - y / g * b / |B|;x / g * b / |B|), but don't forget about checking that the hypotenuse isn't parallel to coordinate axes.

407B - Long Path

In this problem you had to simulate route of character in graph.
Note that if you are in vertice i, then edges in all vertices with numbers less than i are turned to p_i. It gives us opportunity to see a recurrence formula: let dp_i be number of steps, needed to get from vertice 1 to vertice i, if all edges are rotated back, into p_i. Then dp_i + 1 = 2dp_i + 2 - dp_pi. Answer will be dp_n + 1.

BONUS: Can you solve this task without statement p_i ≤ i? I don't know the solution, it seems difficult.

407C - Curious Array

In this problem you had to find how to add binomial coefficients in array offline.
Let's see, how problem changes due to increasing k from small to big values.

1) All queries have K = 0
Every time you add 1 on subsegment.
For solve this task you can add 1 at some array b[] in b[L] 1, then substract 1 from b[R+1], and after doing all queries make array a[] as array of prefix sums of array b[].

2) All queries have K = 1
Arithmetic progression 1 2 3 4 ... is added on subsegment
For solve this task you can add 1 at some array c[] in c[L] 1, then substract 1 from c[R+1], and after doing all queries make array b[] as array of prefix sums of array c[]. Actually you added 1 1 ... 1 on every subsegment at each query. If you will substract (R — L + 1) from c[R+1], and make array a[] as array of prefix sums of array b[], then it will be an answer: 1 1 ... 1 became 1 2 3 ... (R-L+1).

3) K is arbitrary
Summaring previous results one can see that if we will do

1. a[K+1][L] += 1
2. a[j][R+1] -= C(k + 1 — j + r — l, k + 1 — j) for all 1 <= j <= K + 1

and after that do a[i][j] = a[i][j-1] + a[i+1][j] (making a[i] as array of prefix sums array a[i+1]), a[0] will be the answer.
What is C(k + 1 — j + r — l, k + 1 — j)? This number is need for each query affect only on segment L..R, and you can see, why is it so, in Pascal's Triangle.

If this explanation is not clear for you, you can try to see other participants solutions (for example, Xellos's one).

407D - Largest Submatrix 3

In this task you have to find largest by area submatrix, consisting from different numbers.
Let's see solutions from slow to fast.

1) Solution by O(n⁶):
Iterate through two opposite vertices submatrix-answer and check that all numbers are different.

2) Solution by O(n⁴):
Let's fix Up and Down borders submatrix-answer (O(n²)).
Use two pointers method to iterate Left and Right borders: while in submatrix there are no equal numbers, increment Right, while there are equal numbers — increment Left. Every check — (O(n)), increments — (O(n)).

3) Solution by O(n³logn): Let's construct function maxR(Left) (let's consider that Up <= Down are fixed): maximal value Right, so that in submatrix (Up, Down, Left, Right) there is no equals numbers. You can see that maxR(i) <= maxR(i + 1) is true for every i.
How values of this function changes by shift Down to Down-1? Every value maxR(Left) can only be the same (if segment(Down, Down, Left, maxR(Left)) only added new numbers), or it can decrease.
When maxR(Left) is decreasing? Only when one of the numbers from added segment have already been in the current submatrix.
Shift Down to down let's see all numbers in row Down. For each number (let it be in column j) find indices i and k so i <= j, there is number, equal to a[Down][j] between rows Up and Down-1, i — maximal; k >= j, there is number, equal to a[Down][j] between rows Up and Down-1, k — minimal. When you find these indices (it is easy to find them using set, when you store all columns where number x was between Up and Down for all numbers x), you can try to update maxR[i] with j — 1, maxR[j] with k — 1. It will be enough, if you also update for all i = m..1 maxR[i] = min(maxR[i], maxR[i + 1]). Now maxR(Left) is correct, and you can check answer for these Up and Down by O(n).

4) Now, solution by O(n³). It requires understanding previous solution.
Previous solution, despite good asymptotics, requires to store a lot (about 160 000) sets, where you will store about 160 000 elements. Even at n = 200 it works very slow.
Let's get rid of log. Set is using only for finding nearest left and right elements, which are in rows from Up to Down, and equal to current.
Note that when you do Up = Up — 1, nearest element comes near (by column) to a[i][j], so we can find all numbers, for which the nearest element will be in new row Up, and update them nearest number, and do that in O(n²).
This solution uses O(n²) memory and O(n³) time.

BONUS: Can you solve this task faster than O(n³)? I spend a lot of time and I didn't come to any solution, but I can't show that there is not solution faster.

407E - k-d-sequence

In this problem you have to find longest subsegment, satisfying the condition.

Reduce problem to d = 1.

If d = 0, then answer is longest subsegment from equal numbers, this case we solve separately.

If d ≠ 0, then notice that if on some subsegment there are two numbers a_i, a_j so that a_i%d ≠ a_j%d, then this segment can't be good.
Divide the sequence to consequent subsegments numbers, equal by modulo d, and divide each number by d, and solve task separately with every segment, consider that d = 1.

Notice that segment [L, R] is good if and only if when max(L, R) — min(L, R) — (R — L) <= k, and there are no equal numbers. It is easy to exlain: if there are no equal numbers, then max(L, R) — min(L, R) — (R — L) is exactly number of numbers is needed to add for segment to consist of all numbers from min(L, R) to max(L, R).

For all L lets find such maxR[L], that on segment [L..maxR[l]] there are no equal numbers, and maxR[L] is maximal. It can be done by O(nlogn) by many ways, for example you can use map.

Let's learn how we can maintain array a[R] = max(L, R) — min(L, R) — (R — L). If we have such array, then we have to find rightmost R such that a[R] <= k to get an answer.

We will need two stacks and segment tree with operations "Add number on segment", "Find min element on segment", "Find rightmost number doesn't exceed k".
Let's iterate L from right to left (n downto 1). How does function max(L, R) look like with fixed L? It's values represent a set of segments so that maximum on the segment is leftmost element of segment, and these maximums are increasing. (example: for array 6 4 8 0 7 9 function max(1, R) will be 6 6 8 8 8 9). How function changes with shift L to left? Some segments are absorbed by new element, if new element is bigger than maximum on segment. Maximums on segments are increasing, so we can keep them all in stack, and when we need to add new element we have to only pop some segments from stacks while maximum on top of stack is less then new element, and push new segment after that. If every operation with stack will be accompanied with right operation with segment tree, we can store array a[R] = max(L, R). For get array a[R] = max(L, R) — min(L, R) we need only to maintain second similar stack. For get array a[R] = max(L, R) — min(L, R) we need add -1 on all suffix when we are shitfing L.

Now query "Find fightmost number less of equal k". First, segment tree divides segment of request to log(n) segments with length powers of two. Let's choose rightmost segment with minimum <= k, and do iterative deeping there to find element that we need.

So, for every L we get query on segment L..maxR(L) on rightmost number less or equal k. It is one of candidates to an answer.
We are doing O(n) operation with stack, and every requires query to segment tree, so asymptotics is O(nlogn).

Hello everyone!

This Sunday, on March 30 at 11:00 MSK (March 30 at 07:00 UTC), Codeforces Round #239 for both divisions participants will take place. Note the unusual time of the round.

The problems have been prepared by me. I want to thank Codeforces team: tasks coordinator Gerald Agapov (Gerald) for invaluable contribution to the preparation of tasks and Maria Belova (Delinur), who has translated the problems. Also thank to Niyaz Nigmatullin (niyaznigmatul) for testing.

I wish you all good luck and have a good weekend!

UPD: You can see score distribution at the problems page.

UPD2: You can find editorial here.

Problem A:

Note that the k-th element is copied to the end. Then the (k+1)-th element from the initial sequence is copied, then (k+2)-th, … , n-th, k-th, (k+1)-th, etc. So all the numbers on the blackboard will become equal if and only if all the numbers from the k-th to the n-th in the initial sequence were equal. It's now also obvious that the number of operations needed for it is equal to the index of the last number that is not equal to the n-th element of the initial sequence, because it's exactly the number of deletions needed to eliminate the elements that are not equal to the last one. If this number is greater than k, than answer is -1. Complexity — O(n).

Problem B:

Let’s store the order of the rows and columns of table. Thus, row[x] is the number of the row x in the initial table and column[x] is the number of column x in the initial table. Then, the value of an element in the row x and column y in the current table is equal to t[row[x], column[y]], where t — initial table. When we get the update request, we need to swap the x-th element and the y-th element in the corresponding array. Complexity — O(n * m + k).

Problem C:

Let's factorize the numerator and denominator. Now for each prime integer x we know the extent of x in the factorization of the numerator(a[x]) and the denominator(b[x]). For each prime number x we can calculate the extent of x in the factorization of the numerator and the denominator after reduction : newa[x]=a[x]-min(a[x], b[x]), newb[x]=b[x]-min(a[x],b[x]). We have the numerator and the denominator of the answer in factorized form. Now we have to bring them into the form which is required in the condition. One of the ways to do it is to note that the fraction from the statement satisfies the conditions. We can factorize it again and in the answer we will have the same fraction for which there will not be such a prime x so that the degree of x in answer would be greater than newa[x] or newb[x]. (This operation can be called reduction) The result will satisfy the condition and the fraction will be equal to the required number. If you try to build answer greedily (put factors in the answer till their product <= 10^7), the count of numbers in the answer (n_out or m_out) will be bigger than 10^5. Factorization by O(sqrt(max)) received TL. You should have found a faster way. For example you could have used linear sieve of Eratosthenes. Complexity — O(max + n * log(max)). log(max) is size of factorization.

Problem D:

First of all, note that in any case the best place which Vasya can take is the first place for he can earn maximum points. Now we must find the worst place which Vasya can take. We need to find maximal matching in bipartite graph, where the edge between vertice i from the first part and vertice j from the second part exists if a[i] + b[j] >= x. To solve this task, it is enough just to sort the vertices in both parts of the graph by their weights and use two pointers method. Suppose that we have sorted all the vertices by non-increasing points (a1 >= a2 >= ... >= an). Let's take two pointers — L = 1 in the first part and R = N in the second part. While a[L] + b[R] < x we must decrease R to find the first vertice such a[L] + b[R] >= x. When we found such R, we must add this edge to the answer, i.e. increase the answer, increase L by 1, decrease R by 1. It is easy to show why this algo is correct and it finds the optimal solution. I have discovered a truly marvelous proof of this, but the margins of this analysis are too narrow to for him. Complexity — O(N log N) for sorting and O(N) for two pointers.

Problem E:

1) Solution with complexity O(n*m*m), using the dynamic programming: State — d[n][m] — the number of allowed chains of length n that ends in symbol m. Transition — sort out all possible characters, and check if you can put the symbol k after symbol m.

2) Solution with complexity O(m*m*m*log n): Note that the transition in the first solution is always the same. So we can make the transition matrix A of size MxM. If j-th symbol can follow i-th then A[i][j]=1 else A[i][j]=0. Define a vector of size 1хМ b={1,1,…,1}. We can see that b * a^(n-1) = answer. Now we can use fast exponentiation for computing a^(n-1). We should consider the case with n=1 separately. The answer is the sum of numbers in the vector ans. Complexity — O(m^3) from matrix multiplication and O(log n) from fast exponentiation.

Hello everybody!

Today, Codeforces Round #137 for the Second Division Participants will take place. As usual, all other interested persons can take part in it.

The problems have been developed by a group of authors from Vladivostok: Ilya Zban (izban), Alexey Evsyukov (aevsyukov), Zakhar Voit (zakharvoit).

Gerald Agapov (Gerald) has greatly contributed as well and we thank him for it. The translation of the problems has been done by Maria Belova (Delinur) — thanks to her! We are also grateful to Pavel Kunyavskiy (PavelKunyavskiy), who has help us in the preparation of the contest.

We hope you will have fun and like this round. The points distribution will be standard (500 — 1000 — 1500 — 2000 — 2500).

Good luck to everybody!

UPD: The start will be 15 minutes later due to technical reasons, we apologize.

UPD2: Congratulation to winners!

In second division:

1: zxl0714

2: resodo

3: mugurelionut

4: hmspmy077

5: CCC

6: white_rich_beautiful

7: loveSakura

8: gcwtft827

9: yuxingdubai

10: b821213

In first division:

1: navi

2: Shik

3: SteamTurbine

UPD3: The editorial is published.