Hi!

415A - Mashmokh and Lights

For this problem for each light j you could just iterate over all pressed buttons and find the first button b_i that b_i < j. Then you could output b_i and move to next light.  

415B - Mashmokh and Tokens

For this problem you can find the number of tokens you can save if you initally have k tokens in O(1). Then you can calculate the answer for all of numbers in O(n).

Suppose by p. then p * b ≤ w * a. then .

Suppose initially we have k tokens. Let then we need to find such maximum k₀ that .

So k₀ will be equal to . so we can calculate k₀ in O(1).

414A - Mashmokh and Numbers

In each turn Bimokh will at least get one point so the result is at lease . So if the answer is -1.

Let's denote . Then you could output x and 2x as the first two integers in the sequence then output consecutive integers and also one random integer(distinct from the others) if n is odd. Based on the following fact, Bimokh's point will equal to which is equal to k.

.

Also you must consider some corner cases such as when n = 1.

414B - Mashmokh and ACM

Lets define dp[i][j] as number of good sequences of length i that ends in j.

Let's denote divisors of j by x₁, x₂, ..., x_l. Then

This yields O(nk sqrt(n)) solution which is not fast enough. But one could use the fact that the following loops run in O(n log(n)) in order to achieve O(nk log(n)) which is fast enough to pass the tests.

for (i = 1; i <= n; i++)  //loop from 1 to n
   for (int j = i; j <= n; j += i)  //iterating through all multiples of i that are at most n

414C - Mashmokh and Reverse Operation

Build a complete binary tree with height n. So its i-th leaf corresponds to i-th element of the initial array. For each vertex v lets define its subarray as the subarray containing the elements that have a leaf corresponding to them in subtree rooted at v.

For each non-leaf vertex v, suppose its left child's subarray contains elements [a..b] of the array and its right child contains elements [b + 1..c] of the array. We'll calculate two numbers for this vertex. number of pairs (i, j)(a ≤ i ≤ b ≤ j ≤ c) that a_i > b_j and number of pairs (i, j)(a ≤ i ≤ b ≤ j ≤ c) that a_i < b_j. We'll call the first calculated number, normal number and the other one reverse number. Calculating these numbers can be done using merge-sort algorithm in O(n  *  2ⁿ). We'll

Initially write normal number for each vertex on it. We'll define a vertex's type as type of the number that is written on them. Let's define height of a vertex v equal to its distnace to the nearest leaf. Also let's define switching a vertex as switching the number written on it with the other type number(if normal number is written on it change it to reverse number and vise-versa).

Initially sum of writed numbers is equal to number of inversions in the initial array. Now when query h is given, by switching all vertices with height at most h, the sum of writed numbers will become equal to the number of inversions in the new array. The only question is how to perform such query fast? One can notice that in a height h, always all of the vertices has the same type. So we can calculate two numbers for each height h. The sum of normal numbers of vertices with height h and the sum of their reverse numbers. Then instead of switching vertices in a height one by one each time, one can just switch the number for that height. The sum of numbers of heights after each query will be the answer for that query. since there are n height each query can be performed in O(n) so the total running time will be O(nq  +  n  * 2ⁿ).

414D - Mashmokh and Water Tanks

Let's suppose instead of a tank there is a pile at each vertex and instead of water the game is played on tiles.

Let's denote distance of each vertex q from the root by depth(q). Also Let's label each tile with number of the vertex it was initially put on. Suppose initially there was a tile at each of vertices v and u and after some move tile u and v are in the same vertex's pile. Then one can prove that there were exactly |depth(v) - depth(u)| moves at which vertex containing the tile at vertex with less depth was closed and the vertex containing the other tile wasn't.

Suppose after i-th move, there was x_i tiles inside the root's pile and x_j is the maximum among these numbers. Suppose tiles a₁, a₂, ...a_xj were on the root after j-th move. Then the other tiles that we put inside the tree at the beginning have no effect in the final result. Then we can suppose that only these tiles were initially put on tree.

So we can assume that all tiles we place at the beginning will reach to the root together. Suppose h_i of these tiles were put at a vertex with depth i and d₁ is the maximum depth that there is at least a tile in that depth. So as to these tiles reach to the root together we must pay . Then we want to minimize the number of needed coins so at the beginning there must not be two consecutive depth i and i + 1 that i + 1 ≤ d and there is a tile at depth i and an empty vertex at depth i + 1. In other words if we denote the minimum depth that initially there is a tile inside it as d₀ then there must be a tile at each vertex with depth more than d₀ and less than or equal to d₁.

Let's iterate over d₁. Then for each d₁ we can calculate d₂, the minimum depth that we can pay the needed price if we put a tile at each vertex with depth at least d₂ and at most d₁. Let's denote this needed price as p₀. Then we can also put at depth d₂ - 1. So we can calculate maximum number of tiles that we can put on the tree so that they all reach to root together for a fixed d₁. So the maximum of these numbers for all possible d₁ will be the answer.

Since by increasing d₁, d₂ won't decrease one can use two-pointers to update d₂ while iterating over d₁. Let's denote number of the vertices with depth i as cnt_i. Then we can save and update the following values.

Then the needed price is equal to (d₁ * s) - t. So as long as (d₁ * s) - t > p we must increase d₂. This yields an O(n) solution.

414E - Mashmokh's Designed Problem

Let's define the dfs-order of a tree as the sequence created by calling function dfs(root). We'll build another sequence from a dfs-order by replacing each vertex in dfs-order by '+1' and inserting a '-1' after the last vertex of its subtree. Note that all vertices of a particular subtree are a continuous part of dfs-order of that tree. Also note that for each vertex v if the +1 corresponding to it is the i-th element of sequence, then v's distance from root(which we'll denote by height of v) is equal to sum of elements 1..i.

Suppose we can perform the following operations on such sequence:

1. For each i, find sum of the elements 1..i.

2. For each i find the biggest j(j < i) so that sum of elements 1..j of the sequence equals p.

Using these two operations we can find LCA of two vertices v and u, so since distance of u and v equals to height(u) + height(v) - 2 * height(LCA(u, v)) we can answer the second query. Also the third query can be answered using the second operation described above.

As for the first query it cuts a continuous part of sequence and insert it in another place. This operation can be done using implicit treap. Also we can use the treap as a segment tree to store the following values for each vertex v. Then using these values the operations described above can be done. All of these operation can be done in O(logn).

1. Sum of the elements in its subtree(each vertex in the treap has a value equal to +1 or -1 since it corresponds to an element of the sequence.)

2. Let's write the values of each vertex in the subtree of v in the order they appear in the sequence. Then lets denote sum of the first i numbers we wrote as ps[i] and call elements of ps, prefix sums of the subtree of v. Then we store the maximum number amongst the prefix sums.

3. Also we'll store the minimum number amongst prefix sums.