Edit (Jan 22, 2:45 AM UTC): Added Div1E and the editorial is now complete. I am sorry for the delay.

Edit (Jan 21, 9:45 AM UTC): Added the explanation for Div1C/2E, and the problem setters' codes. Div1E will need several more hours. Thank you again for your patience.

First, here are some statistics on this round:

Division	Registrants	Participants	A Accepted	B Accepted	C Accepted	D Accepted	E Accepted
1	1364	572 (*)	294	199	8	113	1
(Estimated number of AC by me)			800 (wrong)	500 (wrong)	70 (FAIL)	90 (ok)	5 (wrong)
2	4016	2028	1355	945	41	5	0

(*) Where did the remaining 792 people go? :)

We are sorry for terribly underestimating the difficulty of the problems (except Div1D), especially Div1A/2C and Div1C/2E.

Div.2 A: 505A - Подарок мистера Китаюта

[Problem] Given a string, turn it into a palindrome by inserting one letter or state that it is impossible.

(Problem by evima)

Since the string is short (at most 10 characters), you can simply try every possible way of inserting a letter ("where" and "what" to insert), and check if the resulting string is a palindrome.

The writer's code (C++): 9501249
Note: For some strange reason, we (contest managers) cannot submit solutions so that everyone can see them. PraveenDhinwa told us how to do so. Thank you!

Div.2 B: 505B - Цветной граф мистера Китаюта

[Problem] Given an undirected graph whose edges are painted in colors, process the queries of the following form:

• Given two vertices u_i and v_i, find the number of the colors that satisfies the following condition: the edges of that color connect u_i and v_i (possibly indirectly).

(Problem by hogloid)

Since neither the graph nor the number of queries is too large, for each query you can simply count the number of the "good" colors (the colors that satisfies the condition) by checking if each color is "good". To do that, you can perform Depth First Search (or Breadth First Search) and verify whether you can reach v_i from u_i traversing only the edges of that color. If you prefer using Union-Find, it will also do the job.

The writer's code (DFS, C++)
The writer's code (Union-Find, C++)

Div.2 C / Div.1 A: 505C - Мистер Китаюта, охотник за сокровищами

[Problem] Since it is hard to summarize this problem, please refer to the official statement.

(Problem by yosupo)

Below is the explanation from yosupo, translated by me.

[From here]

Let m be the number of the islands (that is, 30001). First, let us describe a solution with time and memory complexity of O(m²).

We will apply Dynamic Programming. let dp[i][j] be the number of the gems that Mr. Kitayuta can collect after he jumps to island i, when the length of his previous jump is j (let us assume that he have not collect the gems on island i). Then, you can calculate the values of the table dp by the following:

• dp[i][j] = 0, if i ≥ m
  (actually these islands do not exist, but we can suppose that they exist and when Mr. Kitayuta jumps to these islands, he stops jumping)
• dp[i][j] =  (the number of the gems on island i)  + max(dp[i + j][j], dp[i + j + 1][j + 1]), if i < m, j = 1
  (he cannot perform a jump of length 0)
• dp[i][j] =  (the number of the gems on island i)  + max(dp[i + j - 1][j - 1], dp[i + j][j], dp[i + j + 1][j + 1]), if i < m, j ≥ 2

This solution is unfeasible in terms of both time and memory. However, the following observation makes it an Accepted solution: there are only 491 values of j that we have to consider, which are d - 245, d - 244, d - 243, ..., d + 244 and d + 245.

Why? First, let us find the upper bound of j. Suppose Mr. Kitayuta always performs the "l + 1" jump (l: the length of the previous jump). Then, he will reach the end of the islands before he performs a jump of length d + 246, because
d + (d + 1) + (d + 2) + ... + (d + 245) ≥ 1 + 2 + ... + 245 = 245·(245 + 1) / 2 = 30135 > 30000. Thus, he will never be able to perform a jump of length d + 246 or longer.

Next, let us consider the lower bound of j in a similar way. If d ≤ 246, then obviously he will not be able to perform a jump of length d - 246 or shorter, because the length of a jump must be positive. Suppose Mr. Kitayuta always performs the "l - 1" jump, where d ≥ 247. Then, again he will reach the end of the islands before he performs a jump of length d - 246, because
d + (d - 1) + (d - 2) + ... + (d - 245) ≥ 245 + 244 + ... + 1 = 245·(245 + 1) / 2 = 30135 > 30000. Thus, he will never be able to perform a jump of length d - 246 or shorter.

