157A - Результат игры

Straightforward implementation.

157B - След

Calculate the answer based on whether the given number is odd or even.

157C - Сообщение

One should observe that inserting a letter at any end of the string is always equivalent to the following operation: we insert an auxiliary (or dummy) letter first, for instance “*”, and then replace it with the desired letter. Besides, in fact we will never need implement any deleting operation, since on one hand, it is not necessary to take a longer string and delete some letters to make it have the same length as our target string; on the other hand, if we have taken the string with the same length, for instance, “abcd”, and the target string is “abce”, instead of first deleting “d” and then inserting “e”, we can directly replace “d” with “e”.

According to the above arguments, we can always only use replacement operations to obtain the target string, with the minimum number of modification. Therefore, suppose that the length of the target string is u_l and the given string has length s_l. Then, we insert u_l auxiliary letters, for instance “*”, both to the head and end of string s to obtain a new string s' with length of 2u_l + s_l. Next, we check all the substrings of s' with length u_l and find the one that has the minimum number of different letters corresponding to the same indices. This number just indicates how many replacement operations should be implemented.

157D - Подозреваемые

We should first find out all the potential criminals. We check for each person that if he is the unique criminal, whether there are exactly m true claims. By some simple precalculation, we can find all the potential criminals with complexity O(n).

Then, for each person, we check the result of its claim. For “+i”, there are three possible cases: 1) i is the unique criminal; 2) i is not included in the set of potential criminals; 3) i is not the only potential criminal. Similarly, there are also three cases for “-i”, and omitted here.

We can adopt “set” to store the potential criminals, and thus we can handle any of the above cases with complexity of order O(logn).

157E - Шифр

One can check that no matter how many operations have been implemented, the sum of the string will always be the same. Two strings are equivalent if and only if they have both the same length and the same sum (I did not figure out how to prove this...).

Therefore, we can adopt dfs with memorization. We use dp[i][j] to store the number of equivalent strings that have length i and sum j, while using function dfs(i, j) to denote the number of equivalent strings whose first i letters have sum equal to j. When we reach dfs(i, j), we should recursively call function dfs(i - 1, j - 0), dfs(i - 1, j - 1),..., dfs(i - 1, j - 25), where 0 means letter “a”, and in fact we are enumerating from “a” to “z” for the i-th position (remember to memorize the answers in dp[i][j]).

One could also calculate dp[i][j] in previous, and this is less time comsuming than the above method.

156D - Улики

This turns out to be another classic problem !! One can check Caylay's formula for some preliminaries.

This problem can be viewed as an advanced version of Caylay's formula. For the original version, all the nodes are simple nodes, while in this problem, one node may be a “big node”, which in fact is a connected component.

The proof for this advanced version can be found in the Russian tutorials (I use google translation and I think it works quite well)...

155A - I_love_\%username\%

We should keep updating the maximum and minimum values that we have obtained, and increase the counter according to the requirements.

155B - Комбинация

The main idea is greedy algorithm. We sort the cards in a decreasing order of the number of cards that we can further check, and if the numbers are equal, we sort them in a decreasing order of scores. After sorting, we start from the first card and implement the simulation step by step.

155C - Домашнее задание

Note that any single letter will not appear in more than one constraint, and thus we can deal with the constraints one by one in an independent manner.

Given a constraint, i.e., two letters x₁ and x₂, we can find all the consecutive intervals [l, r] so that only the two letters are included. For each interval [l, r], we also count the number of letter x₁ and x₂ as n₁ and n₂, respectively. It is obvious that we must either delete all x₁ or all x₂, since otherwise we can always find two neighboring letters of x_1x2 or x_2x1. Thus, we should delete the letter corresponding to min(n₁, n₂) for this interval.

155D - Коллайдеры

A key observation is that 100000 < 2 × 3 × 5 × 7 × 9 × 11 × 13, implying that any integer that does not exceed 100000 can have at most 7 (strictly speaking 6) different prime divisors.

Based on the above observation, we can implement sieve function to find out all the prime integers and also the prime divisors that each integer has. Then, when an integer is added, we find all its prime divisors and check whether these divisors have already appeared before or not, to determine whether this integer can be successfully inserted or not. If an integer is deleted, we should delete all their prime divisors at the same time.

In other words, we can maintain multiple sets d[i], so that d[i] (it is a set) contains all the integers which have been added and have such a prime divisor (this implies that i should be some prime integer), and update these sets whenever an integer is inserted or deleted.

155E - Профили-двойники

The idea is a little weird (from the tutorials). The essential issue is to determine whether two sets contain exactly the same integers or not.

We find a prime integer, for instance 29, and assign integer i with a weight 29ⁱ. Then, for some set containing integers (i, j, ...), we compute its hash value as i × 29ⁱ + j × 29^j + ... (if we use “long long int”, the modulo operation is automatically implemented). Two sets are exactly the same if they have the same hash value. For simplicity, we use h[i] to denote the hash value of the set that node i has.

Note that we should check every pair of two nodes. We can divide all the pairs into two types, one containing those which have direct edges, while the other one containing those that do not have direct edges.

For the first type, we can check each of them in the order of given edges. Be careful that we should delete the hash value of the neighboring node from the total hash value.

For the second type, we can sort h[i] in an increasing order, and find out all the intervals of h[i] that have the same value. For instance, some interval contains k same values, and then it contributes to the final answer.

152A - Оценки

Straightforward implementation.

152B - Шаги

It leads to TLE if we implement the simulation step by step. Instead, we should directly compute the farthest position that we can reach for each given vector. Take care of some special cases, for instance, one dimension of the given vector is zero.

152C - Записная книжка

For each column, we can count the total number of different letters as cnt[i]. Then, by some simple observation, one can find that the answer is just .

152D - Рамки

At first, we find out all the rows that have at least three consecutive “#”s. Note that only those rows with the minimum row index, second minimum row index, maximum row index and second maximum row index can in fact serve as the potential parallel sides of rectangles. Then, we deal with columns in a similar manner.

The following work is to enumerate all the feasible combinations of rows and columns so as to construct two rectangles (they may intersect or completely overlap with each other as the problem claims). Then, we compare each obtained board with the given one. If the given board contains two rectangles “correctly”, we will surely find out one single candidate result that is exactly the same as the given one. Otherwise, we can never find out any feasible answers.

152E - Сад

Well, I find that this is a famous topic, referred to as Steiner Tree !! To solve this problem, one has to master several amazing techniques, such as dynamic programming based on bit-mask, SPFA (perhaps short for shortest path faster algorithm) and so on.

One can find a large number of materials talking about this topic on the internet, and even standard frameworks about how to write the codes (as far as I consider).

151A - Газировкопитие

Simply calculate the answer as the sample indicates.

151B - Телефонные номера

A straightforward implementation problem. Take care of the output format.

151C - Победи или замерзни

Note that the player who can not move wins! Therefore, for the initially given integer q, if it is a prime number, the first player wins.

Otherwise, we decompose q = (p₁)^a₁(p₂)^a₂..., where p_i is a prime divisor. If q only has two prime divisors, it is obvious that the second player wins. If q has more than two prime divisors, the first player definitely wins, since he can find any two prime divisors p_i and p_j and write down integer p_i × p_j, and then the second player has to face an integer that has only two prime divisors.

