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

Unable to parse markup [type=CF_TEX]

and

Unable to parse markup [type=CF_TEX]

, then we can compute

Unable to parse markup [type=CF_TEX]

, 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

Unable to parse markup [type=CF_TEX]

, we adjust its two subtrees at first, using recursion. Then we increase one edge from

Unable to parse markup [type=CF_TEX]

's child to

Unable to parse markup [type=CF_TEX]

.

C. Om Nom and Candies

If there is a kind of candy which weighs greater than

Unable to parse markup [type=CF_TEX]

, then we can iterate over the number of it to buy, which is less than

Unable to parse markup [type=CF_TEX]

.

Otherwise, without loss of generality we suppose

Unable to parse markup [type=CF_TEX]

. If the number of the blue candies that Om Nom eats is more than

Unable to parse markup [type=CF_TEX]

, he could eat

Unable to parse markup [type=CF_TEX]

red candies instead of

Unable to parse markup [type=CF_TEX]

blue candies, because

Unable to parse markup [type=CF_TEX]

. It means the number of the blue candies will be less than

Unable to parse markup [type=CF_TEX]

, 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

Unable to parse markup [type=CF_TEX]

for each prefixes of a given string

Unable to parse markup [type=CF_TEX]

For a prefix P, let's split it into some blocks, just like

Unable to parse markup [type=CF_TEX]

, which

Unable to parse markup [type=CF_TEX]

is a prefix of

Unable to parse markup [type=CF_TEX]

. Obviously, if we use KMP algorithm, we can do it in linear time, and the length of

Unable to parse markup [type=CF_TEX]

will be minimal. There are only two cases :

Unable to parse markup [type=CF_TEX]

.

1. Unable to parse markup [type=CF_TEX]

   . When

   Unable to parse markup [type=CF_TEX]

   . Assume that

   Unable to parse markup [type=CF_TEX]

   appears

   Unable to parse markup [type=CF_TEX]

   times. Consider "ABABAB....ABABA", the last

   Unable to parse markup [type=CF_TEX]

   must be a suffix of

   Unable to parse markup [type=CF_TEX]

   , and it must be like

   Unable to parse markup [type=CF_TEX]

   , so

   Unable to parse markup [type=CF_TEX]

   will be like

   Unable to parse markup [type=CF_TEX]

   , and so will

   Unable to parse markup [type=CF_TEX]

   . By greedy algorithm, the length of

   Unable to parse markup [type=CF_TEX]

   will be minimal, so it will be

   Unable to parse markup [type=CF_TEX]

   , where

   Unable to parse markup [type=CF_TEX]

   appears

   Unable to parse markup [type=CF_TEX]

   times. And

   Unable to parse markup [type=CF_TEX]

   will be

   Unable to parse markup [type=CF_TEX]

   , where

   Unable to parse markup [type=CF_TEX]

   appears

   Unable to parse markup [type=CF_TEX]

   times. So we just need to check whether

   Unable to parse markup [type=CF_TEX]

   .

2. Unable to parse markup [type=CF_TEX]

   . When

   Unable to parse markup [type=CF_TEX]

   , the strategy is similar to

   Unable to parse markup [type=CF_TEX]

   . A will be like "SS...ST", and its length will be minimal. At last we just need to check whether

   Unable to parse markup [type=CF_TEX]

   .

The total time complexity is

Unable to parse markup [type=CF_TEX]

.

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

Unable to parse markup [type=CF_TEX]

.

By monotonicity, it is easy to get the length of maximal blocks which starts from 1 to

Unable to parse markup [type=CF_TEX]

in

Unable to parse markup [type=CF_TEX]

. Assume the block with minimal length is

Unable to parse markup [type=CF_TEX]

and its length is

Unable to parse markup [type=CF_TEX]

, it is obvious that whatever the blocks are, there must be a block that it starts in

Unable to parse markup [type=CF_TEX]

