First of all, sorry for the late editorial. I was too exhausted and immediately went to bed after the round finished, and didn't write the editorial.

There are many pictures in this editorial, to cover up my poor English skills! If you have detected any errors or have questions, feel free to ask questions by comments. Unfortunately, the authors only know English, so we can't answer you if you write comments in Russian.

500A - New Year Transportation

Let's assume that I am in the cell i (1 ≤ i ≤ n). If i ≤ n - 1, I have two choices: to stay at cell i, or to go to cell (i + a_i). If i = t, we are at the target cell, so I should print "YES" and terminate. If i > t, I cannot go to cell t because I can't use the portal backwards, so one should print "NO" and terminate. Otherwise, I must go to cell (i + a_i).

Using this method, I visit each cell at most once, and there are n cells, so the problem can be solved in linear time.

What is test 13?

There are 9 pretests in this problem. There are no test where n = t holds in pretests. Many people didn't handle this case, and got hacked or got Wrong Answer on test 13.

• Time: O(n)
• Memory: O(n) (maybe O(1))
• Implementation: 9335683

500B - New Year Permutation

It seems that many contestants were confused by the statement, so let me clarify it first. Given a permutation p₁, p₂, ..., p_n and a n × n-sized binary matrix A, the problem asks us to find the lexicographically minimum permutation which can be achieved by swapping two distinct elements p_i and p_j where the condition A_i, j = 1 holds. (From the statement, permutation A is prettier than permutation B if and only if A is lexicographically less than B.)

Let's think matrix A as an adjacency matrix of a undirected unweighted graph.

If two vertices i and j are in the same component (in other words, connected by some edges), the values of p_i and p_j can be swapped, using a method similar to bubble sort. Look at the picture below for easy understanding.

Because all the two distinct vertices in the same component can be swapped, the vertices in the same component can be sorted. In conclusion, we can solve the problem by the following procedure.

• Find all the connected components.
• For each component, sort the elements in the component.
• Print the resulting permutation.

The size limit is quite small, so one can use any algorithm (DFS/BFS/..) for as many times as you want.

• Time: O(n²) — because of the graph traversal. O(n³) is okay because of small constraints.
• Memory: O(n²)
• Implementation: 9335689 (.o.)

What is test 15? There are too many wrong answers in this case.

Actually, I made the pretests very weak in order to make many hacks. As mentioned in the Hack me! post by kostka, just swapping the elements greedily could pass the pretests easily. There were 14 pretests, and I made test 15 an counter-example of such algorithm in order to reduce judging time, and it seems that most of the wrong submissions failed in this test case :D

500C - New Year Book Reading

In order to calculate the minimum possible lifted weight, we should find the initial stack first. Let's find the positions one by one.

• First, let's decide the position of book b₁. After day 1, book b₁ will be on the top of the stack, regardless of the order of the initial stack. Therefore, in order to minimize the lifted weight during day 1, book b₁ must be on the top of the initial stack. (so actually, in day 1, Jaehyun won't lift any book)
• Next, let's decide the position of book b₂. (assume that b₁ ≠ b₂ for simplicity) Currently, b₁ is on the top of the stack, and it cannot be changed because of the procedure. Therefore, in order to minimize the lifted weight during day 2, book b₂ must be immediately below book b₁.

Considering this, we can find the optimal strategy to create the initial stack: Scan b₁, b₂, ..., b_m step by step. Let's assume that I am handling b_i now. If b_i has appeared before (formally, if ), erase b_i from the sequence. Otherwise, leave b_i. The resulting sequence will be the optimal stack.

You should note that it is not necessary for Jaehyun to read all the books during 2015, which means the size of the resulting sequence may be smaller than n. The books which doesn't appear in the resulting sequence must be in the bottom of the initial stack (obviously). However, this problem doesn't require us to print the initial stack, so it turned out not to be important.

In conclusion, finding the initial stack takes O(n + m) time.

After finding the initial stack, we can simulate the procedure given in the statement naively. It will take O(nm) time.

• Time: O(nm)
• Memory: O(n + m)
• Implementation: 9335694 (.o.)

500D - New Year Santa Network

The problem asks us to calculate the value of

Let's write it down..

So, we need to calculate the value of . I'll denote the sum as S. How should we calculate this?

For simplicity, I'll set node 1 as the root of the tree. Let's focus on an edge e, connecting two vertices u and p. See the picture below.

Set A is a set of vertices in the subtree of vertex u, and set B is a set of vertices which is not in the subtree of vertex u. So, is the set of vertices in the tree, and is empty.

For all pairs of two vertices (x, y) where the condition and holds, the shortest path between x and y contains edge e. There are size(A) × size(B) such pairs. So, edge e increases the sum S by 2 × l_e × size(A) × size(B). (because d(x, y) and d(y, x) both contributes to S)