As a general method, we can find a divisor of q, denoted as d, which falls into interval [2, \srqt{q}]. If such d can not be found, the first player wins. Otherwise, we have found two divisors of q, i.e., d and q / d. Then, we test whether both of them are prime integers. If yes, the first player loses. Otherwise, it suffices to find any two prime divisors of q.

151D - Количество строк

One of the methods is the same as mentioned in tutorials. We can start from some simple examples and find out some particular rules (or patterns) for different values of k and n. Then, we compute the answers according to different cases.

Another method is using union-find. Each letter in the string can be viewed as a node, and a palindrome in fact has introduced edges among different nodes. The connected nodes must have the same letter and thus the number of connected components just indicates that we have these “positions” and each of them can be assigned with a number of letters, which is equal to the size of alphabet.

151E - Хитрый жук

The problem asks to find a segment for each passenger so that he and the conductor can earn as much money as possible.

Suppose that the segment [x_i, x_j] is selected. Then, they can save money equal to x_j - x_i = x_i + 1 - x_i + x_i + 2 - x_i + 1 + ..., while might be penalized with an expected amount of money equal to (p_i + p_i + 1 + ...p_j - 1) × c. Thus, the expectation should be (x_i + 1 - x_i - p_i × c) + (x_i + 2 - x_i + 1 - p_i + 1 × c) + .... It can be seen that the expectation can be viewed as the sum of expectation value of each neighboring stop. Therefore, the original problem can be reduced to such one that asks to find a consecutive subsequence which gives the maximum sum (a classical problem).

To solve the reduced problem, we should adopt segment tree since the number of queries is large. The main idea is divide and conquer. Given a sequence with range of [l, r], we divide it into two smaller sequences with ranges of [l, mid] and [mid + 1, r], respectively. For [l, r], the subsequence with maximum sum can only belong to the following three cases: 1) it is completely included in [l, mid]; 2) it is completely included in [mid + 1, r]; 3) it has intersection both with the two smaller sequences, and thus it must be the concatenation of “maximum suffix of the first sequence” and “maximum prefix of the second sequence”.

Therefore, for each node in the segment tree, we should store maximum prefix, maximum suffix, total sum, and maximum subsequence sum. Then, we can build the tree, and answer the queries.

149A - Business trip

First we sort the array in a decreasing order, and calculate the prefix sum. Then, we find the prefix sum with the minimum index that is not less than the target value.

149B - Martian Clock

At first, we find the largest integer in the given sequence, denoted as d_b. Then, we start testing from base d_b + 1 to 70 (it is sufficiently safe to choose any integer that is larger than 60). If there is no feasible base, the answer is 0. If 70 is also a feasible base, the answer is -1 since there must be infinite bases that satisfy the requirements.

149C - Division into Teams

Suppose that all the elements are sorted as a₁ < a₂ < ... < a_n.

If n is even, we can divide them into two groups consisting of (a₁, a₃, ...a_n - 1) and (a₂, a₄, ...a_n), respectively. The proof is that a_n - |(a₂ + a₄ + ...) - (a₁ + a₃ + ...)| = a_n - 1 - a_n - 2 + a_n - 3 - a_n - 4 + ... + a₃ - a₂ + a₁ ≥ 0.

If n is odd, we can divide them into two groups consisting of (a₃, a₅, ...a_n) and (a₁, a₂, a₄, ...a_n - 1), respectively. The proof is similar if one computes a_n - |(a₃ + a₅ + ...) - (a₁ + a₂ + a₄ + ...)|, and thus omitted here.

149D - Coloring Brackets

The main idea is DFS with memorization (I learned from turotials).

We can build a function dfs(l, r, c1, c2), where l, r are the left and right border of the range that we are considering, inculsively, while (c1, c2) are the colors for the brackets at the two borders. Before implementing dfs, we should calculate for each “(”, which “)” matches with it. Note that for the overall sequence, we can divide it into multiple independent subsequences with smaller size. For instance, “(())()()” can be first divided into “(())” and “()()”, and the second part can be further divided into two parts “()” and “()”. This is similar to the idea of divide and conquer, i.e., we divide the original problem into subproblems with smaller size, and solve them seperately, and finally combine their solutions together to obtain the solution to the original problem. This is in fact how our dfs function works. However, trivial dfs leads to TLE due to the huge number of nodes to visit, and thus we should adopt another array dp[l][r][c1][c2] to store the results that we have obtained to reduce the consumed time.

Here are some key issues involved in dfs function.

1) if dp[l][r][c1][c2] already has a value, we immediately return it;

2) if positions l and c correspond to a matched “( )”, we recursively call function dfs(l + 1, r - 1, c3, c4) where c3 and c4 denote the feasible colors for l + 1 and r - 1. Then, by some simple computation, we can obtain the answer. A special case is that l = r - 1 and the answer can be immediately obtained;

3) if brackets at l and r do not match, we find the position at which the bracket matches with that one at l, denoted as m (this implies that m + 1 and r forms another independent subproblem with smaller size), and then recursively call dfs to compute (l, m) and (m + 1, r), respectively.

4) due to the given constraints, some of the combination of colors are infrasible, and thus should not be considered.

149E - Martian Strings

This problem can be solved based on the well known KMP algorithm.

For each of the given small strings, we implement KMP algorithm. During this process, for every prefix substring, we store the minimum index at which it is found in the longer string. Furthermore, we reverse both the long and small string and repeat the above process again. Note that the “reversal” version in fact calculates the maximum index at which every suffix string is found in the long string. Thus, we divide the small string at different positions to obtain a prefix and a suffix, and check that if the minimum index of the prefix does not exceed the maximum index of the suffix, then the current small string can be seen.

148A - Insomnia cure

A straightforward solution is to enumerate every element in the sequence and check whether it can divide at least one of the given four integers.

148B - Escape

We can simply simulate the process until the princess reaches the destinatiin. Be careful that when comparing two “double” types, it is better to use a < b + ε instead of directly checking a < b, where ε can be set to 1e - 9 (I used this value).

148C - Terse princess

A greedy algorithm can solve the problem. The first element can be assigned with value 1. Then, for the next b elements, we assign values so that each of them is larger than the sum of all the previous elements. For the next a elements, each of them should be larger than the maximum value of the previous elements. Finally, we can assign the remaining elements with the same value.

Note that there are two special cases which are quite tricky to a certain extent.

One case is that a = n - 1 (this has implied that b = 0 due to the constraint a + b < n). In fact, there exists no reasonable sequence since the second element must be larger than the first one, however this means that the second element should belong to type “b” rather than type “a” while b = 0 here.

The second case is b = 0, 0 < a < n - 1. A reasonable sequence exists for this case, but be careful to make sure that the second element should not be larger than the first one (same reason as mentioned above).

148D - Bag of mice

I used a classic probability model (I am not sure of the terminology...) to solve it.

Given n = b + w elements, there are totally n! permutation and we are going to find all the patterns that the princess wins. It is convenient to define the “first winning event”, i.e., the step at which the princess wins.

Note that the n elements can be divided into multiple groups, each of which consists of three elements (the last group may have less than three). The first winning event must be one of the following patterns, where “x” means that it can be either “w” or “b”.

wxx xxx xxx ...

bbx wxx xxx ...

bbx bbx wxx xxx ...

....

