114A - Cifera

We keep dividing l by k until l is not a multiple of k any more, and then check whether l is reduced to 1 or not.

114B - PFAST Inc.

As n is limited up to 16, we can use bitmask to enumerate all the feasible combinations and check whether they can form a group or not. The total complexity is O(2ⁿ × n²).

114C - Grammar Lessons

This is a straightforward implementation problem. For each given string, we need to check the following conditions.

1) all the words end with the required suffix

2) all the words have the same gender

3) all the words appear in the required order

4) there is exactly one noun word

114D - Petr#

The idea is to previously calculate all the positions of the required prefix and suffix. Then, we enumerate every pair of feasible combination, and find out all the different substrings.

Therefore, the main task is how to determine whether two strings are the same or not. I did not come up with a good solution, however I studied the other accepted codes.

I found that they adopt an “unsigned long long int” variable x, initialized with zero value, and compute x = x × prime + s[i], where prime is a prime integer. I think this means to transform or map the string to an integer, like hash table. However, I did not figure out how could this guarantee that no two strings are mapped to the same integer, since we have at most 26²⁰⁰⁰ different strings but only 2⁶⁴ integers. Although for some substring of length m, we can in fact only have O(n) different ones, which is quite small compared with 2⁶⁴, but this still can not guarantee that no collisions occur...

114E - Double Happiness

There is a standard solution, referred to as “sieve function”, to this problem. Using “bitset” can also solve the memory problem. Instead of testing each prime integer, we can enumerate a and b, and then test whether the result of a² + b² is prime or not. The complexity is O(ab) = O(n). To further decrease the constant of complexity, for each value of a, we can start enumerating the value of b from a + 1, with increment step of 2. The reason is that if both a and b are even or odd, the value of a² + b² must be an even integer, and thus is definitely not a prime integer.

112A - Petya and Strings

First change all the letters into lower case ones, and then compare the two strings as the problem requires.

112B - Petya and Square

To cut the whole board into two symmetric parts, the cutting line must pass through the central point. Therefore, the following four squares can not be special cells, i.e., (n, n + 1), (n, n), (n + 1, n), (n + 1, n + 1), where (r, c) denotes the r-th row and the c-th column.

112C - Petya and Inequiations

I did not figure out how to prove this, however it turns out that the following solution can pass all the tests.

At first, note that if can satisfy the requirement, then can satisfy as well. Thus, we set a₁ = a₂ = ...a_n - 1 = 1 and a_n = y - n + 1, which gives the maximum value of . Moreover, if y < n, then the answer is definitely “-1”; otherwise we divide y as mentioned above and check the result is no less than x or not.

112D - Petya and Divisors

For each integer n, it takes complexity to obtain all its divisors. For each divisor, we should check whether it is divisible by any one of the previous y integers. Thus, we can use an array idx[n] to record the maximum index of the given integer that has n as its divisor. When we deal with the current i-th query, we find out each of its divisor x, and check idx[x] to determine whether this divisor satisfies the requirement or not. Next, we update idx[x] = i, since x is divisible by the i-th integer.

Update-1: proof of 112C - Petya and Inequiations

Given a₁ + a₂ + ... + a_n = D where only positive integers are involved and D ≥ n, the maximum value of a₁² + a₂² + ... + a_n² is (n - 1) + (D - (n - 1))² with a₁ = a₂ = ... = a_n - 1 = 1 and a_n = D - (n - 1), i.e., the optimal sequence can have at most one positive integer that is greater than 1.

Proof: We prove this claim by contradiction. Assume that the optimal sequence has more than one positive integer that is greater than 1, and we denote them as x and y, with x > 1 and y > 1. Then, we write s₁ = x² + y² and s₂ = 1² + (y + x - 1)², and one can see that the term s₂ means that we set x = 1 while "moving" a quantity of x - 1 to y. Next, s₂ - s₁ = 1 + (y + x - 1)² - x² - y² = 1 - y² + (y - 1)(y + 2x - 1) = (y - 1)(y + 2x - 1) - (y - 1)(y + 1) = 2(y - 1)(x - 1) > 0. Thus, we have obtained a larger (better) value since s₂ > s₁ and this is contradictory to our assumption, which completes the proof.

110A - Nearly Lucky Number

We can read in the integer as a string, and count the total number of '4' and '7'. As the length of string is at most 18, it is sufficient to check whether the total number is 4 or 7.

110B - Lucky String

One can find that the optimal sequence should have pattern 'abcdabcdabcd...', and thus we can just output the first n letters.

110C - Lucky Sum of Digits

Suppose that the minimum integer has x 4s and y 7s. Then, we have 4x + 7y = n. To construct the minimum integer, we must have x + y as small as possible. If there are multiple such pairs, we should further find the one with the maximum x, which must be unique. After obtaining the optimal (x, y), the minimum integer have a form of 444...777..77.

110D - Lucky Probability

At first, we find out all the lucky integers and sort them in an increasing order. These lucky numbers in fact have divided the interval [1, 1E + 9] into several sub-intervals, whose borders are just these lucky numbers. Suppose that we have m intervals [a₀, a₁], [a₁, a₂], ..., [a_m - 1, a_m], where a₀ = 1, a₁ = 4, a₂ = 7, a₃ = 44, ...a_m = 1E + 9. For any interval [x, y] that contains exactly k lucky numbers, we must have and . Therefore, it suffices to count the number of pairs (x, y) that satisfy the above condition. Equivalently, we can enumerate all the feasible intervals, i.e., [a_i, a_i + 1] and [a_i + k, a_{i + k + 1}], and find out the number of common integers that also appear in [p_l, p_r] and [v_l, v_r].

Moreover, one should take care of one tricky case, i.e., k = 1. As one can see, when k = 1, [a_i, a_i + 1] and [a_i + k, a_{i + k + 1}] have a common integer a_i + 1, which implies that a_i + 1 has been counted twice if it belongs to both [p_l, p_r] and [v_l, v_r]. Therefore, one should decrease the counting result by one if this case occurs.

110E - Lucky Tree

As this is a tree, deleting any edges will divide it into several independent smaller trees. We can first delete all the edges that have a weight of lucky number and then adopt “union and find” to construct the smaller connected components.

We use a_i to denote the number of nodes belonging to the i-th component. Now, instead of counting the required answer, we count the number of triples that do not satisfy the requirements. Note that if we pick all the three nodes from the i-th component, they definitely are against the requirements. This case gives , where all a_i ≥ 3. Next, if we pick two nodes from the i-th component while one node from another different component, this gives , where a_i ≥ 2. Finally, the desired result is n(n - 1)(n - 2) - n₁ - n₂.

109D - Lucky Sorting

If the given sequence is not initially non-decreasing, we need at least one lucky number.