Therefore, we have obtained a working solution: similar to the O(m²) one, but we will only consider the value of j between d - 245 and d + 245. The time and memory complexity of this solution will be O(m^1.5), since the value "245" is slightly larger than .

This solution can be implemented by, for example, using a "normal" two dimensional array with a offset like this: dp[i][j - offset]. The time limit is set tight in order to fail most of naive solutions with search using std::map or something, so using hash maps (unordered_map) will be risky although the complexity will be the same as the described solution.

[End]

The writer's code (memoized recursion, C++)

Div.2 D / Div.1 B: 505D - Технология мистера Китаюта

[Problem] Given an integer n and m pairs of integers (a_i, b_i) (1 ≤ a_i, b_i ≤ n), find the minimum number of edges in a directed graph that satisfies the following condition:

• For each i, there exists a path from vertex a_i to vertex b_i.

(Problem from evima)

Let G₁ be the directed graph built from the input, and G₂ be a directed graph that satisfies the given conditions. What we seek is the minimum number of edges in G₂. Also, we say that two vertices u and v in a directed graph are "weakly connected" if we can reach v from u by traversing edges, not considering their directions.

If a pair (u, v) is present in the input, then vertices u and v must be weakly connected in G₂. Therefore, for each weakly connected component (abbreviated to wcc) in G₁, the vertices in that component must also be in the same wcc in G₂. We can "merge" multiple wccs in G₁ and create a larger wcc in G₂, but for now, let us find the minimum number of edges required in G₂ for each wcc in G₁ when we do not "merge" them. There are two cases to consider:

1. If a wcc in G₁ does not have cycles, then we can perform topological sort on that wcc, and we can make a "chain" (see the image below) using the topological order to satisfy the conditions. We need (the number of the vertices in the wcc)  - 1 edges, which is the minimum required number since any connected graph with V vertices has at least V - 1 edges.
2. If a wcc in G₁ has cycles, then topological sort cannot be applied. We need at least (the number of the vertices in the wcc) edges this time, since any connected graph with V vertices and V - 1 edges is a tree, which does not contain cycles. Actually, this number (the number of the vertices in the wcc) is always achievable by connecting the vertices into a "ring" (see the image below), thus it is the minimum required number that we seek.

We have found the minimum required number of edges for each wcc in G₁ when we do not "merge" them. Let us show that "merging" wccs in G₁ do not reduce the number of required edges. Suppose we combine k( > 1) wccs C₁, C₂, ..., C_k in G₁ into one wcc C in G₂. Again, there are two cases to consider:

