Hello, Codeforces!

Today, 17th of October at 17:35 MSK Codeforces Round #377 for second division participants will take place. As usual, first division participants are able to participate out of rating.

The round problems are taken from the problemset of regional stage of the All-Russian school team programming olympiad which was taking place yesterday in Saratov. The problemset for onsite competition was invented and prepared by Mike MikeMirzayanov Mirzayanov, Ilya IlyaLos Los, Danil danilka.pro Sagunov, Vladimir vovuh Petrov and Roman Roms Glazov. We are thankful for pre-solving competition problems to many of Saratov State U teams' participants. One problem in the round will have a bit harder version than at the competition.

Nikolay KAN Kalinin and Tatyana Tatiana_S Semenova helped us preparing problems and translating for the round — thank you! Thanks to Mike MikeMirzayanov Mirzayanov for the Codeforces and Polygon systems.

There will be 6 problems and 2 and a half hours to solve them at the round. We wish you the best luck!

If you are a participant of the yesterday competition in Saratov, please, do not register for the round and do not participate in it, also do not discuss the problems before the round ends.

UPD Scoring: 500-1000-1500-2000-2000-2500

UPD2

Congratulations to the winners!

Div.2

1. gxgod

2. FizzyDavicl

3. dothanhlam97

4. ngkan

5. Judy.Hopps

Div.1

1. dreamoon_love_AA

2. kmjp

3. NVAL

4. eddy1021

5. pekempey

As soon as the time of registration to the round was a bit early, there may be some first division participants taking part in a line with a second division participants. There are not many of them, so (and due to technical problems) this will be left as is.

Due to NEERC subregionals in Saratov, rating will be updated tomorrow.

UPD3 Editorial

Good time of day, Codeforces!

I am glad to announce that this Sunday, 8th November at 19:30 MSK, Codeforces Round #330 for both divisions will take place.

The problemset of the round has been prepared for you with pleasure by Alex fcspartakm Frolov and me, Dan Sagunov. We want to thank the coordinator of Codeforces Gleb GlebsHP Evstropov for his valuable help in problem preparation, Mike MikeMirzayanov Mirzayanov for Codeforces and Polygon systems, Maria Delinur Belova for translating problem statements into English and Vladislav winger Isenbaev and Alex AlexFetisov Fetisov who have tested the round problemset.

Every participant will be given two hours to solve five problems. We have tried to make the round problemset variative and interesting and therefore we strongly recommend to read all the problem statements during the round. Scoring will be announced later as always.

We wish good luck and high rating to everyone!

UPD. We are sorry again for the mistake in Cdiv2/Adiv1 problem: jury's solution is working wrong in odd n case. We are hoping that other problems was (or will be such in upsolving) interesting and useful.

Anyway, let's congratulate the round winners:

First division winners:

1. jcvb
2. 2222
3. KAN

second division winners:

1. Tagrimar
2. fsps60312
3. uhateme

Editorial could be found here.

UPD. Problem Cdiv2/Adiv1 was fixed and now it has the statement and solution which jury meant it to be. Problem has been returned to the contest, so feel free to upsolve it.

Adiv2

To solve the problem one could just store two arrays hused[j] and vused[j] sized n and filled with false initially. Then process intersections one by one from 1 to n, and if for i-th intersections both hused[h_i] and vused[v_i] are false, add i to answer and set both hused[h_i] and vused[v_i] with true meaning that h_i-th horizontal and v_i-th vertical roads are now asphalted, and skip asphalting the intersection roads otherwise.

Such solution has O(n²) complexity.

Jury's solution: 13390628

Bdiv2

It is always optimal to pass all the computers in the row, starting from 1-st to n-th, then from n-th to first, then again from first to n-th, etc. and collecting the information parts as possible, while not all of them are collected.

Such way gives robot maximal use of every direction change. O(n²) solution using this approach must have been passed system tests.

Jury's solution: 13390612

Adiv1

Let the answer be a₁ ≤ a₂ ≤ ... ≤ a_n. We will use the fact that gcd(a_i, a_j) ≤ a_min(i, j).