We denote the original sequence and the sorted sequence as a and b, respectively. For each element in a, it appears in b at a unique position. There are exactly n such pairs, and thus we can adopt two arrays to record their relationship. We use atob[i] to denote that the i-th element in a is at position atob[i] in b, while using btoa[i] to denote that the i-th element in b is at position btoa[i] in a. Then, we enumerate each element in array b, and try to move the “required” element to the current position.

If i = btoa[i], it is not necessary to move any element. On the contrary, we should move the btoa[i]-th element to the i-th position. If either one of a[i] or a[btoa[i]] is a lucky number, it takes one “move” to exchange their positions. Otherwise, we can first exchange a[i] with a lucky number at position j, and then move a[btoa[i]] to the i-th position, which costs two “moves”.

From the above operations, one can check that it is always feasible to sort the original array in a non-decreasing order within 2n “moves as long as there is at least one lucky number. Note that whenever we exchange two elements, both atob and btoa should be updated at the same time.

108A - Palindromic Times

Note that for each hour, there either exists a unique answer or no answer. For instance, at hour 14, the answer is 14: 41 while for hour 17, no answer exists.

Therefore, we can first check for the given hour whether there is a feasible answer or not. If no, then we continue to search for the next hour that has such an answer.

108B - Datatypes

We should first sort the array in an increasing order. Then, for every pair of (a_i, a_i + 1) with a_i < a_i + 1, we check whether there exists such an integer x.

The maximum x that can be represented by a_i bits is 2^a_i - 1. Thus, x² = 2^2a_i - 2^a_i + 1 + 1. One can check that x² can always be represented by a_i + 1 bits as long as a_i + 1 ≥ 2a_i.

108C - Dorm Water Supply

According to the description of the problem, the graph in fact consists of several simple rings and single links. Thus, we start enumerating from node 1 to node n and for each node that has no input pipe, we visit all the nodes along the pipes while recording the minimum diameter. Finally, print out the recorded results.

108D - Basketball Team

We denote the number of his teammates as A and the number of the other students as S. Then, the problem can be solved based on the following three cases.

1) A + S < n - 1: this means that there are not enough students;

2) S < n - 1: this means that the probability is absolutely one;

3) none of the above cases: the answer is just . To compute , I usually transform it into F = e^log(F). In other words, we first calculate , and then obtain F = e^f. I think “log” can guarantee better precision than directly mutiplying all the float numbers together.

106A - Card Game

As the problem requires, we first check the suits of the given two cards. If they have the same suit, then we compare their ranks; otherwise we check whether the first card is the the trump card or not.

106B - Choosing Laptop

We can adopt a double loop to eliminate all the outdated laptops. Next, we find the cheapest one as the answer.

106C - Buns

At first, I tried to solve it based on greedy algorithm. However, it turns out that such a greedy algorithm fails since all the involved numbers are integers...

Well, this is essentially a backpack problem, if we implement some equivalent transformation. More specifically, it is a multiple-backpack problem, one can also check the one in 95E - Lucky Country, which is also solved based on multiple-backpack.

106D - Treasure Island

The solution is straightforward implementation. However, trivial implementation ends up with TLE. To avoid this, for each position, we should calculate in previous the farthest position that we can reach when we move to any one of the four directions. This can be computed by using DP algorithm with complexity O(mn).

105A - Трансмиграция

It seems that the difficulty of this problem mainly lies in the precision. Suppose that we are given an integer F and a float number L, and asked to compute the value of ⌊ F × L⌋. One can implement the above calculation based on float numbers, however this might lead to some weird precision problem. Instead, as for this specific problem, one can write L in the fractional form of , where both A and B are integers, and A can be obtained by extracting from the given input while B = 100. With this transformation, ⌊ F × L⌋ can be equivalently calculated as F * A / B, where “/” denotes the “integer division”.

105B - Темная Ассамблея

We use DFS to generate all the feasible patterns of distributing candies. For each configuration, we calculate the probability of winning by enumerating all the possible results of voting. The results of voting can be represented based on bitmasks. For instance, 0011 denotes that the first two people give positive voting while the other two give negative voting.

104A - Blackjack

Determine the result based on each value of n carefully.

104B - Testing Pants for Sadness

We use a[1], a[2], ..., a[n] to denote the given n values. To achieve the maximum number of clicks, it is obvious that we should first choose a[i] - 1 wrong answers and then select the correct one, for every i. For a[i], we have a[i] - 1 wrong answers, and thus we start from 1 to i - 1 for a[i] - 1 times, which gives (a[i] - 1) × (i - 1) clicks. Also remember that i contributes a[i] clicks, and this gives totally (a[i] - 1) × (i - 1) + a[i] clicks before we move to index i + 1. Therefore, we enumerate all the elements, and add the answers together.

104C - Cthulhu

Let us consider what form can such a graph have. There are n nodes and only one circle. This implies that we must have n edges as well, i.e., m = n. Next, after deleting some single edge, we will surely obtain a connected tree. Therefore, we can adopt a double loop to check if we can obtain a connected tree by eliminating some edge. The connectivity can be simply checked by using Union-Find.

I also find that it is sufficient to just check whether the original graph is connected or not, which can reduce the double loop to a single loop.

104D - Russian Roulette

We first consider the case where n is an even integer, and there is only one bullet. It can be seen that all the positions can be divided into two types, even indices and odd indices. The probability of winning is always 0.5 no matter at which type we put the bullet. Now suppose that we have two bullets. One can check that if both two bullets are put at the same type, the winning probability is still 0.5; otherwise, the winning probability is decreased. Thus, we should put the two bullets at the same type. Extending this to a general approach, we should put bullets at the even indices until all the even indices have been used up, and then put them at the odd indices. To achieve the minimum lexicographical order, we should implement the above operations from right to left.

Now we deal with the case where n is an odd integer. For one bullet, we can put it at any position, which always gives a winning probability of . When there are two bullets, the second one should be put at a position with even index so that the winning probability is not decreased. For more bullets, the strategy is similar as the case where n is even. In a word, when n is an odd integer, we should put the first bullet at position n. Then, we put the other bullets at positions n - 1, n - 3, n - 5, ..., 4, 2, n - 2, n - 4, ..., 5, 3, 1.

104E - Time to Raid Cowavans

This is a very very tricky problem.

If we answer the query by exhaustive calculation, the complexity is O(qN). However, note that if all queries have , the complexity is reduced to . On the other hand, if all the queries have , we can previously use DP algorithm to compute the results for all the potential values of b, resulting in a complexity of .

Based on the above observations, we can select one of the two algorithms according to the value of b. We sort the queries in the increasing order of b. For , we use DP algorithm with complexity O(N) to calculate the desired result; otherwise we directly compute the sum. The former operation may be implemented for at most times, which gives complexity while the latter one might be implemented for at most times, which gives complexity . Therefore, the total complexity has been reduced to .