Suppose that we have g groups and the first “w” appears in the first element of the i-th group, and we are going to calculate its probability p(i). To form such a pattern, we have A_w¹ ways to select the first “w”, and A_b^2i - 2 ways to choose the previous “b”s, and finally (n - 1 - (2i - 2))! ways to deal with the remaining elements (). Thus, we have . In general, it is better to transfer the formula to logarithm domain, i.e., we compute log(p(i)) instead. After some simple deduction, one can find that the main issue is reduced to the computation of log(k!) for some positive integer k. We can calculate it when necessary, which results in complexity of O(N²), or calculate in previous and maintain a table, which gives O(N).

148E - Porcelain

For the i-th shelf, we first consider given that we can select m_i elements, what is the maximum value that we can take. According to the problem, we could select x elements from left and y elements from right, with x + y = m_i. Thus, we can calculate prefix sum and suffix sum, and enumerate every feasible pair of (x, y) to find out the maximum value.

Then, the original problem is reduced to find max(f₁(m₁) + f₂(m₂) + ... + f_n(m_n)), given that m₁ + m₂ + ... + m_n = m, where f_i(m_i) denotes the maximum value given that we can select m_i elements from the i-th shelf.

The reduced problem can be solved based on dp. We use dp[i][j] to denote the maximum value that we can obtain under the condition that totally j elements have been selected from the first i shelves. The recursive formula is dp[i][j] = max_{mi = 0, 1, 2, ..}(dp[i - 1][j - m_i] + f(m_i)). The final answer is just dp[n][m].

146A - Lucky Ticket

We read in the integer as a string and the left work is straightforward implementation.

146B - Lucky Mask

For a < b, the answer is obviously b. If a ≥ b, note that 10⁶ + b is always a potential answer except that it might not be the minimum one. Therefore, we can enumerate integers from a + 1 and immediately terminate the loop if we find the first integer that satisfies the requirement (the loop will surely be terminated since 10⁶ + b provides an upper bound).

146C - Lucky Conversion

Let us compare the two strings position by position, and denote the total number of indices which lead to difference as m. For the first string, its m indices must “contain” m₁ 4s and m₂ 7s, while for the second string, it becomes m₁ 7s and m₂ 4s. To achieve the minimum number of operations, we should swap min(m₁, m₂) 4s and 7s while changing the left max(m₁, m₂) - min(m₁, m₂) from 4s to 7s (or from 7s to 4s). Thus, the final answer is in fact max(m₁, m₂).

146D - Lucky Number 2

Let us first consider what happens when we try to write a sequence. Suppose that we write a 4 first. Then, no 47 or 74 appears until we write a 7 (since one can keep writing 4, which gives 444...). Right now, we have one 47 and zero 74. Next, no more 47 or 74 appears until we write a 4, and now we have one 47 and one 74. By some simple induction, one can find that we always have k 47s and k - 1 or k 74s, i.e., the number of 74s is either equal to that of 47s or one less than that of 47s. Similarly, if we write a 7 first, we either have one more 74 than 47 or equal number of 47s and 74s.

With the above arguments, no reasonable sequence exists if |a₃ - a₄| > 1. Thus, we can solve the problem based on the following three cases.

1) a₃ - a₄ = 1: the pattern must be like (44..444)(4747..47)(77..77). The middle '( )' contains a₃ 47s, while the left and right '( )' contains the remaining 4s and 7s. The reason is that if we insert more 4s into the middle '( )', it is still a reasonable sequence but not the minimum one (obviously we should put as many 4s in the front as possible). The reason is similar why we should not insert more 7s into the middle '( )'.

2) a₄ - a₃ = 1: the pattern should be like (77..777)(7474...7474)(44..44). The middle '( )' should have a₄ 74s and the remaining 7s and 4s are put into the left and right '( )', respectively.

3) a₃ = a₄: the pattern can be either (74)(44..44)(74..74)(77..77)(7) or (44..44)(4747..47)(77..77)(4). For the first one, the first '( )' contains exactly one 74, and the last '( )' should contain exactly one 7, and the third '( )' should contain a₄ - 1 74s, while the remaining 4s and 7s are inserted into the other two '( )'. For the second pattern, the last '( )' has exactly one 4, and the second '( )' has a₃ 47s while the remaining 4s and 7s are put into the other '( )'.

146E - Lucky Subsequence

This problem involves several wonderful techniques.

The main idea is to divide the given integers into two sets, one consisting of unlucky integers while the other one containing lucky integers. We use f(i) and g(i) to denote the number of different ways to select i and j integers from the two sets, respectively. Thus, to select totally k integers, we have ways.

Let us first consider how to compute f(i). It is obvious that f(i) is just equal to the conventional . There is a standard algorithm to compute formula like . By using Fermat's theorem, we can transfer it into ab^p - 2%p. Furthermore, one can adopt fast exponentiation to calculate b^t%p (note that we can calculate all the values of n!%p in previous).

Then, we focus on how to compute g(i). Suppose that there are totally m different lucky integers and the number of the i-th lucky integer is denoted as num[i] (there may exist multiple same lucky integers). Then, we use dp[i][j] to denote the number of ways to choose j different lucky integers among the first i ones. The recursive formula is dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] × num[j], which is similar to pascal triangle, and thus g(i) = dp[m][i]. To obtain num[i], one should implement data compression first, since the data range is huge but the number of lucky integers is less than 1024.

As a summary, the involved techniques are prefix idea, fermat's theorem, fast exponetiation, dp and data compression. This is a delicately designed problem.

145E - Lucky Queries

I read the tutorials and learned an advanced version of segment tree there. One could find a large number of materials about various segment trees and their implementation, either on the internet, or in many blogs posted in codeforces. Here I recommend this solution 1115215, and I think the overall framework is written in a very clear, systematic and standard manner.

144A - Приезд генерала

We should find the maximum value with the minimum index and the minimum value with the maximum index, whose indices are denoted as id1 and id2 (index starts from 0), respectively.

If id1 = id2, it means that all the values are the same and thus no swap is necessary. If id1 < id2, it takes id1 steps to move the maximum value to the first position while n - 1 - id2 steps to move the minimum value to the last position, which gives totally id1 + n - 1 - id2 steps. If id1 > id2, we need id1 + n - 1 - id2 - 1 steps, where the last term  - 1 comes from that when we move the maximum value to the head, the minimum value in fact has been moved one position to the right.

144B - Совещание

The solution is straightforward. We enumerate each point on the four sides, and check whether it is included by at least one circle or not. Note that the four corner points should be checked only once.

144C - Поиск анаграмм

Let us denote the length of the first and second string as slen and plen (these strings are denoted as s and p). It is obvious that if slen < plen, then it is impossible to find any good substrings.

For slen ≥ plen, we only need consider the substrings of s with length plen. It is convenient to imagine that we have a sliding window and move along string s to find good substrings. For any substring of length plen, we use a hash table to store the number of letters that appear there. For simplicity, we use hs[i] and hp[i] to denote the number of letter 'i' appearing in string s and p, respectively. One can check that if for all letter 'i', we have hs[i] ≤ hp[i], then the current substring is good, since the “missing” letters can be obtained by replacing '?'. Otherwise, it is definitely not a good substring, since the “redundant” letters can not be eliminated.

Note that hp[i] can be calculated once for all while hs[i] should be updated whenever we move the sliding window one step forward, which can be implemented with complexity O(1) as only one old letter is removed and one new letter is added. Thus, the total complexity is O(max(slen, plen)).