It is true that gcd(a_n, a_n) = a_n ≥ a_i ≥ gcd(a_i, a_j) for every 1 ≤ i, j ≤ n. That means that a_n is equal to maximum element in the table. Let set a_n to maximal element in the table and delete it from table elements set. We've deleted gcd(a_n, a_n), so the set now contains all gcd(a_i, a_j), for every 1 ≤ i, j ≤ n and 1 ≤ min(i, j) ≤ n - 1.

By the last two inequalities gcd(a_i, a_j) ≤ a_min(i, j) ≤ a_n - 1 = gcd(a_n - 1, a_n - 1). As soon as set contains gcd(a_n - 1, a_n - 1), the maximum element in current element set is equal to a_n - 1. As far as we already know a_n, let's delete the gcd(a_n - 1, a_n - 1), gcd(a_n - 1, a_n), gcd(a_n, a_n - 1) from the element set. Now set contains all the gcd(a_i, a_j), for every 1 ≤ i, j ≤ n and 1 ≤ min(i, j) ≤ n - 2.

We're repeating that operation for every k from n - 2 to 1, setting a_k to maximum element in the set and deleting the gcd(a_k, a_k), gcd(a_i, a_k), gcd(a_k, a_i) for every k < i ≤ n from the set.

One could prove correctness of this algorithm by mathematical induction. For performing deleting and getting maximum element operations one could use multiset or map structure, so solution has complexity .

Jury's solution: 13390679

Bdiv1

One could calculate matrix sized n × n mt[i][j] — the length of the longest non-decreasing subsequence in array a₁, a₂, ..., a_n, starting at element, greater-or-equal to a_i and ending strictly in a_j element with j-th index.

