Hello everyone, I hope you can enjoy this special round for Zepto Lab. Here are the solutions of this round.

A. King of Thieves

This task is easy for many of you. We can just iterate over all possible i₁ and i₂ - i₁, then we can compute i_{3, ..., 5}, and check whether this subsequence satisfies the condition mentioned in the task.

B. Om Nom and Dark Park

We use greedy and recursion to solve this task. For each tree rooted at v, we adjust its two subtrees at first, using recursion. Then we increase one edge from v's child to v.

C. Om Nom and Candies

If there is a kind of candy which weighs greater than , then we can iterate over the number of it to buy, which is less than .

Otherwise, without loss of generality we suppose . If the number of the blue candies that Om Nom eats is more than W_r, he could eat W_b red candies instead of W_r blue candies, because H_b × W_r < W_b × H_r. It means the number of the blue candies will be less than , and we can iterate over this number.

D. Om Nom and Necklace

This task is to determine whether a string is in the form of ABABA... ABA for each prefixes of a given string S

For a prefix P, let's split it into some blocks, just like P = SSSS... SSSST, which T is a prefix of S. Obviously, if we use KMP algorithm, we can do it in linear time, and the length of S will be minimal. There are only two cases : T = S, T ≠ S.

1. T = S. When T = S, P = SSS... S. Assume that S appears R times. Consider "ABABAB....ABABA", the last A must be a suffix of P, and it must be like SS... S, so A will be like SS... SS, and so will B. By greedy algorithm, the length of A will be minimal, so it will be SSS... S, where S appears times. And B will be SSS... S, where S appears times. So we just need to check whether .
2. T ≠ S . When T ≠ S, the strategy is similar to T = S. A will be like "SS...ST", and its length will be minimal. At last we just need to check whether .

The total time complexity is O(n).

E. Transmitting Levels

Our task is to compute at least how many number of blocks are needed to partition a circular sequence into blocks whose sum is less than K.

By monotonicity, it is easy to get the length of maximal blocks which starts from 1 to n in O(n). Assume the block with minimal length is A and its length is T, it is obvious that whatever the blocks are, there must be a block that it starts in A. So, we can iterate over all the T numbers of A, making it the start of a block, and calculate the number of blocks.

Notice that all the lengths of blocks is (non-strictly) greater than T, therefore the number of blocks we need is at most N / T + 1. We need to iterate T times, but each time we can get the answer in O(N / T), so finally we can check whether the answer is legal in T * O(N / T) = O(N).

F. Pudding Monsters

Actually this problem is to compute how many segments in a permutation forms a permutation of successive integers.

We use divide and conquer to solve this problem.

If we want to compute the answer for an interval [1, n], we divide this interval into two smaller ones [1, m], [m + 1, n] where . We only care about the segments which crosses m. We call the first interval L and the latter one R.

Considering the positiions of maximum numbers and minimum numbers in these valid segments, There are four possible cases:

1. the maximum number is in L, the the minimum is also in L;
2. the maximum number is in R, the the minimum is also in R;
3. the maximum number is in L, the the minimum is in R;
4. the maximum number is in R, the the minimum is in L;

Let A be the given sequence and we define Lmax_p = max_{p ≤ i ≤ m}A_i. Similarly we can define Rmax_p, Rmin_p, Lmin_p.

For simplicity we only cares about case 1 and case 4.

In Case 1, we iterate over the start position of the segment, so we know the maximum and minimum number so we can compute the length of the segment and check the corresponding segment using Rmin and Rmax.

In Case 4, we iterate over the start position again, denoted as x. Suppose the right end is y, then we know that Lmin_x < Rmin_y, Lmax_x < Rmax_y so we can limit y into some range. Another constraint for y is that Rmax_y - Lmin_x = y - x, i.e. Rmax_y - y = Lmin_x - x. Note that when x varies, the valid range for y also varies, but the range is monotone, so we can maintain how many times a number appears in linear time.

It's easy to show that this algorithm runs for , by Master Theorem.

There are some other people using segment trees. You can see a nice implement here

G. Spiders Evil Plan

In this task, we are given a tree and many queries. In each query, we are supposed to calculate the maximum total length of y paths with the constraint that x must be covered.

Consider S is the union of the paths (it contains nodes and edges).