size(A) (the size of the subtree whose root is u) can be calculated by dynamic programming in trees, which is well known. size(B) equals to N - size(A).

So, for each edge e, we can pre-calculate how many times does this edge contributes to the total sum. Let's define t(e) = size(A) × size(B), (A and B is mentioned above). If the length of a certain road e decreases by d, S will decrease by t(e) × d. So we can answer each query.

• Time: O(n) (pre-calculation) + O(q) (query)
• Memory: O(n) (O(n + q) is okay too)
• Implementation: 9335695 (.o.)

Something about precision error

Because of the tight constraints, the total sum of d(a, b) + d(b, c) + d(c, a) (it is equal to S × (n - 2)) can be so large that it can't be saved in long long(64-bit integer) type. Some contestants didn't handle this and got WA.

However, there are some contestants who saved this value divided by n × (n - 1) × (n - 2) in double type. double has 52 bits to store exact value, so it isn't enough. But because we allow 10^- 6 precision error, it seems to have been got accepted.

What if we allowed the length of the road could become 0? Then the precision error gets much more bigger, and the solution prints something that is far from the expected value (for example, negative value). ainu7 discovered this effect and suggested to apply this, but we didn't because it was hard to fix the statement..

Why does the road length decreases? It doesn't matter even if increases.

It's because of the weird legend. It is hard to explain, "People repairs a certain road per year, and its length may be increased or decreased." fluently for me..

500E - New Year Domino

From the statement, it is clear that, when domino i falls to the right, it makes domino j also fall if and only if p_i < p_j ≤ p_i + l_i.

For each domino i, let's calculate the rightmost position of the fallen dominoes R[i] when we initially pushed domino i. From the definition, . This can be calculated by using a segment tree or using a stack, in decreasing order of i (from right to left). After that, we define U[i] as the smallest j where R[i] < p_j holds. (In other words, the smallest j where domino j is not affected by pushing domino i)

Now, the problem becomes: Calculate P[U[x_i]] - R[x_i] + P[U[U[x_i]]] - R[U[x_i]] + ..., until U[x_i] ≤ y_i. Because i < U[i], this task can be solved by precalculating 'jumps' of 2^something times, using the method described in here. You must read the "Another easy solution in <O(N logN, O(logN)>" part..

Formally, let's define U^n + 1[k] = U[Uⁿ[k]] and S^n + 1[k] = Sⁿ[k] + (P[U^n + 1[k]] - R[Uⁿ[k]]). So, Sⁿ[k] means the sum of domino length extensions when we initially push domino i and we prolonged the length exactly n times. U^2i + 1[k] = U²ⁱ[U²ⁱ[k]], and S^2i + 1[k] = S²ⁱ[k] + S²ⁱ[U²ⁱ[k]] holds. (If you don't understand this part, I suggest you to read the article linked above)

• Time : or .
• Memory :
• Implementation: 9335698 (.o.)
• We would like to know whether there is a linear offline solution or not.

500F - New Year Shopping

The i-th item is available during [t_i, t_i + p - 1]. In other words, at time T, item i is available if and only if t_i ≤ T ≤ t_i + p - 1. This can be re-written as (t_i ≤ T and T - p + 1 ≤ t_i), which is T - p + 1 ≤ t_i ≤ T. With this observation, we can transform the item's purchasable range into a dot, and the candidate's visit time into a range: From now on, item i is only available at time t_i. and each candidate pair (a_j, b_j) means that I can visit the store during [a_j - p + 1, a_j], and my budget is b_j dollars at that visit. This transformation makes the problem easier to solve.

Each red circled point denotes an item which is sold at that time, and each black interval denotes a candidate. Let's only consider the intervals which passes time T. All the intervals' length is exactly p, so the left bound of the interval is (T - p) and the right bound of the interval is (T + p).

For each interval, we'd like to solve the 0/1 knapsack algorithm with the items that the interval contains. How can we do that effectively? There is an important fact that I've described above: all the interval passes time T. Therefore, the interval [a_j - p + 1, a_j] can be split into two intervals: [a_j - p + 1, T - 1] and [T, a_j].

So, let's solve the 0/1 knapsack problem for all intervals [x, T - 1] (T - p ≤ x ≤ T - 1) and [T, y] (T ≤ y ≤ T + p). Because one of the endpoints is fixed, one can run a standard dynamic programming algorithm. Therefore, the time needed in precalculation is O(S × W), where S is the number of items where the condition holds.

Let's define h(I, b), as the maximum happiness I can obtain by buying the items where the condition holds, using at most b dollars. For each candidate (a_j, b_j), we have to calculate h([a_j - p + 1, a_j], b_j), which is equal to max_{0 ≤ k ≤ b}{h([a_j - p + 1, T - 1], k) + h([T, a_j], b - k)}. So it takes O(b_j) = O(W) time to solve each query.