144D - Ракетные шахты

The main solution contains two parts.

The first part is Dij algorithm based on priority queue, since the given graph is sparse. There are a large number of materials (also codes) describing the detailed implementation and thus omitted here.

For the second part, we should find out all the required points. At first, we check all the nodes and find out all those that have an exact distance l. Then, we enumerate each edge and check whether there exist positions on the edge that also have a distance l. It can be observed that there are at most two positions that have a chance to have a distance l. One is by passing one node while the other one is by passing the other node. Be careful that these two positions may coincide with each other.

144E - Соревнование

For a cell (r, c) that belongs to the secondary diagonal, it can only be reached from cells (i, j) that satisfy r ≤ i ≤ n and c ≤ j ≤ n, which in fact forms a rectangular.

We can enumerate the cells in the secondary diagonal from bottom to top and also maintain a set containing the candidate sportmans that can be selected. Initially, we check row n and only consider the sportmans that belong to row n. We select the sportman that has the minimum column index and if there are multiple such sportmans, we further select the one the minimum row index. Before we move to row n - 1, we should first delete the selected sportman, and then further delete all sportmans belonging to column 1 from the candidate set, while at the same time add the sportmans that belongs to row n - 1 to the set. Then, we move to row n - 1 and repeat the above operations again.

Generally speaking, when we try to find a sportman that should go to cell (r, c) which belongs to the secondary diognal, we should select one sportman from our candidate set (note that it might be empty), and then delete it and also delete all the sportmans that have a column index c while adding sportmans that have a row index r - 1, and then move to the upper row.

In fact this is a greedy algorithm and by some induction one can see that this will result in a reasonable answer. Now we prove that the complexity is O(mlog(m)).

Suppose that the number of sportmans in the i-th row is r_i while in the j-th column is c_j. When we are dealing with cell (i, n + 1 - i), we delete c_{n + 1 - i} sportmans while adding r_i - 1 sportmans. Both the deleting and adding operation can be implemented with complexity O(logm). Thus, the total number of deleting operations is and the total number of adding operations is , which gives .

143A - Помогите Василисе Премудрой 2

We can enumerate the feasible integers (in fact from 1 to 9) at the left upper corner. Once this value is determined, we can immediately calculate the other three integers. Finally, we only need check whether the four integers meet all the requirements or not.

143B - Помогите Тридевятому царству 2

This is a straightforward implememtation problem but one needs take care of some corner cases.

143C - Помогите крестьянину

As A - 1 must be a divisor of n, we can previously compute all the divisors of n and store them in an array. Then, we adopt the first loop to enumerate these divisors, and for each divisor v, we adopt a second loop to enumerate the divisors of n / v. Thus, we can test all the feasible combination of A, B, C, and find out the maximum and minimum values.

143D - Помогите воеводе

It turns out to be a famous problem, referred to as Knight Tour problem. One can find some simple introduction in Wiki.

Without loss of generality, we assume that n ≤ m (otherwise we can swap their values). The solution consists of three cases:

1) n = 1, the answer is always m.

2) n = 2, we can put knights on columns 0, 1, 4, 5, 8, 9, ..., i.e., 4j + 0, 4j + 1 for j = 1, 2, .... After some simple calculation, one can check that we can put at most 2×(m / 4 + min(2, m%4)) knights.

3) n > 2: as there exists a simple knight tour path, we can color the nodes along the path with black and white, in an alternative manner. Then, it is obvious that the answer should be (nm + 1) / 2.

143E - Помогите складовщику

The general idea is using DFS. We focus on the crossing point of “T” and enumerate each cell of the board to check whether this special point can be put there or not. Note that we should also check all the possible rotation (in fact four).

However trivial DFS leads to TLE since the search space is extremely huge. Here are two tricks that can avoid TLE.

1) record the starting position for each recursive call of DFS function: for instance, suppose that we have successfully put a “T” at the current position, and thus for the next recursive call, we should start from the next column (assuming that the enumeration is implemented first row by row and then column by column) or the first column but next row.

2) adopt branch and bound: as we have recorded the starting position for each recursive call, we can immediately calculate how many cells are still not tested, and obtain a trivial upper bound which indicates how many “T”s we can put at most. For instance, suppose that we have put t “T”s and there are still p cells to test. If t + p / 5 is not larger than the current maximum value, the call of function can be immediately terminated (or returned).

141A - Веселая шутка

We can adopt two hash tables to record the total number of letters appearing in the first two strings and the third string, respectively. Then, we check whether the two hash tables are exactly the same or not.

141B - Классики

It is clear that if y%a = 0, it is definitely not inside any square. Otherwise, we first calculate which row does the point fall into, and then the left work is straightforward implementation.

Notice that the squares are infinitely extended from bottom to top, and the figure only serves as a simple illustration.

141C - Очередь

There exists a solution with complexity O(N²logN).

Let us denote the number of taller people standing in front of each person as a[i]. At first, we sort all the people in an increasing order of a[i]. Note that we are going to arrange all the people in this order, and the left work is to assign a reasonable height to eacg person.

We enumerate each person, and find the tallest a[i] people standing in front of him, whose height are denoted as b₁ ≤ b₂ ≤ ... ≤ b_a[i] and increase their height by one while “assigning” him a height of b₁. If this succeeds till the last person is processed, then we have found a feasible answer.

141D - Трамплины

The main idea is to transform the original problem into a shortest path version. Note that only positions like x - p and x + d matter, since for any other two positions, their distance (here, the distance corresponds to the time it costs to move between them) is a constant integer. For more details, one can check the tutorials (I also learned from that).

Besides, I think this is a very wonderful problem to practice several techniques.

1) Data compression: note that the given range is too large to directly store the positions based on arrays. Thus, one should first compress (or “remap”) the given data into smaller range. A neat method has been introduced in the last notes.

2) Dij algorithm based on priority queue: For sparse graph, using priority queue can achieve a complexity of order O(ElogE). I have found a very well written code 1029303, and I think one can check the “spfa” function there.

3) struct and STL in C++: a well designed struct and STL can simplify the relationship among various data and help write neat codes. I think the code 1029303 has also clearly shown how powerful they are.

140A - New Year Table

One should take care of the precision problem. We need an angle θ to “include” a circle with radius r, where . Thus, we can have small circles, which is . To avoid wrong answer caused by precision, we can implement x ≤ y + ε instrad of x ≤ y.

140B - New Year Cards

In fact, we only need fill a table, where the entry in row i and column j denotes the card that is given to the j-th person after the i-th card is obtained. A simple observation is that when the i-th card is obtained, we should first find out the one with the maximum preference, and denote its index as p. It is obvious that this card should be given to every person except for the one with index p. For him, we should give the card with the second maxumum preference. Thus, it is sufficient to find out the cards with the first and second maximum preference, and fill the table with them.

Moreover, we should also keep updating the best card that each person can obtain. To calculate this result, we should first convert the preference sequence of each person into a “rank” sequence, which tells the rank of each card in the preference sequence.

Once completing the above implementation, we can find out the answer for each person column by column. For each column, we can start from bottom to top, and once we find that the entry in the current row is equal to the best card, we can store the row index as the answer and immediately skip to the next column.

140C - New Year Snowmen