102A - Clothes

We can adopt a triple loop to enumerate all the reasonable combination, and find out the one with the minimum cost.

102B - Sum of Digits

A simple implementation problem. Keep adding all the digits to obtain a new integer, and repeat again until it is reduced to an integer with only one digit.

102C - Homework

At first, we count the number that each letter has appeared in the string. To eliminate the number of different letters as many as possible, it is straightforward to first delete the letter with the minimum number, and then the one with the second minimum number, and then the one with the third minimum number, and so on.

102D - Buses

Although n can be as large as 10⁹, the value of m in fact has determined that at most 2m of the nodes (stops) really affect the result, since the person can only get off the bus at these specified stops.

Thus, we should first compress the number of nodes (or stops) to the order of O(m), which can be achieved by using 'map' of STL in C++. Now we use dp1[k] to denote the number of different ways to get to node k. Furthermore, we maintain a prefix-sum array dp2[k] which have values . For a route from node i to node j, we can calculate . Therefore, to compute any dp1[k], we should find all the routes that can reach node k, and add them together as shown above. Besides, the calculation of dp1[k] should be implemented in an increasing order of k, and do not forget updating dp2[k] = dp2[k - 1] + dp1[k].

102E - Vectors

It is convenient to denote a point P with coordinate (x, y) as P = x + iy, where the complex form is introduced. Suppose that we have implemented several operations, and whatever the order of the two given operations are, they can always be described as repeating the following steps cyclically: first add vector C to vector A for m times, and then rotate the resulted vector for k times (both m and k can have zero values).

Thus, after the first cycle, A becomes (A + m₁C)i^k₁ = Ai^k₁ + m₁Ci^k₁. After the second cycle, it turns out to be Ai^{k₁ + k₂} + m₁Ci^{k₁ + k₂} + m₂Ci^k₂. Note that i^k can only have a form of i or 1. Thus, after several cycles, the resulted vector must have a form of Ai^k + aC + biC, which should be equal to B. This equation is satisfied if and only if both real and image parts are equal, respectively.

Look out for the case where C is a zero vector.

101D - Castle

The main solution consists of two steps.

Step 1. Implement DFS from the root node 1, and during this process, we should compute several variables.

childnode[n]: the number of child nodes that node n has;

total_t[n]: the time consumed to visit all the child nodes of node n while finally returning back to node n;

Step 2. Implement BFS to calculate the required answer. However the order of visiting next nodes should be carefully optimized, which is more complicated than I thought... One can check the tutorials in http://mirror.codeforces.com/blog/entry/2393, and the necessary variables to determine the visiting order has been obtained in the DFS step.

99A - Help Far Away Kingdom

Using C++, there is a simple manner to implement string parsing. For this problem, we can replace '.' with space, and initialize an 'istringstream' type with this modified string. Then, we define two string variables, and initialize them with 'istringstream' as a standard input. The next work is to find the last digit of the first string and the first digit of the second string, and output the answer according to the requirement.

99B - Help Chef Gerasim

Take care of two special cases n = 1, 2. For n ≥ 3, we can find out the maximum and minimum values, denoted as min and max, respectively. Besides, we should find out all the other values that are neither min nor max. If such value is unique, and equal to , the current configuration can be recovered.

99C - Help Victoria the Wise

The complete permutation has 6! = 720 patterns. Therefore, we can compare every one with all the other ones to check whether it results in a unique pattern or not. Now we should figure out how to determine that two patterns are equivalent after some rotation.

As an efficient manner, we can mark the six planes with front, back, up, down, left and right. Then, we fix one plane as the top, and rotate 0, 90, 180, 270 degrees to obtain four equivalent patterns. As there are 6 planes to serve as the top, the total number of equivalent patterns are 6 × 4 = 24.

96A - Football

Count the maximum length of repeated elements, and compare it with 7.

96B - Lucky Numbers (easy) 95B - Lucky Numbers

We store the integer as a string and use L to denote its length. At first, note that if L is an odd number, the answer should be 44...477...7 with 4s and 7s. If L is an even number, we can first compare it with 77...744...4. If the former one is larger, the answer must be 44...477...7 but here both the number of 4 s and 7 s are ; otherwise, it implies that we can always find a required integer with the same length L.

This minimum answer can be found by using DFS (it seems that DFS is an incredibly powerful technique...). The DFS works as follows.

We use s[pos] to denote the digit that we are dealing with at position pos, and use num4 and num7 to denote the number of 4s and 7s that are still not assigned. Initially, .

At first, if num4 > 0, we try to assign 4. If s[pos] < '4', it is obvious that we can safely assign 4 and the final answer is thus straightforward. If s[pos] =  = '4', then we should call DFS again to deal with position pos + 1 with num4 = num4 - 1. If s[pos] = '5', or'6', then we assign 7, and the answer has been determined. If s[pos] =  = '7', then we call DFS to deal with pos + 1 with num7 = num7 - 1. If s[pos] > '7', we should return 'false'.

96C - Hockey

As the strings have small length, we can adopt exhaustive search to find all the positions that should be replaced. We use T to denote the given letter. For each position, if it is not equal to T, we should replace it with T in order to achieve the maximum number of T; otherwise we should further check whether T is 'a' or not. If yes, then we replace it with 'b', and if no, we replace it with 'a'. Be careful that the lower case or upper case should stay the same.

96E - Horse Races

This is a sparse graph, and thus we can implement Dijkstra algorithm based on priority queue with complexity O(ElogE), where E is the number of edges.

With the above arguments, we can implement Dijkstra to every node, and find out all the nodes that it can reach. Then, we can build another new graph with the given cost, and it is sufficient to implement Dijkstra algorithm again to find out the shortest distance between the given starting point and ending point.

95E - Lucky Country

It turns out that this problem has a standard solution. At first, we adopt Union-Find technique to calculate the number of components and also the corresponding sizes. Then, the problem is reduced to a well-known, perhaps referred to as "Multiple-Pack" problem, and one can search a lot of information on the Internet.

94A - Восстановление пароля

A simple problem with straightforward solution. Divide the given string into 8 parts with the same length 10, and convert each of them to a decimal digit according to the provided mapping relationship.

94B - Друзья

Generate all the feasible C₅³ patterns, and check whether there exist any three people that are either known or unknown to each other. The mutual relationship can be represented by the connectivity of graph.

94C - Рамочки

This is a horrible problem...There are a huge number of cases that should be considered. One of the cases that is likely to be ignored is shown as follows:

Suppose that m = 4, n = 100, and a = 3, b = 10. One might give 3 as the answer. However the answer should be 2, since we can first select 3, 4, 7, 8, and then select 5, 6, 9, 10.