One could prove that if we have two matrices sized n × n A[i][j] (the answer for a₁, a₂, ..., a_pn starting at element, greater-or-equal to a_i and ending strictly in a_j element with j-th index inside last block (a_{(p - 1)n + 1}, ..., a_pn) and B[i][j] (the answer for a₁, a₂, ..., a_qn ), then the multiplication of this matrices in a way

will give the same matrix but for length p + q. As soon as such multiplication is associative, next we will use fast matrix exponentiation algorithm to calculate M[i][j] (the answer for a₁, a₂, ..., a_nT) — matrix mt[i][j] raised in power T. The answer is the maximum in matrix M. Such solution has complexity .

Jury's solution (with matrices): 13390660

There's an alternative solution. As soon as a₁, a₂, ..., a_nT contains maximum n distinct elements, it's any non-decreasing subsequence has a maximum of n - 1 increasing consequtive element pairs. Using that fact, one could calculate standard longest non-decreasing subsequence dynamic programming on first n array blocks (a₁, ..., a_n²) and longest non-decreasing subsequence DP on the last n array blocks (a_{nT - n + 1}, ..., a_nT). All other T - 2n blocks between them will make subsegment of consequtive equal elements in longest non-decreasing subsequence.

So, for fixed a_i, in which longest non-decreasing subsequence of length p on first n blocks array ends, and for fixed a_j ≥ a_i, in which longest non-decreasing subsequence of length s on last n blocks array starts, we must update the answer with p + (T - 2n)count(a_i) + s, where count(x) is the number of occurences of x in a₁, ..., a_n array. This gives us solution.

Jury's solution (with suffix and prefix): 13390666

Cdiv1

Let's fix s for every (l, s) pair. One could easily prove, that if subarray contains a_i element, than a_i must be greater-or-equal than a_j for every j such that . Let's use this idea and fix g = gcd(n, s) (it must be a divisor of n). To check if a_i can be in subarray with such constraints, let's for every 0 ≤ r < g calculate

.

It's true that every good subarray must consist of and only of . For finding all such subarrays we will use two pointers approach and for every good a_i, such that is not good we will find a_j such that are good and is not good. Let has k elements . Any it's subarray is superior, so it gives us arrays of length 1, 2, ..., k with count k, k - 1, ..., 1. As soon as sum of all k is not greater than n, we could just increase counts straightforward. There's a case when all a_i are good, in which we must do another increases. Next we must add to the answer only counts of length x, such that gcd(x, n) = g.

Solution described above has complexity O(d(n)n), where d(n) is the number of divisors of n.

Jury's solution: 13390645

Ddiv1

It is a common fact that for a prime p and integer n maximum α, such that p^α|n! is calculated as , where p^w ≤ n < p^w + 1. As soon as , the maximum α for is calculated as .

One could see, that if we consider numbers n, k and n - k in p-th based numeric system, rounded-down division by p^x means dropping last x digits of its p-th based representation. As soon as k + (n - k) = n, every i-th summand in α corresponds to carry in adding k to n - k in p-th numeric system from i - 1-th to i-th digit position and is to be 0 or 1.

First, let convert A given in statement from 10 to p-th numeric system. In case, if α is greater than number of digits in A in p-th numeric system, the answer is 0. Next we will calculate dynamic programming on A p-th based representation.

dp[i][x][e][r] — the answer for prefix of length i possible equal to prefix of A representation (indicator e), x-th power of p was already calculated, and there must be carry equal to r from current to previous position. One could calculate it by bruteforcing all of p² variants of placing i-th digits in n and k according to r and e and i-th digit of A, and make a translation to next state. It can be avoided by noticing that the number of variants of placing digits is always a sum of arithmetic progression and can be calculated in O(1).

It's highly recommended to examine jury's solution with complexity O(|A|² + |A|min(|A|, α)).

Jury's solution: 13390698

Ediv1

One could prove that the number of binary functions on 4 variables is equal to 2²⁴, and can be coded by storing a 2⁴-bit binary mask, in which every bit is storing function value for corresponding variable set. It is true, that if mask_f and mask_g are correspond to functions f(A, B, C, D) and g(A, B, C, D), then function (f&g)(A, B, C, D) corresponds to mask_f&mask_g bitmask.

Now, we could parse expression given input into binary tree. I should notice that the number of non-list nodes of such tree is about . Now, let's calculate dynamic programming on every vertex v — dp[v][mask] is the number of ways to place symbols in expression in the way that subtree of vertex v will correspond to function representing by mask. For list nodes such dynamic is calculated pretty straightforward by considering all possible mask values and matching it with the variable. One could easily recalculate it for one node using calculated answers for left and right subtree in 4¹⁶ operations: dp[v][lmask|rmask] +  = dp[l][lmask] * dp[r][rmask].

But all the task is how to make it faster. One could calculate s[mask], where s[mask] is equal to sum of all its submasks (the masks containing 1-bits only in positions where mask contains 1-bits) in 2⁴·2²⁴ operations using following code:

for (int mask = 0; mask < (1 << 16); ++mask) s[mask] = dp[x][mask];
for (int i = 0; i < 16; ++i)
    for (int mask = 0; mask < (1 << 16); ++mask)
        if (!(mask & (1 << i))) s[mask ^ (1 << i)] += s[mask];

Let's calculate sl[mask] and sr[mask] for dp[l][mask] and dp[r][mask] respectively. If we will find s[mask] = sl[mask] * sr[mask], s[mask] will contain multiplications of values of pairs of masks from left and right dp's, which are submasks of mask. As soon as we need pairs, which in bitwise OR will give us exactly mask, we should exclude pairs, which in bitwise OR gives a submask of mask, not equal to mask. This gives us exclusion-inclusion principle idea. The formula of this will be

, where p is the parity of number of bits in mask^submask.

Such sum could be calculated with approach above, but subtracting instead of adding

for (int mask = 0; mask < (1 << 16); ++mask) s[mask] = sl[mask] * sr[mask];
for (int i = 0; i < 16; ++i)
    for (int mask = 0; mask < (1 << 16); ++mask)
        if (!(mask & (1 << i))) s[mask ^ (1 << i)] -= s[mask];

In such way we will recalculate dynamic for one vertex in about 3·2⁴·2¹⁶ operations.

Jury's solution: 13390713

Greetings, Codeforces!

My name is Danil Sagunov, and I used to be red... Anyway, I wish to congratulate you with the Second Revolution!

I am glad to introduce that this Saturday, 3rd October at 19:30 MSK Codeforces Round #323 for both divisions will take place. Problemset has been prepared for you by me and Vitaly gridnevvvit Gridnev. This is not the first round we are authors of and I'm sure that it's not the last.

Special thanks to our friends Maxim Neon Mescheryakov, Vladimir vovuh Petrov and Roman Roms Glazov for helping us preparing the round. I would like to thank Max Zlobober Akhmedov for his coordinator activity, Michael MikeMirzayanov Mirzayanov for creating and supporting Codeforces and Polygon systems, making this round possible, and Maria Delinur Belova for translating problem statements into English.

Thanks to Vladislav winger Isenbaev and Alex AlexFetisov Fetisov for testing the round problemset!

Both division participants will be given five problems and two hours to solve them. I hope that everyone will find the problems interesting and many of you will return your colors.

UPD The round duration was written incorrectly in the e-mail announcement, the correct duration is 2 hours, not 2.5 hours.

UPD2 Round have been successfully finished! Thank you all for participating.

Congratulations to 1 division winners!

1. ecnerwala
2. ikatanic
3. uwi
4. PavelKunyavskiy
5. sd0061

And the second division:

1. wrong_order
2. ahwhlzz
3. kefaa

My gratitude to fotiIe96, one to solve problem D!

UPD3 Editorial can be found here

534A - Exam

Is easy to see that k = n with n ≥ 4. There are many algorithms that can be used to build a correct sequence of length n with n ≥ 4. For example, students can be seated from left to right with the first to seat students with odd numbers in decreasing order starting with largest odd number. Then similary to seat students with even numbers. In this sequence the absolute difference between two adjacent odd (or even) numbers equal to 2. And the difference between odd and even numbers greater or equal 3 (because n ≥ 4).

Cases n = 1, n = 2, n = 3 are considered separately. Solution complexity — O(n).

Jury's solution: 10691992

534B - Covered Path

It can be easily proved that every second i (0 ≤ i ≤ t - 1) the maximum possible speed is . You can iterate through i from 0 to t - 1 and the values of v_i.

Solution complexity — O(t).

Also you can use next fact. If current speed equal to u and left t seconds then there is a way to get v₂ speed at the end only if |u - v₂| ≤ t·d. Consider this criteria, one can simply try to change speed to maximum possible (from u + d down to u - d), choosing first giving a way to reach the end of the path.

Jury's solutions: 10692136 и 10692160

534C - Polycarpus' Dice

Solution uses next fact. With k dice d₁, d₂, ..., d_k you can dial any sum from k to . This is easily explained by the fact that if there is a way to get the amount of s > k, then there is a way to dial the sum equal s - 1, which is obtained by decreasing the value of one die by one.

Let's denote sum of all n dice as . Fix the dice d_i (value on it denote as x (1 ≤ x ≤ d_i). Using the other dice we can select s (n - 1 ≤ s ≤ S - d_i). We know that average value s + x = A, and n - 1 ≤ A - x ≤ S - d_i, giving A - (n - 1) ≥ x ≥ A - (S - d_i).

Using facts described above, for every dice one can calculate a possible values segment, giving the answer for the count of impossible values of that dice. Solution asymptotic — O(n).

Jury's solution: 10692192

534D - Handshakes

From here we will not consider resulting permutation but correct handshakes sequence (rearranged given sequence). Formally, the sequence of handshakes count a_i is correct if and only if a_i + 1 ≤ a_i + 1 and a_i + 1 ≡ a_i + 1 ± od{m} and a₁ = 0. To form correct sequence, we can use following greedy algorithm.

First, place 0 as the first number. Next, for every following number a_i + 1 we will select maximum possible number from numbers left, matching above constraints (in simple case it will be a_i + 1, otherwise we will check if a_i - 2 left, e.t.c).

The solution may divide given sequence into three parts (depending on modulo by 30), and using, for example, data structure ''set'', quickly find the next number to place into resulting sequence. Such solution will work in . There is also possible to get O(n) asymptotics using path compression technique.

Jury's solution: 10692252

534E - Berland Local Positioning System

Suppose that the bus started his way from the stop with number 1 and modulate its way during m stops. For every stop we will calculate how many times this stop was visited by the bus at that way. Check if that counts match counts in the input and update the answer if needed. Then we will try to move the start stop to stop with number 2. It's easy to see that the last visited stop (as long as bus must visit m stops) will move to the next stop. So we need to modulate bus way to another one stop from first stop and from last stop to change the starting stop to another (it makes maximum of four counts to be updated). It could be done in O(1) time.

This way we need to move starting stop to every variant (its count is equal to 2n - 2) and for every variant update the answer if needed. Average solution works in O(n) time.

Jury's solution: 10705354

534F - Simplified Nonogram

This task has several solution algorithms.

One of them could be described next way. Let's divide n × m field into two parts with almost same number of columns (it will be n × k and n × (m - k)). Let's solve the puzzle for every part of the field with brute-force algorithm (considering column constraints on number of blocks) with memorization (we do not need same solutions with same number of blocks in rows). Then we will use meet-in-the-middle approach to match some left part with right part to match constraints on n × m field.

Another solution could be profile dynamic programming, where the profile is the number of blocks in the row.

Jury's solution uses both ideas: 10705343

499A - Watching a movie

One can solve the problem using greedy algorithm: if we can skip x minutes at current moment without skipping any good moment — we do that, otherwise — watch another minute of the film.

499B - Lecture

In this task you must find for every string in the text the pair containing that string, and from two strings of that pair output the shortest one.

498A - Crazy Town / 499C - Crazy Town

It can be easily proved that, if two points from statement are placed on different sides of some line, this line will be crossed anyway. So, all we need to do is to cross all these lines, so the answer is the number of these lines.

To check if two points lies on different sides of a line one can simply use its coordinates to place in line equation and check if these two values have different signs.

Solution complexity — O(n).

498B - Name That Tune / 499D - Name That Tune

Let's numerate all the songs and seconds starting from 0.

Problem will be solved using DP approach. State will be described by two integers (i, j): dp[i][j] is probability of that we named exactly i songs, and the last named song was named exactly before j'th second (after j - 1 seconds). dp[0][0] = 1 obviously.

To make a move from state (i, j) to state (i + 1, j + k) (1 ≤ k < t_i), we must name the song exactly after k seconds its playing — probability of that is (1 - p_i)^k - 1·p_i.

To fixed state (i + 1, j) sum of that moves can be represented as . Simple calculation of this value for each state gives O(nT²) complexity, so one must notice, that this values can be calculated using two pointers for fixed i (in common case it represent a segment with t_i length) for every j in time O(T). This way calculating this type of moves takes O(nT) time.

There is also a move to (i + 1, j + t_i) and a move from (i, j) to (i, (j + k) = T), when we couldn't name current song in time T. This types of moves is calculated with O(nT) too.

Solution complexity — O(nT).

498C - Array and Operations / 499E - Array and Operations

We will divide only by prime numbers.

First, let's build a graph, where each of n numbers have own vertex group:

Find all prime factors of current number. Every factor will have its own vertex in a group, furthermore, if some factor p has power of a_i in current number, it will have exactly a_i vertexes in group.

The number of vertexes in such graph is .

Now we will make edges in our graph: edge between two vertexes exists if and only if there is a good pair (given in statement) of vertexes group numbers and the prime values of a vertexes are the same. That means that we can divide that group numbers by that prime.

The number of edges is .

Good pairs are given the way that our graph is bipartite. After finding maximum matching in this graph we represent the way of doing operations as described in the statement.

As soon as solution is using Kuhn's algorithm, its complexity is . One could notice that some of the edges are useless and reduce it to .

498D - Traffic Jams in the Land

The solution of a problem — 60 (LCM of a numbers from 2 to 6) segment trees.

In v'th segment tree we will hold for every segment [l, r] the next value: minimum time needed to get from l to r if we start in a moment of time equal to v modulo 60. Using these trees' values it is easy to quickly answer the questions, carefully changing the trees' values.

498E - Stairs and Lines

The problem is solved using DP approach dp[i][mask] — the number of ways to paint first i blocks of a ladder the way that the last layer of vertical edges is painted as described in mask mask. This could be easily recalculated using matrix M[mask1][mask2] — the number of ways to paint horizontal edges between two neighbour vertical layers painted as represented by masks mask1 and mask2.

For fixed i we have w_i layers, so this matrix must be multiplied by itself w_i times, which can be quickly done by binary-pow algorithm. After that this matrix is simply used in dynamic described above.

Solution complexity — .

Hello, Codeforces!

Some minutes ago I got accepted with problem on SPOJ resource. But a hour ago my correct solution was getting Runtime Error (Non-Zero Exit Code) because of in.close() in following code:

in = new BufferedReader(new InputStreamReader(System.in));
...
in.close();

Removing that line brings me accepted. Could anyone explain that?

483A - Counterexample

Problem author gridnevvvit

This problem has two possible solutions:

1. Let's handle all possible triples and check every of them for being a counterexample. This solution works with asymptotics O(n³logA)
2. Handle only a few cases. It could be done like this:

  if (l % 2 != 0)
      l++;
   
  if (l + 2 > r)
    out.println(-1);
  else
    out.println(l + " " + (l + 1) + " " + (l + 2));
 

Jury's solution: 8394832

483B - Friends and Presents

Problem author gridnevvvit

Jury's solution is using binary search. First, you can notice that if you can make presents with numbers 1, 2, ..., v then you can make presents with numbers 1, 2, ..., v, v + 1 too. Let f(v) be the function returning true or false: is it right, that you can make presents with numbers 1, 2, ..., v. Let f₁ be the number of numbers divisible by x, f₂ — the number of numbers divisible by y, and both — number of numbers divisible by x and by y (as soon as x and y are primes, it is equivalent to divisibility by x·y). Then to first friend at first we shold give f₂ - both numbers, and to second friend f₁ - both numbers. Then we must check, could we give all other numbers divisible neither by x nor by y.

This solution works with

Jury's solution: 8394846

483C - Diverse Permutation / 482A - Diverse Permutation

Problem author gridnevvvit

Let's see, what's the solution for some k = n - 1:

1 10 2 9 3 8 4 7 5 6

At the odd indexes we placed increasing sequence 1, 2, 3 .., at the even — decreasing sequence n, n - 1, n - 2, ... First, we must get the permutation the way described above, then get first k numbers from it, and then we should make all other distances be equal to 1.

This solution works with O(n).

Jury's solution: 8394876

483D - Interesting Array / 482B - Interesting Array

Problem author gridnevvvit

We will solve the task for every distinct bit. Now we must handle new constraint: l[i], r[i], q[i]. If number q[i] has 1 in bit with number pos, then all numbers in segment [l[i], r[i]] will have 1 in that bit too. To do that, we can use a standard idea of adding on a segment.

Let's do two adding operation in s[pos] array — in position l[i] we will add 1, and in posiotion r[i] + 1 — -1. Then we will calculate partial sums of array s[pos], and if s[pos][i] > 0 (the sum on prefix length i + 1), then bit at position pos will be 1, otherwise — 0.

After that, you can use segment tree to check satisfying constraints.

Jury's solution: 8394894

483E - Game with Strings / 482C - Game with Strings

Problem author gridnevvvit

Let's handle all string pairs and calculate the mask mask, which will have 1-bits only in positions in which that strings have the same characters. In other words, we could not distinguish these strings using positions with submask of mask mask, then we must add in d[mask] 1-bits in positions i и j. This way in d[mask] we store mask of strings, which we could not distinguish using only positions given in mask mask. Using information described above, we can easily calculate this dynamics.

Now, when we have array d calculated, it is not hard to calculate the answer. Let's handle some mask mask. Now we should try to make one more question in position pos, which is equal to adding one more 1-bit in mask in position pos. After that we may guess some strings, they are 1-bits in mask s = d[mask] ^ d[mask | (1 << pos)]. Then you have to calculate number of bits in s quickly and update the answer.

Jury's solution: 8394918

482D - Random Function and Tree

Problem author RoKi

Let's calculate d[v][p] dynamics — the answer for vertex v with size of parity p.

At first step to calculate this dynamic for vertex v we should count all different paintings of a subtree visiting all children in increasing order of their numbers. By multiplying this number by 2 we will get paintings visiting children in decreasing order. Now some paintings may count twice. To fix that, let's have a look on a some subtree of a vertex v.

Consider all the parities of children subtrees visited by our function (0 or 1). First thing to note is that among these parities exist two different values, the subtree will have different paintings with different ordering (you can prove it yourself). Otherwise, all our children sizes have the same parity.

If all sizes are even, this subtree will be counted twice. Otherwise, if sizes are odd, we are interested only in odd count of visited subtrees. This way, we must subtract from our dynamic the number of ways to paint any number of children with even subtree sizes and odd number of children with odd subtree sizes.

Jury's solution: 8394936

482E - ELCA

Problem author danilka.pro

Let's split all M requests in blocks containing requests each. Every block will be processed following way:

First using dfs we need to calculate for every vertex v, where u is every ancestor of v, size_i — size of subtree of vertex i, including itself. This value shows how will the answer change after removing or adding vertex v as child to any other vertex, furthermore, answer will change exactly by path_v·size_v (decreasing or increasing).

Then we will calculate ch_v the same way — the number of all possible vertex pairs, which have LCA in vertex v. This value shows how the answer changes after changing V_v — if V_v changes by dV_v, answer changes by ch_v·dV_v.

Then mark all vertexes, which occur in our block at least once (in worst case their number is ). Next, mark every vertex being LCA of some pair of already marked vertexes, using DFS. We can prove that final number of these vertexes is at most . After all this we got 'compressed' tree, containing only needed vertexes. Parent of vertex i in compressed tree we will call vertex numbered P_i.

On the image above example of this 'compression' way is given. Vertexes colored red are vertexes in request block, blue — vertexes marked after LCA, dotted line — P_v → v edges in compressed tree.

On such compressed tree we need to calculate one new value C_v for every vertex v — the size of a vertex, lying on a way from P_v to v after P_v on main (non-compressed) tree (son of a P_v vertex in main tree).

Now we should process request on changing parent of vertex v from p_v to u on a compressed tree. The answer will change by path_v·size_v. Now for every vertex i, lying on a way from root to P_v vertex, two values will change: size_i will be decreased by size_v, but ch_i will be decreased by size_v·(size_i - C_t), (P_t = i), but path_i will stay unchanged. For every other vertex j only path_j will be changed: it will be decreased by . After that, we got compressed subtree where subtree of a vertex v is missing. Next, doing the same way as above, all values are changed considering that v (and all it's subtree) is a children of a vertex u. Do not forget to change C_v too.

Let's see, how the value-changing request of a vertex v is to be processed. As described above, the answer will be changed by ch_v·dV_v. For every vertex i lying in vertex v subtree only path_i will be changed (it could be easy done using C_to values), all other values stay unchanged.

This solution has complexity, but in N = M case it has to be .

Авторское решение: 8394944

441A - Valera and Antique Items

Problem author gridnevvvit

You need to implement what written in statement. You could act like that: let's calculate q_i — minimum item price from seller i. Then if q_i < v, we can make a deal with seller i, otherwise we can't.

Jury's solution: 6850474

441B - Valera and Fruits

Problem author gridnevvvit

Let's start counting days from 1 to 3001. Let current day be i. Additionally, we'll have cur variable — number of fruit we didn't collect previous days. Suppose now fruit is ripen current day. If now + cur ≤ v, we need to add now + cur to answer and update cur value (cur = 0). Otherwise we add v to answer, but cur value need to be updated as follows. Let tv = max(v - cur, 0). Then cur = now - tv. In other words, we try to collect fruits that will not be collectable next day.

Additionally, problem could be solved with , but this is not required.

Jury's solution: 6850502

Bonus. Suppose fruit can be collected at days a_i, a_i + 1, ..., a_i + T_i, where T_i — some number for each tree. How to solve this task optimally?

Additionaly, for every day there will be its own v (maximum number of fruit collected).

441C - Valera and Tubes

Problem author gridnevvvit

The solution is pretty simple. First we need to make such route that visits every cell exactly one time. It is not difficult:

1. Initially we stay in (1, 1) cell. Moving from left to right, we should reach (1, m) cell.
2. Move to the next line, in (2, m) cell. Moving from right to left, we should reach the most left sell of 2nd line, (2, 1).
3. Move to the next line. Repeat 1. and 2. while we have not all cells visited.

After that, we can easily find the solution: you can make first (k - 1) tubes length be 2, and the last k tube will consist from cells left.

Jury's solution: 6850508

441D - Valera and Swaps

Problem author danilka.pro

In this task you should represent permutation as graph with n vertexes, and from every vertex i exists exactly one edge to vertex p[i]. It's easy to understand that such graph consists of simple cycles only.

If we make swap (i, j), edges and will become edges and respectively. Then if i and j is in the same cycle, this cycle will break:

but if they are in different cycles, these cycles will merge into one:

this means that every swap operation increases number of cycles by one, or decreases it by one.

Assuming all above, to get permutation q from permutation p, we need to increase (or decrease) number of cycles in p to n - m. Let c — number of cycles in p. Then k always equals |(n - m) - c|.

For satisfying lexicographical minimality we will review three cases:

1) n - m < c

It's easy to understand, that in this case you must decrease cycles number by merging cycles one by one with cycle containing vertex 1. This way every swap has form (1, v), where v > 1. Because every cycle vertex is bigger than previous cycle vertex, this case can be solved with O(n).

2) n - m > c