For each query (x, y), if  y > 1 , then there is always a method that S is connected.

Further, we could get the following theorem:

For an unrooted tree, if it has 2k leaves, then k paths can cover this tree completely.

Proof for this theorem is that, if some edge u - v is not covered, we can interchange two paths, i.e. we change two paths a - b and c - d to a - c and b - d, for a - b in the subtree of u and c - d in the subtree of v.

So a query (x, y) could be described as :

Find 2y leaves in the tree, with node x in S, and maximize the total of weight of the edges in S.

For a query (x, y), we can make x the root. Then this task is how to choose the leaves. Note that we could select leaves one by one, every time we select the leaf which makes answer larger without selecting the others, as follow :

But if for every query we need to change the root, the time complexity cannot be accepted. Assuming the longest path in the tree is (a, b) , we could find that whatever the query is, S will contain either a or b certainly.

So, we just need to make a and b the root in turn, and get the maximum answers. However, there is another problem : x may not be in S. Like this :

But it doesn't matter. We just need to link x with the selected, and erase some leaf. Of course after erasing, the answer should be maximum.

Thanks, for all of your excellent performance!

Sorry for my poor English :) This is the online version.

Problem D. k-Maximum Subsequence Sum

Brief Description Giving a number sequence {A_i}, in this sequence you need to implement the following two operations:

1. 0 x v: Change A_x to v.
2. 1 l r k: Query the k-MSS in [l,  r].

Analysis

Consider the static problem, Apparently, we can use a dynamic programming to solve it.

1. f₀[i][j]: the j-MSS in [0, i].
2. f₁[i][j]: the quasi-j-MSS in [0, i], which the item {A_i} must be selected.

The state transition is enumerating whether the ith element is selected or not. That's easy for a clever guy such as you. So the brute-force method is doing a dynamic programming for each query. The operation Modify takes O(1) time, and Query takes O(nk) . It's too slow to get Accepted.

A simple optimization is using a data structure to speed up Query. The segment tree can be OK. In every node, we store such values in the interval represented by the node:

1. the max sum if choosing j subsegments
2. the max sum if choosing j subsegments with the first element chosen
3. the max sum if choosing j subsegments with the last element chosen
4. the max sum if choosing j subsegments with both first element and last element chosen

It's clear that if we know the values of two intervals A and B, we can infer the values of the interval which is concatenating A and B by just enumerating how many subsegments can be chosen in A and can be chosen in B. The time complexity of concatenating two intervals is O(k²). So both operations Modify and Query take running time. The time limit is 5s in order to save Java's life. If you do some optimization, the solution can be Accepted. You can see liouzhou_101's solution for details.

It seems hard to be optimized using such idea. Now we are going to use another totally different idea from max-flow problem. We construct a max-cost max-flow model to solve this problem. The source is S and the sink is T. There are other n + 1 vertices. A bi-directional edge between Vertex i and Vertex i + 1 has cost A_i and capacity 1. The unidirectional edge from S to Vertex i has cost 0 and capacity 1 and the unidirectional edge from Vertex i to T has cost 0 and capacity 1. It's obvious for correctness. We can use Successive shortest path algorithm to solve the flow problem. But it's as slow as the brute-force method, or even worse.

Considering how the flow problem is solved, that is, how Successive shortest path algorithm works. We find the longest path(**max-cost** instead of min-cost ) between S and T, and then augment. We can simplify the algorithm due to the special graph. The new algorithm is:

1. find the subsegment with the maximum sum
2. negate the elements in the subsegment
3. repeat the two steps k times
4. the answer is the sum of the sum of the subsegment you found each time.

So, the key point is doing these two operations quickly, where segment tree can possibly be used. To find the MSS you need to store

1. the sum of an interval
2. the maximum partial sum from left
3. the maximum partial sum from right
4. the MSS in the interval

To negate a subsegment, the minimum elements must be stored. To find the position of MSS, all the positions are supposed to be kept. The complexity of Modify is , and the complexity of Query is . It can pass all the test data easily but it has a really large constant. This is UESTC_Nocturne's solution and FattyPenguin's solution

The idea is hard to come up with and is also hard to code. So let's applaud again for UESTC_Nocturne and FattyPenguin. Also thanks for the great optimization of liouzhou_101.