94D - Окончание сессии

It turns out that greedy algorithm solves this problem. Assume that we have n segment lines with the same length w, and we put them one after another, i.e., the i-th one starts from the end of the previous one. Next, we have another m segment lines with the same length , and also put them in the same manner as mentioned above.

For each segment line with length w, we check whether it contains more than two segment lines with length . If yes, the answer is NO; otherwise we can further calculate the “contents” in each cup by checking what are included in each of the m segment lines.

Note that if we use “float” types, we may fail obtaining sufficiently precise results, especially under some weird cases. The best choice is to replace all the division with an equivalent multiplication.

94E - Аземблер

At first, I consider using DP to solve this problem. For instance, we can use dp[n] to denote the minimum number of operations to obtain the integer n. We can find out all pairs of (i, j) and coefficients k = 1, 2, 4, 8 so that n = i + k × j holds and dp[n] = dp[i] + dp[j] + 1. However, this fails since dp[i] and dp[j] are dependent under some cases. For instance n = 138, and the optimal decomposition is 138 = 2 + 8 × 17 and 17 = 1 + 8 × 2. Here dp[17] = 2 and dp[2] = 1, and thus dp[138] = 4. However the optimal answer should be 3 since after we obtain 2, the number of operations to obtain 17 is reduced to 1 instead of 2.

It turns out that this problem can be solved by using DFS with powerful branch and bound tricks. In detail, we just keep generating values by using the values that have already been calculated, and assign them to the registers that have not been consumed. When all the registers have been used or we have got the target value n, the call of DFS function should be terminated immediately to significantly reduce the comlexity.

93E - Лостборн

At first we derive the recursive formula. We use f(a₁, a₂, ..., a_k)[n] to denote the target value. Suppose that we have obtained f(a₂, ..., a_k)[n], and to calculate the target value, we should further delete the integers which are divisible by a₁. These integers have form q × a₁, but q is not divisible by any a₂, a₃, ..., a_k, since we have chosen them in such a manner. Moreover, holds, and thus f(a₁, a₂, ..., a_k)[n] = f(a₂, ..., a_k)[n] - f(a₂, ..., a_k)[n / a₁], where “/” denotes the integer division.

With the above formula, we can compute the result based on DFS. For small n, we can calculate f(a₁, a₂, ..., a_k)[n] in previous to reduce the search complexity. Furthermore, we can sort (a₁, a₂, ..., a_k) in a decreasing order in order to decrease “n” as fast as possible, for each call of DFS.

92A - Chips

It can be observed that n people will consume elements. Thus, we should first compute the remainder m%N, and then find out the maximum i so that . The answer is .

92B - Binary Number

This is a simulation problem. We start from the end of the binary sequence, and enumerate the digit one by one. If we meet a “0”, then do nothing; otherwise we simulate the binary addition of adding “1” to the current position. When the sequence reduces to a single “1”, the number of total operations is just the answer.

92C - Newspaper Headline

To construct the second string while using the the minimum number of the first string, we can adopt the greedy algorithm.

Specifically, we maintain a variable S, which is set to  - 1 initially. For any letter appearing in the second string, we should find the same letter in the first string with the smallest index i satisfying i > S. Then, we update S = i. When we can not find the required i, it implies that we have to start from the beginning of the first string again, which will set S =  - 1. This also means that the number of the first string should be added by one.

To implement the above algorithm, we can store the positions of each letter in previous, in an increasing order. Thus, we can use binary search to find out the smallest index i satisfying i > S.

92D - Queue

This is a classic “inversal pair” problem, but asking to find out the farthest “inversal pair”.

The basic idea is using suffix, specifically, suffix minimum index. For the original array a[n], we use b[n] to denote its suffix minimum index, i.e., b[i] gives the index from i to n - 1 so that a[b[i]] is the minimum value among a[i], a[i + 1], a[i + 2], ..., a[n - 1]. Furthermore, as there may exist duplicate values, b[i] should be the maximum index if there are several equal minimum values.

Next, to find the farthest inversal pair of a[i], we can implement binary search among b[i], b[i + 1], ..., b[n - 1] and find out the largest b[j] so that a[i] > a[b[j]] holds. The binary can succeed since b[i] is a nondecreasing sequence.

92E - Ski Base

Well, I can only come up with a “not so strict” proof...

We adopt a variable a with initial value equal to 1. Whenever we find that the currently added edge belongs to a connected component, we multiply a by 2 (remember to calculate the modulo), and output the answer a - 1.

To prove the correctness of the above formula, we divide all the edges into two types S and T, with the former one containing the edges that do not belong to any components while the latter one containing the edges belonging to some component. If we remove all the edges from T, then the graph reduces to several unconnected components, and thus no ski base can be built. As we add edges from T, the graph “begins” to contain at least one component. As we have 2^|T| ways to choose edges from T, we can have 2^|T| - 1 ski bases. The term “-1” comes from the empty case, where no edges from T are selected, since this leads to no ski base.

90A - Cableway

There are at most 300 students, and thus we can directly simulate the whole process, i.e., what happens in each minute. The simulation terminates when no students are left.

90B - African Crossword

The implementation is straightforward. We can enumerate each letter, and only those that appear exactly once in the corresponding row and column should be output.

90C - Robbery

An interesting problem.

Suppose that Δ x elements are taken away. To guarantee that the n - 1 sums keep the same, the changing quantity for each element must be  - Δ x, Δ x,  - Δ x, Δ x, .... Therefore, if n is an even number, it is impossible to take away any elements, since the total sum can not be changed. For an odd number n, it can be seen that to take away Δ x elements, we have to carry out moves. For each minute, at most m moves can be conducted, and thus . Given k minutes, we can carry out at most moves. However, the value m = min(a[1], a[3], ...a[2n + 1]) has provided an upper bound (the index starts from 1), and thus the answer should be min(T, m).

90D - Widget Library

The description is long but it turns out to be a traversal on a q-ary tree, which can be solved by using DFS. One important trick is to store the results that have been obtained at each node to avoid TLE.

90E - Chip Play

The trick is how to find out the next position with constant complexity so that the total complexity is (n × m × n × m). For each position with an arrow, we assign four links to denote the nearest four positions with arrows that it can reach, in left, right, up and down directions, respectively. This process can be completed with complexity O(n × m), by using the prefix and suffix idea.

When we move from the current position to the next one, we should update the links assigned to the four nearest arrows as well, since after moving, the current arrow will disappear. Suppose that the current position is P, and its four links are P[L], P[R], P[U], P[D], denoting that the nearest left, right, up and down arrows. When P disappears, the nearest right arrow of P[L] should be P[R], and the nearest left arrow of P[R] is P[L], and the nearest upside arrow of P[D] is P[U], and the nearest downside arrow of P[U] is P[D].