In this case you should break cycle for every vertex, making swap with smallest possible vertex (it should be in this cycle too). This could be done if represent cycle by line . As soon as every cycle is broken with linear asymptotics, this case solution works with O(n²).

Bonus: this way of representing cycle lets us optimize solution to asymptotics, you may think how.

3) n - m = с

Besause in this case k = 0, there is nothing need to be swapped.

It's highly recommended to inspect jury's solution: 6850515

441E - Valera and Number

Problem author gridnevvvit

We will solve the task by calculating dynamic d[i][mask][last][cnt] — possibility of getting v which 8 last bits equals mask, 9th bit equals last, cnt — number of consecutive bits (following 9th bit) and equal to last, after i steps.

Good, but why we left other bits? It's clear, that using operation  +  = 1 we can change only first 0 bit with index  ≥ 9.

Transitions is pretty obvious: we add 1 or multiply by 2 (it's recommended to see them in jury's solution). Perhaps, you should ask following question. For example, we have number x = 1011111111 in binary representation.

And at this moment, we make  +  = 1. According to all above, we must go to d[1][0][1][2] condition, but we can't do that because we don't have any information about 1 in 10th position. But, as we can not change any bit with index  ≥ 9 (mask = 0) we make transition to d[1][0][1][1].

Jury's solution: 6850523

Bonus. Let us have other pseudocode.

// input x, k, p
 
for(i = 0; i < k; i += 1) {
   if (x is even) {
     rnd = random number from interval [1, 100]
     if (rnd <= p)
       x *= 2;
     else
       x += 1;
   } else {
      x *= 2;
   }
}
 
s = 0;
 
while (x is even) {
  x /= 2;
  s += 1;
}
 

As before, you must find expected value of s.

How effectively you can solve this problem? Can you prove your solution?

Your corrections of my bad English are welcome, thank you.

Tired of being loser at Codeforces? Do your best and reach the International Grandmaster rank at least here: http://games.usvsth3m.com/2048/codeforces-edition/