The optimal strategy is that we keep updating the number of different sizes, and always select the three balls that have the maximum numbers. Well, I did not figure out the proof...

The above idea can be simply implemented by using a priority queue. However, the data should be compressed in previous since the given range is too large.

I have learned a very neat and general method. For an array a[n], we first copy all the elements to another array b[n] as a backup. Then, we sort a[n] in an increasing order, and set m = unique(a, a + n) - a, after which m will be equal to the total number of unique elememts (“unique” can be found in STL of C++). Finally, we implement id = lower_bound(a, a + m, b[i]) for every b[i] (“lower_bound” also belongs to STL of C++). After the above steps, in fact we have already mapped b[i] to a smaller number id.

140D - New Year Contest

There exists a greedy solution.

We sort the given sequence in an increasing order. Then, we keep updating the prefix sum and the current problem can be successfully submitted as long as the corresponding prefix sum does not exceed 720. For each problem with a prefix sum that is not larger than 360, its penalty time is zero; otherwise, it contributes a penalty time which is equal to the difference between 360 and the corresponding prefix sum.

The greedy solution can be proved by a standard scheme, which can be found in many books.

139A - Petr and Book

We can first calculate the total number of pages that can be finished within one week. Then, we divide the total number of pages by this number and obtain the residual. Finally, for this residual, we find the last day on which the whole book is finished.

139B - Wallpaper

The description seems a little difficult to understand...

We should first rotate the wall papers with 90 degrees so that the stripes are vertical. Then, we cut it into as many pieces as possible according to the height of the room. Next, we compute the total length that these pieces can cover, and finally obtain the number of rolls that is necessary to decorate the whole room.

139C - Literature Lesson

A straightforward implementation problem, but one needs take care of “corner” cases.

139D - Digits Permutations

This is in fact an exhaustive search problem.

At first, we enumerate the number of 0s at the end. Then, we enumerate all the combinations of the first sum that is equal to 10, counting from right to left. Finally, we find all the digits that have sum equal to 9. This algorithm has complexity O(10N), and we only need record the maximum number of consecutive 0s among all the enumeration and the corresponding combination.

139E - Mushroom Gnomes - 2

I think this is a very nice problem to practice segment tree with lazy propagation. One can find a lot of materials on the Internet about this technique, and one could also read chapter 28 in book Competitive Programmer's Handbook — a new book on competitive programming, which provides many detailed descriptions and talks about how to implement it.

Besides, there is still one important issue that should be considered. We should be very careful of precision problem. Instead of directly using probability domain, it is better to convert it into logarithm domain, since this can in general achieve a better dynamic range by replacing multiplication with addition. However, if the probability is zero, log(0) will lead to an exceptional case. To avoid this, we can aasign, for instance,  - 1000 instead of log(0).

It took me about one year to complete about 100 virtual rounds.

I learned a lot of techniques that I had seldom read in books or even never heard of before, like segment tree with lazy propagation, bit-mask dp and so on.

In the early stage, I could only solve about two div2 problems. As time goes on, I found that I could solve more and even all div2 problems, either on my own or by reading tutorials.

I also got familiar with a lot of IDs as I kept participating in more virtual contests. At first, I competed with them together in div2 but they improved quite fast and went to div1, and as it turns out, they are legends now. But I guessed that before legends become legends, they had similar experiences like us, too, facing challenges, keeping practicing, handling various problems, and making progress day by day.

This makes me believe more deeply, that hard working may not be sufficient to achieve one's target, but is at least surely necessary.

Best wishes to everyone's dream, and please never lose hope.

(Finally, I strongly recommend this book Competitive Programmer's Handbook — a new book on competitive programming, written by a great master, and hope that everyone can find something valuable there.)

137A - Postcards and photos

We scan the sequence from left to right, and count the number of consecutive 'C's and 'P's. For each such subsequence of length m, it contributes m / 5 + (m%5! = 0) to the final answer.

137B - Permutation

We adopt a hash table to record the integers that have been appearing in the sequence. Then, the answer is just the number of integers that are not stored in the hash table.

137C - History

We sort the events in an increasing order of their beginning time. Then, we scan the events from the last one to the first one, and for each one we check whether it can be completely covered by any other event. We denote the ending time of the i-th event in the sorted sequence as a[i]. It is obvious that only the first i - 1 events can completely cover it, and thus it suffices to check whether there is such an index j < i that a[j] > a[i]. Equivalently, we can check max_{j = 0, 1, ..., i - 1}a[j] > a[i]. Therefore, we adopt a prefix array to record the maximum a[m] for j = 1, 2, ..., m, and problem is solved.

137D - Palindromes

A DP problem. At first, we use p[i][j] to denote the minimum number of changes we need to convert the substring starting from i while ending at j, to a palindrome, which can be computed with complexity O(n²).

Next, we consider how to describe the rules of dividing the original string into shorter ones with '+', since this helps determine the recursive formula of DP. Suppose that we are going to add m '+'s, and these '+' are always added from left to right. For instance, given that 'abcdefg' has been divided into 'ab'+'cdefg', if we will add another '+', then it can only added among 'cdefg' but 'ab' can not be divided any more. It can be shown that with this rule, the original string can always be divided into any shorter ones and thus no potential answer will be missed.

Now, we use dp[i][j] to denote that we have added i '+'s and the i-th '+' is at position j, and the minimum number to convert these substrings (the ones before j) into palindrome ones is dp[i][j].

Then, for state dp[i][j], it can transfer to states dp[i + 1][j + nextj], where j + nextj > j and j + nextj ≤ n, and dp[i + 1][j + nextj] = min(dp[i + 1][j + nextj], dp[i][j] + p[j + 1][j + nextj]). Also, we should record the “paths” so that we can trace back the division pattern.

137E - Last Chance

The main idea is that for each position i, we calculate the longest substring that satisifes the requirement. We use p[i] to denote the total number of vowels in the first i positions.

At first, for any substring of length len, we transfer v ≤ 2c into 3v ≤ 2len. Then, for any position i, we should find out the maximum index j ≥ i so that 3(p[j] - p[i - 1]) ≤ 2(j - (i - 1)), which is equivalent to 3p[j] - 2j ≤ 3p[i - 1] - 2(i - 1). Therefore, we could build a segment tree based on 3p[j] - 2j. For any node in the tree, it stores the minimum value of its two child nodes (like a minimum heap). Then, for each i, the maximum j can be computed with complexity O(logN), by traversal from top to bottom (it is also possible that no j exists). Finally, we only need scan all the positions and find the maximum length.

136A - Подарки

A simple inverse-mapping problem.

136B - Тернарная логика

It is similar to binary case, and one should just compute the module based on 3 instead of 2.

136C - Замена

We first sort the array and then check the largest value a[n - 1]. If it is 1, then we just change it into 2; otherwise, we change it into 1 and sort the modified array again.

136D - Прямоугольник и квадрат

Consider all the possible division of the given 8 points, which should be 8!, and check whether we can find a feasible pattern that meets the requirements. Now, the main issue is how to determine that four points form a rectangular or square. At first, we find two neighboring sides and check whether they form a 90 degree, which can be achieved by computing their inner product. Then, we find the two pairs of oppisite sides, and check that whether the two sides belonging to each pair are the same or not. Furthermore, if all of them are the same, it is a square.

136E - Ноль-один

We denote the player who plays first as v and the other one as u.

After some observation, one can find that v will always try to remove 1 from left to right while u tries to remove 0 from left to right. At first, we consider the case that the given zero-one sequence does not contain any '?' and has an even length in order to illustrate the essence behind the solution.

If the number of 0s is larger than 1s, then it is obvious that the final result is 00; on the other hand, if we have more 1s than 0s, then the final result should be 11.

If the numbers of 0s and 1s are exactly the same, then we might have 01 or 10 as the final result. One can check that if the last bit is 1 then it must be 01 since no one can take away the last 1. Similarly, the final result is 10 if the last bit is 0.

Now, we generalize the above idea. At first, we consider the case where the length is odd. In fact this can be simply converted to the even case, as long as we add an extra 0 and exchange their moving order. Secondly, we consider the sequence containing '?'. This is in fact quite similar to that containing no '?'. We check whether we can have more 0s, or more 1s, or equal 0s and 1s, by converting '?' into 0s or 1s properly.

133A - HQ9+

If the given string contains the required characters except for '+', the answer is yes.

133B - Unary

We can construct the binary sequence according to the requirement, and then calculate its value in decimal form.

133C - Turing Tape

Inverse the binary form and then compute the value...

133D - Piet

This is in fact a straightforward implementation problem, but we should complete some pre-processing in order to avoid TLE.

The main issue that might lead to TLE is that we have to move to one of the four corners within one group. One group may consist of many squares with the same color, and according to DP and CP pointers, after we enter such a group, we must first determine the corner and then move to the next square (or group). This sub-problem can be solved based on DP algorithm. For instance, we use dp[0][i][j] to denote that if we are in the i-th row and j-column and facing to the right, then we should move to position dp[0][i][j], which assembles the prefix or suffix idea. Similarly, we implement the same pre-processing for the other three directions.

133E - Logo Turtle

This problem can be solved by adopting a three dimensional DP. We use dp[i][j][0] and dp[i][j][1] to denote the maximum distance that we can reach, under the state that we have completed the first i commands, and implememted j changes, while facing to the right and left, respectively. For dp[i][j][0], it can transfer to states dp[i + 1][j + nextj][0] and dp[i + 1][j + nextj][1], where nextj ≥ 0 and j + nextj ≤ n. The detailed formula of dp[i][j][0] can be represented as follows, while dp[i][j][1] can be derived in a similar manner.

1) the i + 1-th command is 'F' and nextj is an even number: dp[i + 1][j + nextj][0] = max(dp[i + 1][j + nextj][0], dp[i][j][0] + 1)