1. If none of C₁, C₂, ..., C_k contains cycles, then C will need |C₁| + |C₂| + ... + |C_k| - 1 edges. However, if we do not combine them, we will only need (|C₁| - 1) + (|C₂| - 1) + ... + (|C_k| - 1) edges in total, which is fewer.
2. If some of C₁, C₂, ..., C_k contain cycles, then C will need |C₁| + |C₂| + ... + |C_k| edges. However, if we do not combine them, we will need
   (|C₁| - noCycles(C₁)) + (|C₂| - noCycles(C₂)) + ... + (|C_k| - noCycles(C_k)  ≤ |C₁| + |C₂| + ... + |C_k| edges
   (here, noCycles(C_i) is 1 if C_i do not contain cycles, otherwise 0), thus combining them does not reduce the number of required edges.

Thus, we do not need to combine multiple wccs into one wcc in G₂ in order to obtain the optimal solution. That is, the final answer to the problem is the sum of the minimum required number of edges for each wcc in G₁, when they are considered separately.

As for the implementation, detecting cycles in a directed graph with 10⁵ vertices and edges might be a problem if this is your first encounter with it. One possible way is to paste a code that decomposes a graph into strongly connected components. If the size of a strongly connected component is more than one, then that means the component contains cycles.

The writer's code (strongly connected component decomposition, C++): 9501202

Div.2 E / Div.1 C: 505E - Мистер Китаюта против бамбука

[Problem] Since it is hard to summarize this problem, please refer to the official statement.

(Problem from yosupo)

Below is the explanation from yosupo, translated by me.

[From here]

Let us begin by applying Binary Search. The problem becomes: "is it possible that all the bamboos are at most X meters after m days?" It is complicated by the fact that the height does not become negative; the excessive decrease will be wasted. We have found two approaches to this problem.

• Solution 1

Mr. Kitayuta must beat the i-th bamboo at least max(0, ⌈(h_i + m·a_i - X) / P⌉) times (let this number t_i). Actually, it is not necessary for him to beat it more than this number of times. Thus, let us assume that he beat the i-th bamboo exactly t_i times. Also, for each j (1 ≤ j ≤ t_i), find the day d_i, j such that, if the j-th beat on the i-th bamboo is performed before day d_i, it will be no longer possible to keep the i-th bamboo's height after m days at most X (it can be found by doing simple math). If Mr. Kitayuta can beat the bamboos under this constraint, all the bamboos' heights will become X meters or less after m days. Otherwise, some bamboos' heights will exceed X meters.

The time complexity of this solution will be , if we first calculate only t_i, then if the sum of t_i exceeds km, we skip finding d_i, j (the answer is "NO").

• Solution 2

This problem becomes simpler if we simulate Mr. Kitayuta's fight backwards, that is, from day m to day 1. It looks like this:

[Problem'] There are n bamboos. At the moment, the height of the i-th bamboo is X meters, and it shrinks a_i meters at the beginning of each day. Mr. Kitayuta will play a game. He can use Magic Hammer at most k times per day to increase the height of a bamboo by p meters. If some bamboo's height becomes negative at any moment, he will lose the game immediately. Also, in order for him to win the game, the i-th bamboo's height must be at least h_i meters after m days. Is victory possible?

Below is an illustration of this "reverse simulation":

This version is simpler because he is increasing the heights instead of decreasing, thus we do not need to take into account the "excessive decrease beyond 0 meters" which will be wasted. Let us consider an optimal strategy. If there exist bamboos whose heights would become negative after day m, he should beat the one that is the earliest to make him lose. Otherwise, he can choose any bamboo whose height would be less than h_i meters after day m. Repeat beating the bamboos following this strategy, and see if he can actually claim victory.

The writer's implementation of this solution uses a priority queue, and its time complexity is .

[End]

The tester's code (Solution 1, C++): 9501229
The writer's code (Solution 2, C++)

Div.1 D: 506D - Цветной граф мистера Китаюта

[Problem] Given an undirected graph whose edges are painted in colors, process the queries of the following form:

• Given two vertices u_i and v_i, find the number of the colors that satisfies the following condition: the edges of that color connect u_i and v_i (possibly indirectly).

Note: this is the exact same problem as Div.2 B except the constraints, which are 10⁵ instead of 100.

(Problem from hogloid)

Below is the explanation from hogloid.

[From here]

For each color, make a new graph that consists of the edges of the color and vertices connected by the edges. Make UnionFind for each graph, and you can check whether a color connects vertex A and B , using it. For each query, find a vertex which has smaller degree(let this vertex A, and the other vertex B) For each colors such that a edge of the color connects to A, check whether A and B is connected by the color. After answering the query, memorize its tuple — (A, B, answer). If the same query is requested, answer using this information.

This will lead to solution.

For each query, the complexity is (For each color connects A, find a vertex of B of the color & check whether they are connected) The queries that require longest computing time are, to ask every pair among vertices which have largest degrees. Let the indices of the vertices be , and degrees of the vertices be d₁, d₂, ...d_k. Now, let's fix vertex B as i. The total computing time of the queries such that B is vertex i is
.
Vertex B can vary from 2 to k. Hence, the total complexity is at most . This complexity is at most .

By the way, in C++, using unordered_map, total complexity would be .

[End]

There will be many other solutions. I will briefly explain one of them which I think is typical.

Let c_i be the number of colors of the edges incident to vertex i. The sum of all c_i does not exceed 2m since each edge increases this sum by at most 2. Thus, there will be at most 450 values of i such that c_i ≥ 450 (let B = 450). We will call these vertices large, and the remaining ones small. Using O(m / B·m) = O(m² / B) time and memory, we can precalculate and store the answer for all the possible queries where at least one of u_i and v_i is large, then we can immediately answer these queries. For the remaining queries, both u_i and v_i will be small, therefore it is enough to directly count the color that connects vertices u_i and v_i in O(B) time. The total time required will be O(m² / B + Bq). If we choose , we can solve the problem in time.

The writer's code (the first solution, C++)
The tester's code (the second solution, C++): 9501240

Div.1 E: 506E - Подарок мистера Китаюта

[Problem] Given a string s and an integer n, find the number of the palindromes that can be obtained by inserting exactly n letters into s.

Note: Div.2 A is a similar problem, where n is fixed to 1.

(Problem from evima)

First of all, let us note that we are asked to count the resulting palindromes, not the ways to obtain them. For example, if we are to insert "b" into "abba", there are 5 possible positions, but only 3 strings will be produced ("babba", "abbba" and "abbab"). Rather than trying to count the ways of inserting a letter n times and removing the duplicated results, we should directly count the resulting palindrome. To do that, let us reformulate the problem:

[Problem'] Given a string s and an integer n, find the number of the palindromes of length |s| + n (let this number be N) that contains s as a subsequence (not necessarily contiguous).

Consider constructing a palindrome from both ends, and matching it to s from both left and right. For example, let s = "abaac" and N = 11. Let us call the final resulting string t. We first decide what letter to use as t₁ and t₁₁ (they must be equal in order for t to be a palindrome). Let us say 'c' is chosen. Now, we have to construct the remaining part of t, that is, t₂..t₁₀, so that t₂..t₁₀ contains "abaa" as a substring (note that the 'c' at the end of s is discarded). Again, we decide what letter to use as t₂ and t₁₀. This time we choose 'a'. Then, we have to construct t₃..t₉, so that it contains "ba" as a substring (this time the two 'a's at the both ends of s are discarded). We choose t₃ = t₉ = 'c'. Next, we construct t₄..t₈, so that it contains "ba" as a substring (this time s remains unchanged). We choose t₄ = t₈ = 'b'. Then, we construct t₅..t₇, so that it contains "a" as a substring. We choose t₅ = t₇ = 'a' (it is becoming repetitive, isn't it?). The last part of t, that is, t₆, has no restriction (this time we choose a letter for only one position of t, not two). We choose 'd', and we have obtained a palindrome "cacbadabcac" that contains s = "abaac" as a subsequence.

This problem is mostly about analyzing this process carefully.

The most naive solution other than literally enumerating all palindromes of length N would be the following Dynamic Programming: let dp[i][left][right] be the number of the palindromes t that can be obtained if you have already decided the leftmost and the rightmost i letters (2i in total), and the substring s_lefts_left + 1..s_right of s remains unmatched. Each value in this table can be computed in O(1) time. Of course, since i can be up to ⌊n / 2⌋ (n ≤ 10⁹), this solution is far from our goal.

Notice that the transitions from dp[i] to dp[i + 1] are the same regardless of i, thus we can calculate the table by matrix exponentiation. However, since there are O(|s|²) possible pairs for (left, right), we will need time, which is actually worse than the naive calculation considering that |s| can be up to 200.

This is where we need to observe the process which we have gone through at the beginning more carefully. Let us build a automaton corresponding to the process (the image below).

(*) An self-loop with a number means that there are actually that number of edges.

A process of producing a palindrome of length N that contains s as a subsequence corresponds to a path of length ⌈N / 2⌉ from the upper-right vertex to the lower-left vertex. Each red vertex has 24 self-loops since the letters at the both ends of the remaining part of s is different, which correspond to two non-self-loop transitions. Similarly, each green vertex has 25 self-loops since the first letter and the last letter of the remaining string is the same, and the blue vertex, the destination, has 26 self-loops, as there are no more non-self-loop transitions available.

Here is an important fact: there are not so many possible combination of (n24, n25), where n24 and n25 are the number of times a path from START to GOAL visits a red vertex (with 24 self-loops) and a green vertex (with 25 self-loops), respectively. Why? Each time we leave a red vertex, the length of the remaining unmatched part of s decreases by 1, since exactly one of the two letters at the ends of the remaining part is matched and discarded. Similarly, each time we leave a green vertex, the length of the remaining string decreases by 2, since both of the two letters at the ends are matched and discarded. There is a exception, however: if the length of the remaining string is 1, then it will be a green vertex, but in this case the length will decrease by 1. Thus, for any path from START to GOAL, n24 + 2·n25 will be equal to either |s| or |s| + 1. If we fix n24, then n25 will be uniquely determined by n25 = ⌈(|s| - n24) / 2⌉. Since n24 can only take the value between 0 and |s| - 1, there are at most |s| possible pairs of (n24, n25).

With this fact, we are ready to count the paths: let us classify them by the value of n24. For each possible pair of (n24, n25), let us count the number of corresponding paths. To do that, we divide each paths into two parts: first we count the number of paths from START to GOAL, using only non-self-loop transitions. Then, we count the ways of inserting self-loop transitions into each of these paths. The product of these two numbers will be the number that we seek.

The first part is straightforward to solve: let dp[left][right][n24] be the number of paths from the vertex that corresponds to the substring s_lefts_left + 1..s_right, visiting exactly n24 red vertices using only non-self-loop transitions. Each value of the table can be found in O(1) time, thus the whole table can be computed in O(|s|³) time, which is fast enough for the input size (|s| ≤ 200).

The main obstacle will be the second part. For example, let us consider the case where s = "abaac", N = 11, n24 = 2, which corresponds to the example at the beginning. From the fact we found earlier, n25 = ⌈(|s| - n24) / 2⌉ = ⌈(5 - 2) / 2⌉ = 2. Thus, we have to insert ⌈N / 2⌉ - n24 - n25 = 6 - 2 - 2 = 2 self-loop transitions into this path (the image):

The order in which red, green and blue vertices appears in this path does not affect the number of ways of insertion, and can be arbitrary. The number of ways to insert 2 self-loop transitions will be equal to the number of the path of length ⌈N / 2⌉ = 6 from START to GOAL in this automaton (we have to take into account the non-self-loop transitions in it), which can be calculated by matrix exponentiation.

Are we done? No! Consider the case s = "abbb..(|s| - 1 times)..bb". There are |s| - 1 possible values of n24 (n24 = 1 corresponds to the case where you match and discard the 'a' first, and n24 = |s| - 1 corresponds to the case where you keep the 'a' until s becomes "ab"). Thus, you need to perform matrix exponentiation |s| - 1 times, which results in a total of time, which will be too much under the given constraints.

There is still hope, though, and here is the climax. Notice that these automata are very similar to each other, and they differ only in the number of the red and green vertices. We can combine these automata into one larger automaton like this (the image):

The combined automaton should have |s| - 1 red, ⌈|s| / 2⌉ green and ⌈|s| / 2⌉ blue vertices.

By performing matrix exponentiation on this automaton instead of many small automata, we can find all the required value in time, which should be enough. We recommend speeding up matrix multiplication by noticing that the matrix will be upper triangular (6 times faster on paper), since the time limit is not so generous (in order to reject solutions).

The problem is almost solved, but there is one more challenge. When N is odd, the situation becomes a little complicated: as we have seen at the beginning, in the last (⌈N / 2⌉-th) step of producing a palindrome we choose a letter for only one position of the resulting string, that is, the center of that string. In other words, the last transition in the path in the automaton we have first built must not be one from a green vertex with a string of length 2 (for example, "aa") to GOAL.

Let us find the number of the paths that violates this condition and subtract it from the answer. As previously mentioned, for each path n24 + 2·n25 will be equal to either |s| or |s| + 1, and if we fix the value of n24, n25 will be uniquely determined by n25 = ⌈(|s| - n24) / 2⌉. If |s| - n24 is odd, then it means that the last non-self-loop transition is one from a green vertex with a string of length 1, therefore in this case no path will violate the condition. If |s| - n24 is even, then the last non-self-loop trantision is from a green vertex with a string of length 2, thus the paths that does not contain the self-loop from GOAL to itself violate the condition. It will be equal to the number of the paths of length ⌈N / 2⌉ - 1 from START to the vertex just before GOAL, which can be found in a similar way to the second part of the solution.

The journey has finally come to an end. Actually, it is also possible to solve this problem in time without matrix exponentiation, but this margin is too small to explain it. I will just paste the link to the code.

The writer's code (matrix exponentiation, C++): 9501164
The writer's code (without matrix exponentiation, C++): 9501177

Congratulations again to Petr who was the only participant to solve this problem in 108 minutes. Also, I would like to give a special mention to rng_58, who was VERY close to solving it in only 63 minutes. He was just one byte away from getting AC (compare 9460984 and 9465440)!



If you find a possible error, or have a question, please feel free to ask here. Alternative solutions are also welcome.