. So, we can iterate over all the

Unable to parse markup [type=CF_TEX]

numbers of

Unable to parse markup [type=CF_TEX]

, 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

Unable to parse markup [type=CF_TEX]

, therefore the number of blocks we need is at most

Unable to parse markup [type=CF_TEX]

. We need to iterate

Unable to parse markup [type=CF_TEX]

times, but each time we can get the answer in

Unable to parse markup [type=CF_TEX]

, so finally we can check whether the answer is legal in

Unable to parse markup [type=CF_TEX]

.

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

Unable to parse markup [type=CF_TEX]

, we divide this interval into two smaller ones

Unable to parse markup [type=CF_TEX]

where

Unable to parse markup [type=CF_TEX]

. We only care about the segments which crosses

Unable to parse markup [type=CF_TEX]

. We call the first interval

Unable to parse markup [type=CF_TEX]

and the latter one

Unable to parse markup [type=CF_TEX]

.

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

1. the maximum number is in

   Unable to parse markup [type=CF_TEX]

   , the the minimum is also in

   Unable to parse markup [type=CF_TEX]

   ;
2. the maximum number is in

   Unable to parse markup [type=CF_TEX]

   , the the minimum is also in

   Unable to parse markup [type=CF_TEX]

   ;
3. the maximum number is in

   Unable to parse markup [type=CF_TEX]

   , the the minimum is in

   Unable to parse markup [type=CF_TEX]

   ;
4. the maximum number is in

   Unable to parse markup [type=CF_TEX]

   , the the minimum is in

   Unable to parse markup [type=CF_TEX]

   ;

Let

Unable to parse markup [type=CF_TEX]

be the given sequence and we define

Unable to parse markup [type=CF_TEX]

. Similarly we can define

Unable to parse markup [type=CF_TEX]

.

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

Unable to parse markup [type=CF_TEX]

and

Unable to parse markup [type=CF_TEX]

.

In Case 4, we iterate over the start position again, denoted as

Unable to parse markup [type=CF_TEX]

. Suppose the right end is

Unable to parse markup [type=CF_TEX]

, then we know that

Unable to parse markup [type=CF_TEX]

so we can limit

Unable to parse markup [type=CF_TEX]

into some range. Another constraint for

Unable to parse markup [type=CF_TEX]

is that

Unable to parse markup [type=CF_TEX]

, i.e.

Unable to parse markup [type=CF_TEX]

. Note that when

Unable to parse markup [type=CF_TEX]

varies, the valid range for

Unable to parse markup [type=CF_TEX]

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

Unable to parse markup [type=CF_TEX]

, 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

Unable to parse markup [type=CF_TEX]

paths with the constraint that

Unable to parse markup [type=CF_TEX]

must be covered.

Consider

Unable to parse markup [type=CF_TEX]

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

For each query

Unable to parse markup [type=CF_TEX]

, if

Unable to parse markup [type=CF_TEX]

, then there is always a method that

Unable to parse markup [type=CF_TEX]

is connected.

Further, we could get the following theorem:

For an unrooted tree, if it has

Unable to parse markup [type=CF_TEX]

leaves, then

Unable to parse markup [type=CF_TEX]

paths can cover this tree completely.

Proof for this theorem is that, if some edge

Unable to parse markup [type=CF_TEX]

is not covered, we can interchange two paths, i.e. we change two paths

Unable to parse markup [type=CF_TEX]

and

Unable to parse markup [type=CF_TEX]

to

Unable to parse markup [type=CF_TEX]

and

Unable to parse markup [type=CF_TEX]

, for

Unable to parse markup [type=CF_TEX]

in the subtree of

Unable to parse markup [type=CF_TEX]

and

Unable to parse markup [type=CF_TEX]

in the subtree of

Unable to parse markup [type=CF_TEX]

.

So a query

Unable to parse markup [type=CF_TEX]

could be described as :

Find