2) the i + 1-th command is 'T' and nextj is an odd number: the same as 1)

3) the i + 1-th command is 'F' ans nextj is an odd number: dp[i + 1][j + nextj][0] = max(dp[i + 1][j + nextj][0], dp[i][j][1])

4) the i + 1-th command is 'T' and nextj is an odd number: the same as 3)

However, it is still not done here, since the maximum distance may be “negative”. In other words, we can achieve the maximum distance by moving to the left. Thus, we should implement DP again, but replace max with min. After all of the above steps, we will finally obtain the answer.

132D - Constants in the language of Shakespeare

Well, I searched on the Internet and found that it can be solved with a greedy algorithm. Nevertheless, I did not figure out how to prove it...

We start from the right bit and move to left. We will always try to find a subsequence consisting of consecutive 1s. If there is only one 1, we should assign a  + 2^ to this position; otherwise, we should assign a  - 2^ instead, while deleting these consecutive 1s but changing the next 0 into 1, which indicates that we add a  + 2^ to that position, temporarily.

We give s=10011011 as a simple example. We scan from right to left and first find 11. Then, we assign  - 2⁰ and modify it as s=10011100, and find 111. Now, we assign  - 2², and change it into s=10100000. Next, we assign  + 2⁵ and  + 2⁷. As a result, we obtain  - 2⁰ - 2² + 2⁵ + 2⁷.

131A - cAPS lOCK

Modify the letters as the problem requires.

131B - Opposites Attract

We use a[i] to denote the number of a non-negative integer i while using b[i] to denote the number of a negative integer  - i (i > 0). For any positive integer i, we have min(a[i], b[i]) choice, while for i = 0, we have choice. Thus, the final answer should be .

131C - The World is a Theatre

We enumerate all the feasible combination of boys and girls, and only consider those that satisfy the requirements. Then, the main issue is to calculate . Although n is not larger than 30, it is still difficult (or infeasible) to compute n!. Thus, we modify the formula as , which could handle all n ≤ 30.

131D - Subway

The solution is first DFS, and then BFS.

At first, we implement DFS to find the unique cycle and all the nodes on the cycle. Then, we implement BFS with all of these nodes as the starting state, and update the distance of each node. One can find plenty of materials about how to find the cycle based on DFS.

131E - Yet Another Task with Queens

There exists a solution with complexity of O(m). We first enumerate all the queens, and update three values for each row. The first value is the total number of queens in the current row; the second value is the position of the leftmost queen; the third value is the position of the rightmost queen. Then, we enumerate all the queens again. For any queen in the i-th row, if the total number of queens in this row is less than or equal to 1, then no queen could threaten it; otherwise, there will be exactly one or two queens that could threaten it, depending on whether it is the leftmost one or the rightmost one, which can be checked with complexity O(1) since we have stored the positions of the leftmost and rightmost queens.

Similarly, for each column, we update three values as well. The first value is the total number of queens in the current column; the second value is the position of the top queen; the third value is the position of the bottom queen. The following operations are almost the same as done when we deal with rows.

Finally, we deal with the diagonals of  + 45 and  - 45 degrees, respectively, and the answer is thus obtained.

131F - Present to Mom

The idea is that we use exhaustive enumeration to deal with one dimension while using “two pointers” to deal with the other dimension, which gives a solution of complexity O(n³).

We use dp[i][j] to denote the total number of stars from column 1 to column j, for the i-th row. Then, we enumerate all the feasible two boundaries of columns. For each combination, we adopt two pointers p1 and p2, both starting from 0, and move p2 downwards while letting p1 chase after p2. This behaves like a sliding window, and we modify its position and size so that it contains t stars, where t is the minimum integer that is not less than k. During this process, we update the answer.

129A - Cookies

We can compute the sum of all the integers. Then, we enumerate each element and test whether their difference is even or not.

129B - Students and Shoelaces

A straightforward implementation problem. We can use BFS to find out all the nodes whose degree is exactly one. The answer is just the total number of BFS.

129C - Statues

Note that at the eighth second, all the positions are definitely safe. Therefore, it is sufficient to check whether we can survive within the first eight seconds. One feasible solution is to record and update all the safe positions at each second. If we can survive after eight seconds, it means that we can always reach the right upper corner; otherwise not.

129E - Games with Rectangle

In fact we might obtain some more clear observation if we consider the length and width of each rectangular in an independent perspective. For instance, for the length, the rectangulars can only have positions at (1, 2, 3,... n-1). As there are exactly k rectangulars, we should select 2k positions, which gives C_n - 1^2k different patterns. Similarly, for the width we have C_m - 1^2k patterns as well, and thus the final answer should be C_n - 1^2k × C_m - 1^2k. C_p^q can be calculated by using Pascal triangle.

127A - Wasted Time

A straightforward implementation problem. Calculate the total distance and then the average time.

127B - Canvas Frames