After the above updating, we can always find out the next arrow with constant complexity. Remember to restore the initial links after every time we complete DFS.

88A - Chord

Given three elements, we can generate all the 6 permutations, and calculate the distance to check which type it belongs to. Note that the distance might be a negative integer and when this occurs, add 12 to convert it to a positive one.

88B - Keyboard

When given an uppercase letter, the basic idea is to enumerate the distance of all the feasible combinations of “Shift” and the corresponding lowercase letter, and check whether there exists any one that satisfies the requirement. However, if we implement the computayion every time the query comes, it may lead to TLE. As there are at most 26 uppercase letters, we can first calculate the distance for each one, and store the results. When a query comes, just take out the corresponding result.

88C - Trains

This problem can be solved by direct simulation. Suppose that a < b, and one can see that after time , the two trains meet each other again, and thus it is sufficient to focus only on this time interval.

We implement the simulation based on the length of b, i.e., we first consider the time interval [0, b], then [b, 2b], [2b, 3b], and so on. There are exactly such intervals. Next, we store and update the starting time of train-a in each interval of length b, and calculate the number of interval of length a that is included. This total length is just the time that train-a will be selected, while the left length belongs to train-b.

The total complexity is about O(max(a, b)).

88D - Vasya and Types

This problem can be solved by straightforward implementation. The key point is to store the number of “*” and “&” for each type and do not forget the case where the type reduces to “errtype”.

88E - Interesting Game

This is a famous game theory problem, referred to as Sprague-Grundy Theorem. One can check the book written by the great master Competitive Programmer's Handbook — a new book on competitive programming for more details.

84A - Toy Army

The strict proof seems to be a little complicated as far as I consider, however an intuitive understanding suggests that the answer is n + n / 2, and it is accpeted...

84B - Magical Array

We must find out all the intervals that consist of the same integers. For an interval with P integers, the number of reasonable subsequences is . Thus, we can adopt two pointers to find out all the target intervals, and calculate the answer.

84C - Biathlon

As it has been guaranteed that no two circles intersect with each other, the given point can only fall into at most one particular circle (one special case is that two circles touch each other at the given point). Thus, we first sort the circles in an increasing order of their X-coordinates, and find out two circles between which the give point falls (check the X-coordinate of the given point as well, and a special case is that the given point falls at one of two ends of all the circles), which can be achieved by using binary search.

Then, the final step is to check which circle it falls inside, or completely outside all the circles.

84D - Doctor

The basic idea is still binary search. We use a[n] to denote the given array. We use binary search to find out the maximum T so that . Moreover, we compute K - S as the remainder. Then, any a[i] that is not larger than T should be firstly eliminated. Next we enumerate the first K - S survived a[j] in the natural order while decreasing them by one, and eliminate those a[i] ≤ T again. Finally, we start from the current position and output the survived indices one by one, by shifting to the right in a circular manner.

84E - Track

I spent about three hours modifying the algorithm to avoid the time limit....The most impressive modification I used is scaling the constant from 1 to . This is the first time that I realized what an important role that a constant can play.

The general idea is to generate all the feasible patterns of maps and find out the one with the minimum distance and order. For instance, if letter 'a' and 'b' can be used, then we will obtain a map where we can move to positions of 'a' and 'b' while the other ones can not be used. With this equivalent map, we can implement BFS from the starting position until the terminating position is reached. During this process, we update the distance and also the minimum order if necessary.

As k can take values up to 4, we may have to check as many as C₂₆⁴ patterns for the worst case. It turns out that this will lead to TLE. Therefore, we have to further reduce the complexity. Instead of beginning from the starting position, we can begin from every one of the four positions that can be reached from the starting position. Each time we select one position, we have determined one letter that must be used and thus the number of feasible patterns is reduced to C₂₅³, which is supposed to satisfy the time limit as I consider.

However, I made a mistake that the number of generated patterns is in fact A₂₅³ rather than C₂₅³. As these two values only differ by a constant of , I did not realize (or believe) that such a constant matters so much. After I correct the mistake, it passed... What a fascinating problem!!

79A - Bus Game

We can directly simulate the process and thus obtain the final result.

79B - Colorful Field

We store the positions of all the “waste” in each row, and also the corresponding number. For each query, we find the right row and check whether it is “waste” or not. If no, then we calculate the total number of waste before this position, which can be obtained with constant complexity if we use prefix technique. Then, we will know the total number of crops and the correct type can be computed according to the remainder obtained by dividing 3.

79C - Beaver

For each of the given n small strings, we can calculate its beginning and ending positions in the long string, where it appears. The above results can be directly computed without using any advanced techniques about string, since the length of small string is quite short.

For each index i in the long string, we store two types of information. We first record the indices of small strings that start from i and their beginning position, specifically in this trival case equal to i. Secondly, we record the indicies of small strings that end at i and their beginning position, which is just i - length(smallstring) + 1.

The left work is to use two pointers technique to calculate the required answer. We use p1 and p2 to denote the beginning and ending positions of the current range that we are observing. At the same time, we record a “set” which contains the small strings belonging to the current range.

When we move p2 forward by one step, we add new small strings (if any) to the set, and check is there any small string ending at p2 are included in the set. If yes, it means that the current range contains at least one small string and thus we should move p1 forward by one step to obtain a new range for the next check. Before p1 is increased, all the small strings that start at p1 should be deleted from the set. If no, we can further move p2 forward to check the next extended range.

As we use “set” in the STL of C++, the updating of set has complexity of O(logN), and thus the total complexity is O(NlogN).

78A - Haiku

Count the total number of “a, e, i, o, u” in each line, and check whether they satisfy the form of “5, 7, 5”.

78B - Easter Eggs

For simplicity, we use 0, 1, 2,...,6 to denote the seven colors. The following pattern always satisties the requirement 012345634563456345634...

78C - Beaver Game

A very interesting problem!!

We use FIRST to denote the player who moves first, and SECOND to denote the other player. If n is an even number, this results in a perfectly “symmetric” situation, and SECOND always wins since he can simply “copy” what FIRST has done. As long as FIRST can succeed cutting the logs, SECOND can also make it.

When n is an odd number, it becomes a little complicated. We write m = XY, where both X and Y are divisors of m, and it also means that the original log of length m has been cut into X new logs with the same length Y. To satisfy Y ≥ k, we should have . If we set X as the maximum divisor that satisfies this condition, then none of the logs of length Y can be further cut. We can prove this by contradiction. Assume that Y can be further cut, which implies that Y = pq, and q ≥ k. Thus, we can obtain a larger X' = Xp, which is impossible since we have set the maximum value to X.

