414.md (10239B)
1 Source: https://codeforces.com/blog/entry/11470 2 3 Hi! 4 5 [415A - Mashmokh and Lights](/contest/415/problem/A "Codeforces Round 240 (Div. 2)") 6 7 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. 8 9 [415B - Mashmokh and Tokens](/contest/415/problem/B "Codeforces Round 240 (Div. 2)") 10 11 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*). 12 13 Suppose  by *p*. then *p* * *b* ≤ *w* * *a*. then . 14 15 Suppose initially we have *k* tokens. Let  then we need to find such maximum *k*0 that . 16 17 So *k*0 will be equal to . so we can calculate *k*0 in *O*(1). 18 19 [414A - Mashmokh and Numbers](/contest/414/problem/A "Codeforces Round 240 (Div. 1)") 20 21 In each turn Bimokh will at least get one point so the result is at lease . So if  the answer is -1. 22 23 Let's denote . Then you could output *x* and 2*x* 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*. 24 25 . 26 27 Also you must consider some corner cases such as when *n* = 1. 28 29 [414B - Mashmokh and ACM](/contest/414/problem/B "Codeforces Round 240 (Div. 1)") 30 31 Lets define *dp*[*i*][*j*] as number of good sequences of length *i* that ends in *j*. 32 33 Let's denote divisors of *j* by *x*1, *x*2, ..., *x**l*. Then  34 35 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. 36 37 ``` 38 for (i = 1; i <= n; i++) //loop from 1 to n 39 for (int j = i; j <= n; j += i) //iterating through all multiples of i that are at most n 40 ``` 41 42 [414C - Mashmokh and Reverse Operation](/contest/414/problem/C "Codeforces Round 240 (Div. 1)") 43 44 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*. 45 46 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*n*). We'll 47 48 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). 49 50 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*n*). 51 52 [414D - Mashmokh and Water Tanks](/contest/414/problem/D "Codeforces Round 240 (Div. 1)") 53 54 Let's suppose instead of a tank there is a pile at each vertex and instead of water the game is played on tiles. 55 56 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. 57 58 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*1, *a*2, ...*a**x**j* 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. 59 60 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*1 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*0 then there must be a tile at each vertex with depth more than *d*0 and less than or equal to *d*1. 61 62 Let's iterate over *d*1. Then for each *d*1 we can calculate *d*2, the minimum depth that we can pay the needed price if we put a tile at each vertex with depth at least *d*2 and at most *d*1. Let's denote this needed price as *p*0. Then we can also put  at depth *d*2 - 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*1. So the maximum of these numbers for all possible *d*1 will be the answer. 63 64 Since by increasing *d*1, *d*2 won't decrease one can use two-pointers to update *d*2 while iterating over *d*1. Let's denote number of the vertices with depth *i* as *cnt**i*. Then we can save and update the following values. 65 66  67 68  69 70 Then the needed price is equal to (*d*1 * *s*) - *t*. So as long as (*d*1 * *s*) - *t* > *p* we must increase *d*2. This yields an *O*(*n*) solution. 71 72 [414E - Mashmokh's Designed Problem](/contest/414/problem/E "Codeforces Round 240 (Div. 1)") 73 74 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*. 75 76 Suppose we can perform the following operations on such sequence: 77 78 1. For each *i*, find sum of the elements 1..*i*. 79 2. For each *i* find the biggest *j*(*j* < *i*) so that sum of elements 1..*j* of the sequence equals *p*. 80 81 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. 82 83 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*). 84 85 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.) 86 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. 87 3. Also we'll store the minimum number amongst prefix sums.