For each integer i, we denote its total number as a[i]. Note that only a[i] / 2 (integer division) of them can be used to construct a frame. Thus, the total number of frames that can be built is .

127C - Hot Bath

This is also an implementation problem, but we should take care of the following issues:

1) several special cases like t₀ = t₁ should not be omitted;

2) to find the pair (y₁, y₂) so that the temperature is closet to t₀, it is better to use “integer computation” rather than “double computation”, since the latter one may meet some weird “precision trap”.

127D - Password

The problem can be solved based on the well known KMP algorithm. Specifically, we use the array next[i] in KMP (one can find a lot of details about this on the Internet).

At first, we check next[n]. If it is zero, it means that the answer is definitely “just a legend”; otherwise, we check all next[i] with i = 2, 3, ...n - 1. If at least one of them is equal to next[n], we just find the answer. If there is no such index, we should further check next[next[n]]. If it is zero, it implies that the answer is still “just a legend”, which can be proved by contradiction; otherwise, we just find the answer again.

127E - E-reader Display

It turns out that the problem is not that difficult if we have noticed the following rules.

We first focus on the right upper corner point, (1, n). It can be seen that this point only depends on whether there is a command (1, n). Thus, by observing this point, we can determine this command. Then, we move to point (1, n - 1), and it depends on both the commands at point (1, n) and (1, n - 1). As we have known the command of point (1, n), we can immediately determine the result of (1, n - 1) as well. Similarly, we move to point (1, n - 2) and use the above arguments again.

In general, we enumerate rows from 1 to n, and for the i-th row, we enumerate columns from n to i + 1. After this, we have determined the command at all the points (i, j) with i < j. Then, we enumerate rows from n to 1, and for each row we enumerate columns from 1 to i - 1. After this, we have determined the command at all the points (i, j) with i > j. Finally, we enumerate points (i, i) from i = 1 to i = n and determine the command at points (i, i).

126D - Fibonacci Sums

Although n is up to 10¹⁸, in fact it is sufficient to consider the first 100 Fibonacci integers, since it increases at the order of about 2ⁱ.

We write the Fibonacci sequence as f[i] = (1, 2, 3, 5, ...) also adopt an array a[i] which is initialized with zero. For the given integer n, we find the maximum Fibonacci integer that is not larger than n as f[j] and then set a[j] = 1. Next, we set n to n - f₁ and repeat this process until n is reduced to zero. For instance, if n = 13, we have a[i] = (00000100...), while for n = 7, we have a[i] = (0101000...).

Then, let us consider a[i]. For (00001), we can change it into (00110) and further into (11010). Thus, we adopt another array h[i], which denotes the number of consecutive zeros to the left of index i. For instance (00001001), we have h[5] = 4, h[8] = 2 while the other values are zero (indices start from 1).

Finally, we use dp[i][0] to denote the total number of decomposition under the condition that the i-th 1 in array a[i] is changed into zero; while use dp[i][1] to denote the total number of decomposition under the condition that the i-th 1 is not changed into zero. The recursive formula is dp[i][0] = dp[i - 1][0] * ((h[i] + 1) / 2) + dp[i - 1][1] * (h[i] / 2) and dp[i][1] = dp[i - 1][0] + dp[i - 1][1].

124A - The number of positions

Enumerate all the integers i and find out those that satisfy both i - 1 ≥ a and n - i ≤ b.

124B - Permutations

Generate all the feasible permutation patterns and find out the one under which the difference between the maximum number and the minimum integer is the smallest.

124C - Prime Permutation

We divide the positions into the following sets. A₂ = (2, 4, 6, ..., 2m₁), A₃ = (3, 6, 9, ..., 3m₂), A₅ = (5, 10, 15, ..., 5m₃),...

One can see that for any prime integer p > 2, A_p always has at least one common position with A₂, as long as the index 2p does not exceed the range. Thus, we find out the maximum such prime integer p', and then count the total number of different positions belonging to sets A₂, A₃, ...A_p'. These positions must have the same letters, while the other positions can have any letter. Therefore, the left work is to determine whether we have enough number of the same letter.

124D - Squares

We first focus on the first condition and consider y = 0. One can see that the bad points are distributed on the X-axis with distance 2a. After increasing y to 1, 2, ... + ∞ , one can find that the bad points form multiple lines with  - 45 degrees. Similarly, the second condition results in multiple lines with  + 45 degrees.

As a result, the bad points have divided the whole plane into infinite grids. To get from the starting point to the ending point, we have to cross several (maybe zero) grids. The answer is just the least number of grids that we have to cross. In fact, this is quite similar to the Manhattan Distance. We consider the lines with  + 45 and  - 45 degrees as the “X” and “Y” axis, respectively. Then, we can calculate the manhattan distances of the two points, along the “X” and “Y” axis, as D_x and D_y. The answer is max(D_x, D_y).

124E - Brackets

I read the tutorials and I think the ideas behind this problem is really very amazing. It needs quite strong insight to reduce the problem to single dimension, which is not that straightforward, at least for me. I think I should work harder to improve my insight.

122A - Счастливое деление

Generate all the divisors and check whether at least one of them is a lucky number or not.

122B - Счастливая подстрока

This is an implementation problem. As the length of the string is quite small, every step can be trivially implemented, without any worrying of TLE.

122C - Счастливая сумма

Instead of directly computing each next[i], we previously find out all the lucky numbers, and equivalently enumerate the lucky numbers. The total number of lucky integers that are less than 10⁹ is about 1024, and we can use bitmask to generate all of them. Nevertheless, we still need one more lucky integer, i.e., 4444444444, which is the value of next[i] for all i > 777777776. It is obvious that for any integer i between two lucky integers, next[i] is always equal to the second lucky imteger. Therefore, we can calculate how many integers belong to the interval of two neighboring lucky integers, and update the answer.

122D - Счастливое преобразование

Let us see what happens when we meet the first “47”. If it is changed into “44”, then we can move on to find the next “47”. If it is changed into “77”, then we should check the digit before this “77”. If it is not “4”, then we can move on again; otherwise we have “477” now. It can be seen that we will get stuck into a loop, i.e., we should change “477” into “447” while later change it back into “477” again. For this case, the final result depends on whether the number of operations is odd or even.

122E - Счастливая перестановка

To find the k-th lexicographic small permutation, it is sufficient to consider the last 13 digits, since 13! > 10⁹. Then, the main issue is to find out the k-th lexicographic small permutation. There is a standard algorithm to solve this problem, referred to as Cantor Expansion, and one can search a lot of information and materials on the Internet.

119A - Эпическая игра

The solution is straightforward. We iterate between a and b to compute the GCD with n. Then, we decrease n with the corresponding value until n is reduced to zero, which also determines the winner.

119B - Перед экзаменом

We keep calculating the average points of each provided combination, and updating the maximum and minimum values. Then, for the left theorems, we check whether we can still select some of them to form a new eaxm (perhaps this is the main tricky issue). If yes, we update the maximum and minimum values again.

119C - Реформа образования

We use dp[n][m][w] to denote the maximum total value, under the condition that the n-th day is assigned with the m-th task while the the m-th task has points node[m].a + w. We use node[i] as a struct that has node[i].a, node[i].b and node[i].c as its elements, which have the same meanings as the problem mentions.

