This was my first SRM, and I would like to thank rng_58 (algorithm coordinator + tester), KADR (tester), misof (language reviewer) and dreamoon_love_AA (author of Div1 medium) for their invaluable help.

I will try to keep this short, since the TC editorial writers are much better at writing explanations.

Div2 Easy -- FilipTheFrog

The simplest solution is to perform N iterations. Each iteration, look for a pair (i, j) such that island i is reachable and |positions[i] - positions[j]| ≤ L. Mark island j as visited. The complexity is O(N³). It works because each iteration increases the answer by at least 1 assuming it hasn't already been found, so after N iterations your answer is guaranteed to be correct.

Div2 Medium -- PublicTransit

You can fix each possibility for the teleporter and then test every pair of cells to find the longest distance. You can calculate it as follows: if the teleporter cells are at a and b, then the distance between cells x and y is the minimum of the following:

• dist(x, y)
• dist(x, a) + dist(b, y)
• dist(x, b) + dist(a, y)

The complexity is O(R⁴C⁴). I think you can improve it to O(R³C³) by observing that if one booth is at (r, c), the other booth should be at (R - r + 1, c) or (r, C - c + 1). I'm not actually sure if that's true, though. Maybe it's wrong. Can anyone prove/disprove it?

Div2 Hard -- ApplesAndOrangesHard

First, read the editorial for the easy version below.

We will use the same greedy algorithm, but we can't process every fruit directly. Let's think about the optimal answer if weren't included. We could have floor(K / 2) apples, then ceil(K / 2) oranges, repeated until we have N fruits.

When we are forced to add an apple, we should disrupt this pattern as little as possible. Let's sort and keep a 'window' of size K. Initially, the window's first K / 2 elements are apples and the rest are oranges, and it represents the range of fruits [1, K]. When you move to the next element of , cycle the window forward so that fruit number is at the end of the window. Then, pick the the apple with the greatest index, and move it to the end of the array. You have to ensure you don't pick an apple that is immovable because of a previous value in . The complexity is .

You can also solve it when K ≤ 10⁹, but it's more trouble than it's worth.

Div1 Easy -- ApplesAndOrangesEasy

The algorithm is greedy: for each i from 1 to N, try to make the i-th fruit an apple. If it contradicts the information you have, make it an orange instead. It works because making a fruit an apple affects the next K - 1 choices, so you want to make the earliest possible fruit an apple -- that way, it becomes unimportant sooner.

Naive complexity is O(NK²); you can improve it to O(NK) by using a queue or prefix sum array or clever loop.

Div1 Medium -- CampLunch

(Problem and editorial by dreamoon_love_AA.)

If all permutation in each element of a are same, this problem just a normal Tiling problem such as UVa11270. (Before solve this SRM med problem, you may need to know how to solve UVa11270 with O(n² * 2ⁿ) firstly.)

The main difference of this problem with UVa11270 is a student can seat in different place in consecutive two days. It cause we cannot only reserve dp status for next M seats from current seat (this kind of problem method have the status dp[row][column][the occuppied status of next M grids]). Then, how can we resolve this situation?

Here provides two method to resolve it by change dp status:

(1) Change dp status to dp[row][i-th student][the status of having plan or not of next M (day, student)].

You can imagine it as all student seat in alphabetical order, and plan 2 of lunch represent some pair of student can get double lunch in some day. By this way, you only reserved status of at most M student in dp proccess.

(2) Change dp status to dp[row][column][the status of having plan or not of next M (day,student)].

In detail, the next M (day,student) means students that have larger column number of this row in the same day and other students in next day. I think it's more difficult to imagine than previous method.

Ironically, the two methods are not provided by myself, these solution are provided by two tester. I solve it in O(2ⁿ * n³) originally. The story tell us: if you can find a good status of dp, it make your dp life better.

Div1 Hard

Fix the first teleporter at A. Now do a DFS from A. Suppose we're currently visiting B. Each node N on the path from A to B has a precomputed 'hanging value', the length of the longest path starting from N which doesn't get closer to A or B. Number the nodes on the path from 0 (A) to S - 1 (B), where the path has S nodes. When moving between nodes at positions p₁ and p₂ on the path (p₂ > p₁), we can take a direct route (length p₂ - p₁) or an indirect route (length (S - 1) - p₂ + p₁). Note that the length of the direct route is fixed, while the indirect route gets 1 minute longer with each step of DFS.

In the DFS transition, we add a node to the path. We will process this node to obtain an integer LIM, meaning that the new node enforces the constraint that we can't continue the DFS in a direction away from A and B for more than LIM steps.

How do we process the node? Suppose the node has hanging value v₂ and position p₂. We want to select a node on the path with value v₁ and position p₁ such that:

• The direct path is infeasible: p₂ - p₁ + v₁ + v₂ > X. Rearranging, we want v₁ - p₁ > X - p₂ - v₂.
• The limiting factor (LIM = X - ((S - 1) - p₂ + p₁ + v₁ + v₂)) is minimal. Rearranging, we want to maximize v₁ + p₁.

By converting candidate nodes (v₁, p₁) to diagonal coordinates (v₁ - p₁, v₁ + p₁), it reduces to dynamic RMQ and we can solve it with a persistent segment tree. The complexity is .