Unable to parse markup [type=CF_TEX]

leaves in the tree, with node

Unable to parse markup [type=CF_TEX]

in

Unable to parse markup [type=CF_TEX]

, and maximize the total of weight of the edges in

Unable to parse markup [type=CF_TEX]

.

For a query

Unable to parse markup [type=CF_TEX]

, we can make

Unable to parse markup [type=CF_TEX]

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

Unable to parse markup [type=CF_TEX]

, we could find that whatever the query is,

Unable to parse markup [type=CF_TEX]

will contain either

Unable to parse markup [type=CF_TEX]

or

Unable to parse markup [type=CF_TEX]

certainly.

So, we just need to make

Unable to parse markup [type=CF_TEX]

and

Unable to parse markup [type=CF_TEX]

the root in turn, and get the maximum answers. However, there is another problem :

Unable to parse markup [type=CF_TEX]

may not be in

Unable to parse markup [type=CF_TEX]

. Like this :

But it doesn't matter. We just need to link

Unable to parse markup [type=CF_TEX]

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

Unable to parse markup [type=CF_TEX]

, in this sequence you need to implement the following two operations:

1. 0 x v: Change

   Unable to parse markup [type=CF_TEX]

   to

   Unable to parse markup [type=CF_TEX]

   .
2. 1 l r k: Query the k-MSS in

   Unable to parse markup [type=CF_TEX]

   .

Analysis

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

1. Unable to parse markup [type=CF_TEX]

   : the j-MSS in [0, i].

2. Unable to parse markup [type=CF_TEX]

   : the quasi-j-MSS in [0, i], which the item

   Unable to parse markup [type=CF_TEX]

   must be selected.

The state transition is enumerating whether the

Unable to parse markup [type=CF_TEX]

time, and Query takes

Unable to parse markup [type=CF_TEX]

. 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

   Unable to parse markup [type=CF_TEX]

   subsegments
2. the max sum if choosing

   Unable to parse markup [type=CF_TEX]

   subsegments with the first element chosen
3. the max sum if choosing

   Unable to parse markup [type=CF_TEX]

   subsegments with the last element chosen
4. the max sum if choosing

   Unable to parse markup [type=CF_TEX]

   subsegments with both first element and last element chosen

It's clear that if we know the values of two intervals

Unable to parse markup [type=CF_TEX]

and

Unable to parse markup [type=CF_TEX]

, we can infer the values of the interval which is concatenating

Unable to parse markup [type=CF_TEX]

and

Unable to parse markup [type=CF_TEX]

by just enumerating how many subsegments can be chosen in

Unable to parse markup [type=CF_TEX]

and can be chosen in

Unable to parse markup [type=CF_TEX]

. The time complexity of concatenating two intervals is

Unable to parse markup [type=CF_TEX]

. So both operations Modify and Query take

Unable to parse markup [type=CF_TEX]

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

Unable to parse markup [type=CF_TEX]

and the sink is

Unable to parse markup [type=CF_TEX]

. There are other

Unable to parse markup [type=CF_TEX]

vertices. A bi-directional edge between Vertex

Unable to parse markup [type=CF_TEX]

and Vertex

Unable to parse markup [type=CF_TEX]

has cost

Unable to parse markup [type=CF_TEX]

and capacity 1. The unidirectional edge from

Unable to parse markup [type=CF_TEX]

to Vertex

Unable to parse markup [type=CF_TEX]

has cost 0 and capacity 1 and the unidirectional edge from Vertex

Unable to parse markup [type=CF_TEX]

to

Unable to parse markup [type=CF_TEX]

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

Unable to parse markup [type=CF_TEX]

and

Unable to parse markup [type=CF_TEX]

, 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

   Unable to parse markup [type=CF_TEX]

   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

Unable to parse markup [type=CF_TEX]

, and the complexity of Query is

Unable to parse markup [type=CF_TEX]

. 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.