The updating of dp[n][m][w] is a little different from what I have known before. For instance, to compute some dp function f[n], we usually deduce its relationship with f[i] for i < n, and update f[n] from small indices to large indices. Once we “visit” f[n] for the first time, its value is determined, and will never be changed.

However, for this dp function, we start from some dp[n][m][w] and visit next potential states, perhaps with several times, and keep updating their values until they will never be visited any more. Specifically, from dp[n][m][w], we can move to dp[n + 1][m + i][w'], which means that for the n + 1-th day, we can select any one of the m + i-th task (i > 0) that have points node[m + i].a + w'. Note that some of the states perhaps can not be reached, since it requires that the next point x_i must be either x_i + 1 + k or x_i + 1 × k, while x_i should also be included in the given interval.

Generally speaking, from each determined state, we move to its next potential states and keep updating their values. At the same time, we record the transition between every two neighboring states.

118A - String Task

This problem can be solved by the following three steps. Firstly, change all the letters into lower case ones. Secondly, remove all the required letters. Thirdly, add “.” in front of each survived letter.

118B - Present from Lena

Take care of the number of spaces that should be output before each digit.

118C - Fancy Number

We can enumerate all the digits, and for each digit d, we replace several original digits so that there exist at least k digits which are the same. To achieve the minimum cost and also the minimum lexicographic order, we should replace digits in the order of d (this can be viewed as a trivial case), d + 1, d - 1, d + 2, d - 2, and so on. The replacement should be stopped once we have obtained k same digits.

To simplify the implementation, for each digit, we can also record how many of them should be replaced. Finally, we implement the replacment. However, here we should be very careful. Suppose that the original digit t is replaced with d. If t < d, then we should replace digit t from right to left; otherwise we should do it from left to right, so that we can achieve the minimum lexicographic order.

118D - Caesar's Legions

The solution is DP. Let us use a[n][m][e] to denote the number of all the feasible patterns that have e type-1 people standing at the end of the line one after another, while the total number of type-1 and type-2 people are n and m, respectively. Similarly, we use b[n][m][f] to denote the total number of feasible patterns that have f type-2 people standing at the end of the line.

The recursive formula is as follows:

The initialization should be done as follows:

a[0][m][m] = 1, for all m < k₂

a[n][0][n] = 1, for all n < k₁

118E - Bertown roads

We can start from any node, and implement DFS. During this process, when we are visiting a node a and enumerating its “child” (since this may not be its true child node) node b, if b is still not visited, we add a directed edge from a to b. If b has been visited but its “child” nodes are still not fully visited, then we add a directed edge from a to b as well. If b has been visited and all of its “child” nodes have also been visited, then we do nothing, since this edge must have been assigned with a “direction”.

After the above operations, we in fact have established a directed graph. Then, we check whether it is strongly connected or not, which can be done by inversing all the direction of the edges and implement DFS again.

The last step is to prove that if the above obtained directed graph is not strongly connected, then it is impossible to construct any strongly connected directed graph. Well, I did not figure out a strict proof. But from an intuitive understanding, if the constructed directed graph is not strongly connected, it implies that there is at least one bridge edge, and thus it is impossible to establish any strongly connected graph.

117A - Лифт

At first, note that it takes 2m - 2 minutes for the elevator to go up from the first floor to the top and return back, and we refer to this event as a “cycle”. Thus, for each query, we can compute the floor on which the elevator stops at time t_i.

Now, the left work should be done very carefully. For instance, we should determine whether we can catch the elevator within the current cycle, or we have to wait for another cycle. Moreover, after we get into the elevator, we should determine whether we can reach the target floor within the current cycle, or wait for more one cycle.

117B - Очень занимательная игра

If we denote the first and second integer as x and y, then the integer after concatenation can be represented as x × 10⁹ + y.

Thus, we should check whether 10⁹x%mod = (mod - y)%mod could hold or not. It is obvious that if b ≥ mod - 1, then the above equation can always be satisfied, since (mod - y)%mod can take any value from {0, 1, 2, ..., mod - 1}. If b < mod - 1, then (mod - y)%mod can only take values of {0, mod - 1, mod - 2, ...mod - b}. Therefore, we can enumerate x from 1 to mod - 1, and find the first (also the minimum) integer that can satisfy the equation. Note that it is not necessary to test any x that is larger than mod - 1.

117C - Цикл

If there is no cycle, then it is obvious that no cycles of length 3 exist. On the other hand, there must be at least one cycle of length 3.

We denote the cycle as a₁, a₂, ..., a_n, and check a₁, a_i, a_i + 1, where i is initialized with 2, and increased to n - 1. As this is a cycle, there is an edge from a₁ to a_i, and also en edge from a_i to a_i + 1. We obtain a length-3 cycle if there is an edge from a_i + 1 to a₁. However, if this edge is from a₁ to a_i + 1, then we increase i to i + 1, and check the next three nodes. This construction will always find out a tuple that achieves our target, since this is a cycle, and there must exist at least one node that has an edge directed to a₁.

116A - Tram

The solution is straightforward. It is sufficient to record the number of people in the tram, and find out the maximum value.

116B - Little Pigs and Wolves

This turns out to be a simple problem if one has noticed that there exists at most one wolf around any pig. Thus, it is not necessary to consider the case where some single pig can be eaten by multiple wolves. We can enumerate each wolf and check whether there is at least one pig around it.

116C - Party

We can find that there are multiple connected components, and then implement DFS or BFS to each component, starting from the node which does not have any superior nodes, to calculate the maximum depth. This is just the required answer.

116D - Lawnmower

Note that once we move to the lower floor, we can never return back. Thus, we must clean up all the weeds on the current floor, and then move downstairs.

For each floor, we denote the positions of the leftmost weed and the rightmost weed as pl and pr, respectively. Then, suppose that we reach the current floor at some position p. No matter which direction we are facing to, the minimum distance that we need to move is either |p - pl| or |p - pr|, and finally we stay at either pl or pr. Now, we find the next floor that has at least one weed (note that there might be several floors without any weeds during our moving).

After finding the next floor, we can find that we should move from the previous position to the leftmost weed or rightmost weed in “horizonal” direction, according to whether we face to the same direction or not. The above calculation resembles the Manhattan Distance, whose horizational distance and vertical distance can be independently computed.

116E - Plumber

Well, I think this is really a brain-storm problem. When I finally understand the tutorials, I feel that I have seen a new world...

Let us first consider that we have 1 × m empty cells. If we only focus on the horizonal pipelines, it can be seen that the pattern can only be either “LRLRLRLRL...” or “RLRLRLRLRL...”, where “R” means that the pipeline is connected to the right side while “L” means that the pipeline is connected to the left side. For the vertical pipelines, we have 2^m patterns, since they will never lead to “leaking” states.

Now, we extend the above case to 2 × m empty cells. Based on similar arguments, for the horizonal pipelines, we have 2² feasible patterns since we have two rows. For the vertical pipelines, one can check that for each column we always have “UD” and “DU”, two patterns, where “U” and “D” denote that the pipeline is connected to the upper and bottom side, respectively.

In general, with n × m empty cells, the answer is 2(m + n). If there are several cells that are not empty, then the patterns of the row and column to which these cells belong in fact have been determined. Suppose that the number of rows and columns that are fully empty is totally t, and then the answer will be 2^t. Note that the previously filled cells might have already led to “leaking” states, and thus for this case the answer should be zero.