Therefore, FIRST can first cut any original log so that none of the new logs can be further cut. Then, the situation is equivalent to saying that we are given n - 1 (an even number) logs while rightnow SECOND is the first one to move, and thus FIRST wins. Be careful that X cannot be 1, and thus if X = 1, FIRST still loses.

78D - Archer's Shot

A wonderful mathematical problem. We count the number of hexagons column by column. We denote the column that contains the center “A” as the first column. According to the symmetry, it is sufficient to focus on the columns to the right of “A”, inclusively. For each column, we use binary search to find the highest hexagon. Again due to the symmetry, we only need to count the hexagons above “A”.

For the hexagon with height h, we can check two points, the right upper point and the rightmost point, to see whether both of them fall inside the circle or not. If yes, this hexagon is covered by the circle; otherwise not. The left work is to compute the distance of these two points from the center, which needs some simple geometric calculation (using Pythagorean theorem) and omitted here.

80A - Panoramix's Prediction

As the range is quite small, we can directly calculate the next prime integer and check whether it is the same as the given one or not.

80B - Depression

At first, we should note that if the hour is larger than 12, we can decrease it by 12, since they will form exactly the same angles. For instance, 13:26 is equivalent to 01:26. Then, we calculate the angles of minute and hour, respectively. As 60 minutes are equal to 360 degrees, its angle is just M × 6. For the hour, 1 hour or 60 minutes is equal to 360/12 degrees. Thus, the angle of hour is H × 30 + M × 0.5.

80C - Heroes

A little complicated but not quite difficult problem. Enumerate all the feasible divisions of the heroes, and find out first the minimum difference and then the maximum liking.

80D - Falling Anvils

This is a pure mathematical problem. We use f(p) and f(q) to denote the probability density function (pdf) of p and q, respectively. For normal distribution with range [x, y], the pdf is written as . Then, we derive the formula as follows:

We first deal with the first term.

.

Then, it comes to the second term. This should be solved based on the following two cases:

1) 4b < a:

2) 4b ≥ a:

Therefore, for a ≠ 0 and b ≠ 0, we can calculate the answer according to the above formula. For the other cases, the rules are:

1) a = b = 0, the answer should be 1;

2) a = 0, b ≠ 0, the answer is ;

3) a ≠ 0, b = 0, the answer is 1.

80E - Beavermuncher-0xFF

I think this is a nice problem to practice dp based on trees. We use dp[n] to denote the maximum number of beavers that it can eat, under the condition that all the child nodes of node n have been processed and it returns back to node n. Furthermore, we use left[n] to denote the number of beavers that are still at node n, under the above same condition. We need another array beaver[n] to denote the number of beavers at each node at the beginning.

Now, we start implementing DFS from the given root node s. To calculate dp[n], we assume that all the child nodes of n, i.e., dp[m], have been computed (they are obtained when the DFS function returns). Then, we sort all the dp[m] in a decreasing order. If we use M to denote the number of its child nodes that have at least one beaver, then . Moreover, note that we might still have beavers left at both node n and its child nodes, and we should take them into consideration as well. Thus, we should further update .

Be careful that when we call DFS to deal with any child node, we should decrease beaver[m] by 1, since we need at least one beaver to return back!! Also remember to update left[m] with correct values. The DFS function trivially returns when it is a leaf node or it has no beavers at all. Finally, we can output dp[s] as the required answer.

Well, this is a tough round...

74A - Room Leader

The solution is straightforward. Calculate the total points for each user, and output the one with the maximum points.

74B - Train

The following example might give us more intuitive understanding to this problem. Suppose that stowaway is at position 3 while the controller is at 5 and moving to positions with larger indices. If the train keeps moving, the optimal position at which the stowaway should stay is obviously 1. However, the optimal strategy might change if the train stops at some station before the stowaway is caught. When the train stops, the stowaway can first check both the current position and moving direction of the controller, and then find out the next optimal position, just as the above simple example shows.

With the above arguments, we can directly simulate the whole process according to the given string.

75A - Life Without Zeros

This is a "straightforward-implementation" problem. Eliminate all the zeros in each integer and check whether the sum equation still holds or not.

75B - Facetook Priority Wall

The main issue involved in this problem is how to correctly sort out the names and actions. After this, we only need to record the scores that every user can obtain, and output them in the required order.

75C - Modified GCD

At first, we should compute the GCD of the given two integers. As their common divisors must also be the divisors of GCD, the next step is to calculate all the divisors of GCD, and store them in the array S. Then, we sort S in a decreasing order, and for each query, we can directly enumerate S from the last element to the first one while stopping if we find the first element that falls into the interval.

It seems that the above algorithm might lead to a risk of TLE. However, it turns out that the number of divisors of GCD cannot be very large, even if the maximum integer is up to 1E+9. Suppose that one integer only has 2 as its prime divisor. Then, it cannot exceed 2^36, and thus the number of divisors is at most 37. If it has 2 and 3 as its prime diviosrs, the number turns out to be at most 18*18. Furthermore, if it has 2, 3 and 5, the number seems to be less than 10^3. According to these observations, the above enumeration algorithm almost surely works well.

75D - Big Maximum Sum

A well designed problem! We should first implement some pre-calculation before solving it. For the i-th small array a[n], we compute its total sum T[i], the maximum prefix sum P[i], the maximum suffix sum S[i] and the maximum sum of sub-sequence M[i].

For the large array b[m], we use b_end[m] to denote the maximum sum with b[j] as the ending. This can be calculated by the following formula:

1）if b_end[j-1]+T[b[j]]>S[b[j]], then b_end[j]=b_end[j-1]+T[b[j]]

2）otherwise b_end[j]=S[b[j]]

with b_end[0] initialized as S[b[0]].

Then, we enumerate b_end[m] and find out the maximum b_end[j]+P[j]. Note that we should further compare this value with all the M[j] that have appeared in b[m], and find out the maximum one as the final answer.

73A - The Elder Trolls IV: Oblivon

I think there exists a general method to solve any n-dimensional cases. Suppose that we are given n elements, and we denote them as a[0], a[1],.... At first, we calculate k/n (integer division) and k%n. Then, we find out every a[i] such that a[i]-1≤k/n, and denote the number of such elements as NUM. Furthwrmore, we update the following values:

k=k-(a[i]-1), a[i]=1, n=n-NUM

We repeat the above steps until at least one of the following conditions is satisfied:

1. n=0, i.e., no more a[i] can be cut.

2. k=0, i.e., we have no more chances to cut any a[i].

3. k/n=0, i.e., we only need to deal with the left k%n chances.

If k/n=0 but k%n>0, we can just find all the a[i] that satisfies a[i]>1, and update a[i]=a[i]-1 and k=k-1. This operation stops if either k=0 or no more such a[i] can be found.