The only question left is: How should we choose the value of T? We have two facts. (1) The length of intervals is exactly p. (2) The algorithm covers intervals which passes time T. Therefore, to cover all the intervals given in the input, we should let T be p, 2p, 3p, 4p, ... (of course, one by one), and run the algorithm described above.

Then, what is the total time complexity? Think of intervals [0, 2p], [p, 3p], [2p, 4p], [3p, 5p], .... For each point, there will be at most two intervals which contains the point. Therefore, each item is reflected in the pre-calculation at most twice, so the time needed to precalculate is O(n × W). The time needed to solve each query is O(b_j), and the answer of the query is calculated at most once. Therefore, the time needed to answer all the queries is O(q × W).

• Time : O((n + q) × W).
• Memory : O(n × W)
• Implementations: 9335699 (ainta), 9335703 (ainu7) , 9335710 (.o., using a different approach), 9335709 (.o., using a divide and conquer approach)

Divide and Conquer approach

Let's assume that t₁ ≤ t₂ ≤ ... ≤ t_n. We can easily know that at time T, the indexes of all the available items forms a segment [l, r]. (in other words, item l, item l + 1, ..., item r - 1, item r is available) We can use this fact to solve all the queries. Let's assume that item l_j, item l_j + 1, ..., item r_j - 1, item r_j is available at time a_j.

Define a function solve(L, R). This function calculates the answer for queries where the condition L ≤ l_j ≤ r_j ≤ R holds. Let's assume that L < R holds. (In the case L ≥ R, the answer can be calculated easily) Let . Call solve(L, M) and solve(M + 1, R). After that, the queries needed to be calculated, satisfies the condition l_j ≤ M < r_j, which means all the intervals(queries) passes item M. Now, to calculate the answer for such queries, we can use the method described at the dynamic programming approach.

The time complexity is , because and the answer of the queries can be calculated in O(b_j) per query.

• Time : .
• Memory : O(n × W)
• Implementation: 9335709

Unfortunately, this approach is offline, because of the memory. Is there any available online approach using divide and conquer?

Blocking the divide and conquer solution

I tried my best to block divide and conquer solutions, but failed. It seems that many participants solved the problem with divide and conquer approach. My approach takes time, and it gets accepted in 546ms.

500G - New Year Running

Before starting the editorial, I'd like to give a big applause to Marcin_smu, who solved the problem for the first time!

Warning: The editorial is very long and has many mistakes. There are lots of lots of mistakes.. Keep calm, and please tell me by comments, if you discovered any errors.

This problem can be solved by an online algorithm. Let's focus on a single query (u, v, x, y). This means that JH runs between u and v, and JY runs between x and y.

Just like when we solve many problems with undirected trees, let vertex 1 be the root of the tree. Also, we will assume that they won't stop after when they meet, but they will continue running, in order to explain easily.

Some definitions:

• Path (a, b): the shortest path between vertex a and vertex b.
• d(a, b): the length of Path (a, b).
• LCA(a, b): the lowest common ancestor of vertex a and vertex b.

Finding the common path of two paths

If there is no common vertex between Path (u, v) and Path (x, y), the answer will be obviously  - 1. So, let's find the common vertices first. Because the path between two vertices is always unique, the common vertices also form a path. So, I'll denote the path of the common vertices as Path (c₁, c₂). c₁ and c₂ may be equal to: u, v, x, y, and even each other.

The possible endpoints are P₁ = LCA(u, v), P₂ = LCA(x, y), P₃ = LCA(u, x), P₄ = LCA(u, y), P₅ = LCA(v, x), and P₆ = LCA(v, y). Figure out by drawing some examples. (some of you might think it's obvious :D)

See the pictures above, and make your own criteria to check whether the two paths intersects :D

A small hint. Let's assume that we already know, that a vertex a lies on path (x, y). If a lies on path (u, v), a is a common vertex of two paths. What if a is guaranteed to be an end point of the common path?

Additional definitions

• Let's denote JH's running course is: . Then, there are two possible courses for JY: and ).

• f_JH : the time needed to run the course .
• f_JY : the time needed to run the course .
• t₁ : the first time when JH passes vertex c₁, moving towards c₂.
• t₂ : the first time when JH passes vertex c₂, moving towards c₁.
• t₃ : the first time when JY passes vertex c₁, moving towards c₂.
• t₄ : the first time when JY passes vertex c₂, moving towards c₁.

Case 1) When JH and JY meets while moving in the same direction

Obviously, they must meet at vertex c₁ or vertex c₂ for the first time. Without loss of generality, let's assume that they meet at vertex c₁. In this case, both of them is moving towards vertex c₂. (You can use the method similarly for c₂)

