494.md (13693B)
1 Source: https://codeforces.com/blog/entry/15148 2 3 [495A - Цифровой индикатор](/contest/495/problem/A "Codeforces Round 282 (Div. 2)") 4 5 For each digit *x* you can count the number of digits *y* that because of some broken sticks *x* is shown instead of *y* by hand. for example when *x* = 3, *y* can be 3, 8 and 9. Let's denote this number by *a**x*. Then if the input is *xy* (the first digit shown in the counter is *x* and the second is *y*) the answer will be *a**x* × *a**y*. 6 7 [495B - Модулярные уравнения](/contest/495/problem/B "Codeforces Round 282 (Div. 2)") 8 9 * If *a* < *b* then there is no answer since . 10 * If *a* = *b* then *x* can be any integer larger than *a*. so there are infinite number of answers to the equation. 11 * The only remaining case is when *a* > *b*. Suppose *x* is an answer to our equation. Then *x*|*a* - *b*. Also since  then *b* < *x*. These conditions are necessary and sufficient as well. So the answer is number of divisors of *a* - *b* which are strictly greater than *b* which can be solved in . 12 13 [494A - Сокровище](/contest/494/problem/A "Codeforces Round 282 (Div. 1)") 14 15 Consider a string consisting of '(' and ')' characters. Let's build the following sequence from this string: 16 17 1. *a*0 = 0 18 2. for each 1 ≤ *i* ≤ |*s*| *a**i* = *a**i* - 1 + 1 if *s**i* = '(' and *a**i* = *a**i* - 1 - 1 otherwise. (The string is considered as 1-based index). 19 20 It can be proven that a string is beautiful if the following conditions are satisfied: 21 22 1. for each 0 ≤ *i* ≤ |*s*| *a**i* ≥ 0. 23 2. *a*|*s*| = 0 24 25 Using the above fact we can prove that if in a beautiful string we remove a ')' character and put it further toward the end of the string the resulting string is beautiful as well. These facts leads us to the following fact: if we can move a ')' character further toward the end of string it is better if we'd do it. This yields the following greedy solution: 26 27 We'll first put exactly one ')' character at each '#' character. Then we'll build the sequence we described above. if the first condition isn't satisfied then there is no way that leads to a beautiful string. So the answer is -1. Otherwise we must put exactly *a*|*s*| more ')' characters in the place of last '#' character. Then if this string is beautiful we'll print it otherwise the answer is -1. 28 29 [494B - Одержимость строкой](/contest/494/problem/B "Codeforces Round 282 (Div. 1)") 30 31 We call an index *i*(1 ≤ *i* ≤ |*s*|) good if *t* equals *s**i* - |*t*| + 1*s**i* - |*t*| + 2... *s**i*. To find all good indexes let's define *q**i* as the length of longest prefix of *t* which is a suffix of *s*1*s*2... *s**i*. A good index is an index with *q**i* = |*t*|. Calculating *q**i* can be done using Knuth-Morris-Pratt algorithm. 32 33 Let's define *a**i* as the number of ways to choose some(at least one) non-overlapping substrings of the prefix of *s* with length *i* (*s*1*s*2... *s**i*) so *t* is a substring of each one of them and *s**i* is in one the chosen substrings(So it must actually be the last character of last chosen substring). Then the answer will be . 34 35 Also let's define two additional sequence *q*1 and *q*2 which will help us in calculating *a*. 36 37  38 39  40 41 The sequence *a* can then be calculated in *O*(*n*) as described below: 42 43 If *i* is not a good index *a**i* = *a**i* - 1 since in each way counted in *a**i* the substring containing *s**i* also contains *s**i* - 1 so for each of these ways removing *s**i* from the substring containing it leads to a way counted in *a**i* - 1 and vice-versa thus these two numbers are equal. If *i* is a good index then *a**i* = *q*2*i* - |*t*| + *i* - |*t*| + 1. To prove this let's consider a way of choosing substring counted in *a**i*. We call such a way valid. The substring containing *s**i* can be any of the substrings *s**j**s**j* + 1... *s**i* (1 ≤ *j* ≤ *i* - |*t*| + 1). There are *i* - |*t*| + 1 valid ways in which this substring is the only substring we've chosen. Number of valid ways in which substring containing *s**i* starts at *s**j* equals to *q*1*j* - 1. So the total number of valid ways in which we've chosen at least two substrings are equal to  which is equal to *q*2*j* - 1. So *a**i* = *q*2*i* - |*t*| + *i* - |*t*| + 1. 44 45 [494C - Помощь нуждающимся](/contest/494/problem/C "Codeforces Round 282 (Div. 1)") 46 47 We'll first create a rooted tree from the given segments which each node represents a segment. We'll solve the problem using dynamic programming on this tree. First of all let's add a segment [1, *n*] with probability of being chosen by Malek equal to 0. The node representing this segment will be the root of the tree. Please note by adding this segment the rules described in the statements are still in place. 48 49 Let's sort the rest of segments according to their starting point increasing and in case of equality according to their finishing point decreasing. Then we'll put the segment we added in the beginning. A segment's father is the right-most segment which comes before that segment and contains it. Please note that since we added segment [1, *n*] to the beginning every segment except the added segment has a father. We build the tree by putting a segment's node child of its father's node. 50 51 In this tree for each two nodes *u* and *v* which none of them are in the subtree on another the segments representing these two nodes will not overlap. Also for each two nodes *u* and *v* which *u* is in subtree of *v* segment representing node *u* will be inside(not necessarily strictly) segment representing node *v*. We define *mx**i* as the maximum money a person in the segment *i* initially has. *mx**i* can be calculated using RMQ. Let's define *a**i*, *j* as the probability of that after Malek finishes giving his money the maximum in the segment *i* is at most {*mx*}*i* + *j*. The properties of the tree we built allows us to calculate *a**i*, *j* for every *i* and *j* in *O*(*q*2) (since 1 ≤ *i*, *j* ≤ *q*). If number of the segment we added is *k* then the answer will be . 52 53 Calculating *a**i*, *j* is described below: 54 55 Suppose *f* is a child of *i* and suppose Malek doesn't accept the *i*-th recommendation. Then since we want the maximum number after money spreading to be at most *mx**i* + *j* in segment *i* and since *f* is inside *i* we want the maximum number after money spreading to be at most *mx**i* - *mx**f* + *j*. If Malek accepts the recommendation then we want it to be at most *mx**i* - *mx**f* + *j* - 1. So if probability of *i*-th recommendation being accepted by Malek be equal to *p**i* then . Using this formula we can calculate *a**k*, *j* recursively and calculate the answer from it in *O*(*q*2). The overall complexity will be *O*(*nlgn* + *q*2). *nlgn* for creating RMQ used for calculating the array *mx* and *q*2 for the rest of the algorithm. 56 57 [494D - День рождения](/contest/494/problem/D "Codeforces Round 282 (Div. 1)") 58 59 We solve this problem by answering queries offline. We'll first store in each vertex *v* number of vertices such as *x* for which we must calculate *f*(*v*, *x*) . starting from the root. We'll keep two arrays *a* and *b*. Suppose we're at vertex *v* right now then *a**i* equals *d*(*i*, *v*)2 and *b**i* equal *d*(*i*, *v*). Having these two arrays when moving from vertex *v* to a child with an edge with weight *k* one can note that *b**i* for all *i*s inside subtree of *v* decreases by *k* and all other *b**i*s gets increased by *k*. Knowing this fact one can also update array *a* as well. To calculate *f*(*v*, *x*) it's enough to be able to calculate sum of *a**i*s for all *i* inside subtree of *x*. Handling each of these operations is a well known problem and is possible using a segment tree. Overall complexity is *O*((*n* + *q*)*lgn*). There is an online solution using dynamic programming as well. 60 61 [494E - Шарти](/contest/494/problem/E "Codeforces Round 282 (Div. 1)") 62 63 Let's first solve this problem for another game: Suppose that we've an *n* × *n* table. Each cell have some(possibly zero) marbles on it. During each move the player chooses a square with side-length at most *k* which its lower-right cell has at least one marble, he removes one marble from it and puts one marble in every other cell of this square. One can notice that in such game each marble is independent of the others and doesn't affect other marbles. So one can see this game as some separate games played on some tables. More formally for each marble placed in a cell such as (*i*, *j*) consider the game when played on a *i* × *j* table which the only marble placed on it is at its lower-right cell. Let's denote the Grundy number of this game by *g**i*, *j*. Then according to Grundy theorem the first player has a winning strategy if and only if the xor of *g**i*, *j* for every cell (*i*, *j*) having odd number of marbles on it is positive. 64 65 To calculate *g**i*, *j* note that the first move in such game must be choosing a square with its lower-right cell being the lower-right cell of table. So the only thing to decide is the side-length of chosen square at the first move. Let's say we choose the first square width side length *l*. Grundy number of the next state will be equal to xor of *g**c*, *d* for every *i* - *l* < *c* ≤ *i*, *j* - *l* < *d* ≤ *j*. Using this fact one can calculate *g**i*, *j* for all (1 ≤ *i*, *j* ≤ *a*) (*a* being an arbitrary integers) in *O*(*a*3). 66 67 If we calculated the first values of *g**i*, *j* one can see a pattern in the Grundy numbers. Then one can prove that *g**i*, *j* = *min*(*lowest*_*bit*(*i*), *lowest*_*bit*(*j*), *greatest*_*bit*(*k*)) where *lowest*_*bit*(*x*) = the maximum power of 2 which is a divisor of *x* and *greatest*_*bit*(*x*) = the maximum power of 2 which is not greater than *x*. 68 69 Now let's prove that our first game(the game described in the statement) is actually the same as this game. Suppose that a player has a winning strategy in the first game. Consider a table containing one marble at every cell which is white in the table of the first game. We'll prove that the same player has winning strategy in this game as well. Note that a cell is white in the first game if and only if the parity of marbles in the second game is odd so there is at least one marble on it. So as long as the other player chooses a square with its lower-right cell having odd number of marbles in the second game, his move corresponds to a move in the first game so the player having winning strategy can counter his move. If the other player chooses a square with its lower-right cell having even number of marbles, it means the cell had at least 2 marbles on it so the player can counter it by choosing the same square which makes the parity of every cell to be the same after these 2 moves. And since it can be proven that both of the game will end at some point then the player has winning strategy in this game as well. The reverse of this fact can also be proven the same since if a player has a winning strategy there is also a winning strategy in which this player always chooses squares with lower-right cell having odd number of marbles(since otherwise the other player can counter it as described above) and counters the moves of the other player at which he chose a square with lower-right cell having even number of marbles by choosing the same square(since the Grundy number by countering in this way won't change the Grundy number and thus won't change the player with winning strategy). 70 71 So if we consider a table having one marble at each of the cells which are in at least one of the rectangles given in the input we only need to calculate the Grundy number of this state and check whether it's positive or not to determine the winner. To do this for each *i*(1 ≤ *i* ≤ *greatest*_*bit*(*k*)) lets define *a**i* as the number of cells (*x*, *y*) which are contained in at least one of the given rectangles, 2*i*|*x* and 2*i*|*y*. Lets also define *a**greatest*_*bit*(*k*) + 1 = 0. Then according the fact we described above about *g**i*, *j* the number of 2*i*s which are xored equals *a**i* - *a**i* + 1. Knowing this calculating the Grundy number of the initial state is easy. Calculating *a**i* is identical to a very well-known problem which is given some rectangles count the number of cells in at least one of them and can be solved in *O*(*mlgm*) (*m* being number of rectangles). So overall complexity will be *O*(*mlgmlgk*). 72 73 If there is any problem in the editorial please feel free to note that to us. 74 75 Thank you.