73B - Need For Brake

This is a very "brain storm" problem. Although only m new scores are given, we can add n-m zeros to obtain a n-length sequence, denoted as S, which is further sorted in a decreasing order. We first try to find the worst rank.

It is obvious that to obtain the worst rank, the target racer should add the minimum value of S. Then, we sort all the racers in a decreasing order, and denote the current rank of target racer as R. For the racers with better rank than R, we should assign the minimum values of S to them, too. Thus, we use a pointer R2 to denote the rightmost position of S, which is still not assigned to any racer. We scan the racers with rank worse than R, and calculate whether it is possible to achieve a better rank if the score with index R2 is added. If yes, we move on to check next racer and update R2=R2-1. Otherwise, we only decrease R2 by one check again. During this process, we should record the number of racers which have better ranks than R, and this is just answer.

Now, we try to find the best rank. We give the target racer the highest score, and sort all the racers again in a decreasing order. For the racers who have better rank than R, we should assign the maximum scores to them, since they have already got better ranks even without any extra scores. We need to introduce another pointer R1 to denote the leftmost position of S which has not been assigned to any racer. Then, we scan the racers with worse ranks, and check whether it is possible to obtain a better rank than R if giving the score at R2. If yes, we in fact should give the score R1 rather than R2 to him, since "he is surely" to achieve a better rank, while updating R1++. If no, we should decrease R2 by one and check again. For this case, we should introduce a variable RES, which is used to denote the number of skipped R2. In fact, the previous opeartions under "YES" is not correct.... Instead, if yes, we should first check whether RES is larger than zero or not. If RES>0, we add R by one while decreasing RES by one; otherwise we update R1=R1+1, and also add the number of racers who have better ranks by one.

73C - LionAge II

This is a standard DP problem. It suffices to use dp[n][z][k] to denote the maximum value under the state of "dealing with the n-th character in the given string, changing this letter to 'z', the number of changed letters being no larger than k". The updating formula is

1) z=s[n], dp[n][z][t]=max(all z', dp[n][z'][t]+weight[z'][z])

2) z!=s[n], dp[n][z][t]=max(all z', dp[n][z'][t-1]+weight[z'][z])

71A - Way Too Long Words

For the given string, if its length is not larger than 10, we shloud output it directly; otherwise we should output the first letter, the length minus 2, and the last letter.

71B - Progress Bar

It can be observed that a reasonable answer must always be writen as x*k+y, where x denotes the number of values that are equal to k while y denotes the unique value which is neither k nor zero. Note that y can be zero.

According to the conditions, we have (x*k)/(n*k)≤(t/100), and thus x≤t*n/100. We can first compute x as t*n/100, where "/" denotes the integer division. Then, we can enumerate y from 0 to k-1, inclusively, to find out the answer.

71C - Round Table Knights

It seems that we have to enumerate all the feasible polygons and their rotation angles to find out the answer, which leads to complexity of O(N^2). However, one can check that if a polygon with M edges is found to be reasonable, then we can always find at least another one polygon with Q edges, where Q is a divisor of M, which is reasonable as well. The reason is simple. As all the M points are reasonable, we can select the first points of every M/Q points to form the target polygon.

Therefore, it is sufficient to test the polygons which have 3, 4, 5, 7, 11, 13... edges. It can be seen that all the integers are prime except for 4. The left work is to find out all the prime numbers from 3 to the given n. There exists a famous algorithm with complexity O(NlogN), and one can search on the internet for more details. I remember that the number of prime integers from 1 to some constant N is O(logN). If I am correct, the total complexity turns out to be O(NlogN).

71D - Solitaire

The solution is straightforward, and one should just follow the steps to calculate the results. However, the coding is fairly complicated....

71E - Nuclear Fusion

This is a nice problem to practice DP based on bitmask technique.

We use an integer i from 0 to (1<<n) to denote the "states". For a bit, "1" means that the corresponding element is used to generate a new element; while "0" means that it has not been used. At the first step, for each state, we take out "1"s and calculate the sum weight that it can achieve. Moreover, for each sum, we store all the states that can achieve this value. Then, we use dp[1<<n][k] to denote that whether it is possible or not to generate the first several target elements, while achieving the corresponding states. The 0-th column of dp is initialized to zero except for the first row, which is set to 1 to indicate that it is possible to generate 0 target element while achieving the all-zero state, i.e., no given elements are used. Then, to update dp[row][col], we first enumerate all the values of dp in column col-1, and find out those with dp[row'][col-1]=1, since only these states are reasonable. Next, we enumerate all the states S that can generate the col-th target element. Note that only those satisfying S & row'=0 should be considered as reasonable states, and this in fact leads to a new state S | row', and thus we should update dp[S | row'][col]=1. Furthermore, we should keep S so that we can backtrace the equation required by the problem.

70A - Cookies

We use a[n] to denote the number of empty cells for a square of size 2^n*2^n. The square of size 2^(n+1)*2^(n+1) can be built from the smaller one of size 2^n*2^n. Moreover, it can be observed that if we divide the larger square into four smaller ones, the left upper, left bottom and right bottom ones are just exactly the same copies of the smaller one, while the right upper one is fully filled. Thus, a[n+1]＝3*a[n]. Note that for the special case n=0, the answer should be 1.

70B - Text Messaging

At first, we find out all the independent sentences, and store them in the same order as they are given. Then, we keep merging the sentences into a message as long as its length does not exceed the requirement. Be careful that if two messages are combined together, the space between should also be counted, while if they belong to different messages, the space must be omitted.

70C - Lucky Tickets

We use rev[i] to denote the integer obtained by reversing i. Next, we use g[i] to denote the GCD of i and rev[i]. Note that i/rev[i] can be further reduced to (i/g[i])/(rev[i]/g[i]), and thus it can be observed that j must be a multiple of rev[i]/g[i].

With the above observations, we can directly enumerate x from 1 to maxx while y from 1 to maxy bit with j=j+rev[i]/g[i]. During this process, once we find that i*j=rev[i]*rev[j], we store j by using the segment tree. Then, we implement binary search to find out the smallest y so that the number of i*j=rev[i]*rev[j] is no less than w. Therefore, we can check the value of x*y and obtain the minimum answer.

Remember to calculate all g[i] and rev[i] previously; otherwise it might lead to TLE.

69A - Young Physicist

Add all the vectors together, and check whether the result is a zero vector or not.

69B - Bets

We first enumerate all the sections, and for each section we check all the players to find the one who participates and has the minimum time to finish this section. Then, for this section, we can just bet on this selected player and obtain the corresponding profit. Finally, we add the profits of all the sections together to obtain the required answer.

69C - Game

This problem is solved by straightforward implementation. One should be careful that whenever a new query comes, we should immediately check whether a new composite element can be obtained. If yes, we should implement this operation and update the results at once.

69D - Dot

I think this is a very nice problem to practice dealing with a game, which two people take turns to play using the optimal strategy.

At first, one can find that it is not necessary to take the "reflection" operations into consideration. When someone first chooses to reflect x and y, it in fact means that he must have been in a losing state. However, the competitor can reflect the coordinates again, and thus it returns to the previous state. In other words, the two reflection operations from different players cancel each other.

Next, for each coordinate (x, y), we assign it with a state, indicated by 'losing and winning', which gives the final result that one player can achieve if he starts to move from this position. For each position, we can obtain all the feasible positions that he can move to according to the given vectors (note that only the positions inside the circle should be viewed as "feasible"). Moreover, if any of them is a losing state, this position should be assigned with winning state, otherwise with losing state. We can start from the initial position and implement DFS to calculate the states. Note that for some position, if all the next positions to which it can move fall outside the circle, it is definitely a losing state, and this serves as the "return condition" in DFS.

This sort of problem in fact has a general solution, which uses BFS rather than DFS. It looks a little like Topological Order. One can check the book in http://mirror.codeforces.com/blog/pllk for more details.

69E - Subsegments

This problem turns out to be quite easy if one uses the "set<>" in STL of C++. When a new element enters the sliding window, we increase the times that it appears by one, while if an element moves out of the sliding window, we decrease it by one. If one element appears exactly once, then we insert it into the set; otherwise we erase it from the set. Sorting is automatically implemented and maintained in set, and thus the maximum value can be obtained at any time with constant complexity O(1). "Insert, erase, sort" are all implemented with complexity O(logN), which leads to a total complexity of O(NlogN).

68A - Иррациональная задача

This problem can be solved by direct implementation as it requires. The main issue involved is the generation of all permutations for some given sequence. As the problem guarantees that all the given integers are different, a simple recursive backtracing algorithm is sufficient. Completing this, we can count the number of integers that satisfy the conditions.

68B - Обмен энергией

This is a very nice problem to practice binary search. Different from the conventional binary search based on index, this one has to deal with "float type", and thus the loop should be terminated by limiting the number of search.

We can directly search the required answer. During each search, we enumerate all the elements and calculate two results, denoted as E_out and E_in as follows. If the element is no less than the current answer, then we add the difference to E_out; otherwise we add the difference to E_in. Note that here the difference is always larger than or equal to 0. Then, we compare whether E_out*(1-k/100) is no less than E_in or not. If yes, it means that the answer for the next loop should be increased; otherwise it should be decreased.

68C - Синхрофазотрон

This problem has given me a deeper understanding of DFS, or backtracing.

We should adopt an array FLOW[n] to denote the fuels that are currently stored at some node, and later these fuels will flow to other nodes. As we start at node 1, we can enumerate all the possible values of fuels that are initially stored at node 1. It is sufficient to begin with 0 and end with 26, since there are at most 5 edges going out from node 1, and each of them is at most 5. The enumeration should be immediately terminated once we have found a reasonable value, since the problem asks to find out the minimum flow.

The DFS function should handle three cases depicted as follows:

1. For some node i, all the nodes to which it directs have already been processed. Then, we check FLOW[i], and if FLOW[i]=0, we should call this DFS function again but start at node i+1;

2. For node n-1, all the nodes that it directs to have already been processed. We should immediately "return" and update the maximum cost;

3. For some node i, we enumerate all the possible fuels X that can flow to some other connected node j, while decreasing FLOW[i] by X and increasing FLOW[j] by X. Then, we call the DFS function for the next node. Remember that after the function returns, FLOW[i] and FLOW[j] should be changed back to their original values.

68D - Дерево полураспада

Although the complete binary tree will have about 2^30 nodes, only a small fraction of them will be used, since the number of queries is limited to 10^5. Thus, we should first use map<int ,int > to compress the indices of nodes that we are going to deal with. Then, the problem can be solved based on the following two steps:

1) Update: We use cost[n] to denote the number of electrons that node-n and all its child nodes currently contain. Whenever a node with some electrons X is added, we find out the path from this node to the root node, and add the same number of electrons to all the nodes involved in this path. In other words, cost[n]=cost[n]+X, cost[n/2]=cost[n/2]+X, cost[n/4]=cost[n/4]+X...

