Blog entries - Codeforces

495A - Digital Counter

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.

495B - Modular Equations

If a < b then there is no answer since $\text{[math]}$ .
If a = b then x can be any integer larger than a. so there are infinite number of answers to the equation.
The only remaining case is when a > b. Suppose x is an answer to our equation. Then x|a - b. Also since $\text{[math]}$ 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 $\text{[math]}$ .

494A - Treasure

Consider a string consisting of '(' and ')' characters. Let's build the following sequence from this string:

a₀ = 0
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).

It can be proven that a string is beautiful if the following conditions are satisfied:

for each 0 ≤ i ≤ |s| a_i ≥ 0.
a_|s| = 0

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:

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.

494B - Obsessive String

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₁s₂... s_i. A good index is an index with q_i = |t|. Calculating q_i can be done using Knuth-Morris-Pratt algorithm.

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₁s₂... 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 $\text{[math]}$ .

Also let's define two additional sequence q1 and q2 which will help us in calculating a.

$\text{[math]}$

The sequence a can then be calculated in O(n) as described below:

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 = q2_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_js_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 q1_j - 1. So the total number of valid ways in which we've chosen at least two substrings are equal to $\text{[math]}$ which is equal to q2_j - 1. So a_i = q2_i - |t| + i - |t| + 1.

494C - Helping People

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.

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.

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²) (since 1 ≤ i, j ≤ q). If number of the segment we added is k then the answer will be $\text{[math]}$ .

Calculating a_i, j is described below:

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 $\text{[math]}$ . Using this formula we can calculate a_k, j recursively and calculate the answer from it in O(q²). The overall complexity will be O(nlgn + q²). nlgn for creating RMQ used for calculating the array mx and q² for the rest of the algorithm.

494D - Birthday

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)² 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 is inside subtree of v decreases by k and all other b_is 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_is 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.

494E - Sharti

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.

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³).

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.

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).

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ⁱ|x and 2ⁱ|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ⁱ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).

If there is any problem in the editorial please feel free to note that to us.

Thank you.

Full text and comments »

#	User	Rating
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

#	User	Contrib.
1	maomao90	174
2	awoo	164
2	adamant	164
4	TheScrasse	159
4	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

matrix's blog