Let's assume that JH and JY meets at time T. Because the movements of both runners are periodic, T must satisfy the conditions below:

Among possible T-s, we have to calculate the smallest value. How should we do? From the first condition, we can let T = f_JH × p + t₁, where p is a non-negative integer. With this, we can write the second condition as: . In conclusion, we have to find the smallest p which satisfies the condition

Using the Extended Euclidean algorithm is enough to calculate the minimum p. With p, we can easily calculate the minimum T, which is the first time they meet. If there is no such p, they doesn't meet forever, so the answer is  - 1.

Case 2) When JH and JY meets while moving in the opposite direction

In this case, they will meet at a vertex lying on Path (c₁, c₂). Without loss of generality, let's assume that JH is going from c₁ to c₂, and JY is going from c₂ to c₁.

I'll assume that JH and JY meets at time T.

[1] Let's see how JH moves: For all non-negative integer p,

1. At time f_JH × p + t₁, he is at vertex c₁, moving towards c₂.
2. At time f_JH × p + t₁ + d(c₁, c₂), he is at vertex c₂.

Therefore, when f_JH × p + t₁ ≤  (current time)  ≤ f_JH × p + t₁ + d(c₁, c₂), JH is on Path (c₁, c₂). So, T must satisfy the condition:

• f_JH × p + t₁ ≤ T ≤ f_JH × p + t₁ + d(c₁, c₂)

[2] Let's see how JY moves: Similar to JH, for all non-negative integer q,

1. At time f_JY × q + t₄, he is at vertex c₂, moving towards c₁.
2. At time f_JY × q + t₄ + d(c₂, c₁), he is at vertex c₁.

Therefore, when f_JY × q + t₄ ≤  (current time)  ≤ f_JY × q + t₄ + d(c₂, c₁), JY is on Path (c₂, c₁). So, T must satisfy the condition:

• f_JY × q + t₄ ≤ T ≤ f_JY × q + t₄ + d(c₁, c₂)

[3] These two conditions are not enough, because in this case, they can meet on an edge, but they cannot meet on a vertex.

We'd like to know when do they meet on a vertex, like the picture below.

As you see from the picture above, in this case, the condition d(c₁, a) + d(a, c₂) = d(c₁, c₂) holds. If this picture was taken at time s, this condition can be written as:

Because JH and JY both travel their path back and forth, f_JH and f_JY are all even. Therefore, in order to make s an integer, d(c₁, c₂) + t₁ + t₄ must be even. This can be written as

[4] Merging [1], [2] and [3], we can conclude that if these two conditions holds,

• 
• max{f_JH × p + t₁, f_JY × q + t₄} ≤ min{f_JH × p + t₁ + d(c₁, c₂), f_JY × p + t₄ + d(c₁, c₂)}

JH and JY meets on a certain vertex lying on path (c₁, c₂). The first condition can be easily checked, so let's focus on the second condition. The second condition holds if and only if:

• f_JY × q + t₄ - t₁ - d ≤ f_JH × p ≤ f_JY × q + t₄ - t₁ + d

You can check this by changing "f_JH × p" to the lower bound and the upper bound of the inequality. Therefore, the problem is to find the smallest p which satisfies the condition above.

Let's define a function g(M, D, L, R), where M, D, L, R are all non-negative integers. The function returns the smallest non-negative integer m which satisfies . This function can be implemented as follows.

1. If L = 0, g(M, D, L, R) = 0. (because L = 0 ≤ D·0)
2. If , it is "obvious" that there is no solution.
3. If 2D > M, g(M, D, L, R) = g(M, M - D, M - R, M - L).
4. If there exists an non-negative integer m which satisfies L ≤ D·m ≤ R (without modular condition), g(M, D, L, R) = m. Obviously, we should take the smallest m.
5. Otherwise, there exists an integer m which satisfies D·m < L ≤ R < D·(m + 1). We should use this fact..
   
   If holds, there exists an non-negative integer k which satisfies L + Mk ≤ D·m ≤ R + Mk. Let's write down.. D·m - R ≤ M·k ≤ D·m - L
    - R ≤ M·k - D·m ≤  - L
   L ≤ D·m - M·k  ≤ RBecause , we can write the inequality as Therefore the minimum k among all possible solutions is equal to . We can easily calculate the smallest p using k.

Then, what is the time complexity of calculating g(M, D, L, R)? Because 2D ≤ M (the 2D > M case is handled during step 3), the problem size becomes half, so it can be executed in .

Conclusion

For each query, we have to consider both Case 1) and Case 2), with all possible directions. Both cases can be handled in , so the time complexity per query is , and it has really huge constant.

• Time:
• Memory:
• Implementation: 9330235