2) Calculate: When a query comes, we calculate the required result, denoted as ANS. If the decay occurs at the first leaf node, we will obtain a component which consists of node-1, node-3 and all the child nodes of node-3 (there are other components, but we first only focus on this one). If the decay occurs at the second leaf node, we will obtain the component consisting of node-1, node-3 and all the child nodes of node-3 again. Besides, it can be seen that if decay occurs at any leaf node with index from [1, 2^(h-1)], i.e., the first half leaf nodes, we will always obtain the component with node-1, node-3 and all the child nodes of node-3. Moreover, we can compute that this special component has a charge of cost[1]-cost[2], while for the other components, it will have charges of at most cost[2]. Therefore, if we have cost[2]<cost[1]-cost[2], it means that if decay occurs at the first half leaf nodes, it will always contribute to the final expectation with 2^(-1)*(cost[1]-cost[2]), i.e., ANS=ANS+2^(-1)*(cost[1]-cost[2]). Thus, we can skip the first half leaf nodes and consider the case that the decay occurs at the second half leaf nodes, i.e., we can move to node-3. On the other hand, if cost[2]>cost[1]-cost[2], it means that cost[3]<cost[1]-cost[3]. This can be proved by using

cost[1]-cost[3]=cost[2]+C(some constant)>cost[2]>cost[1]-cost[2]=cost[3]+C(some constant)>cost[3]

This implies that we can skip the second half leaf nodes, and ANS=ANS+2^(-1)*(cost[1]-cost[3]), and we can move to node-2.

In fact, the problem has been reduced to another one with height h-1, and we can thus repeat the above arguments again. Suppose that we are now at node-3, and thus we should compare cost[3] and cost[3]-cost[6]. However, remember that as we are at node-3 now, and thus the decay should occur at leaf nodes with indices from [2^(h-1)+1, 2^h]. This implies that we will always have a component which consists of node-1, node-2 and all the child nodes of node-2, with charge of cost[1]-cost[3]. We use another variable max_cost to denote this value, i.e., max_cost=cost[1]-cost[3]. This will affect the calculation of ANS. Suppose that cost[3]<cost[3]-cost[6], and then we should compute ANS=ANS+2^(-2)*max(max_cost, cost[3]-cost[6]) rather than directly adding cost[3]-cost[6] to ANS. After this, we should update max_cost=max(max_cost, cost[3]-cost[7]).