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*_{1} and *i*_{2} - *i*_{1}, 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*.

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

- the maximum number is in
*L*, the the minimum is also in*L*; - the maximum number is in
*R*, the the minimum is also in*R*; - the maximum number is in
*L*, the the minimum is in*R*; - 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 2

kleaves, thenkpaths 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 2*y* 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!

thanks for fast editorial :)

Elegant starts with E, which is the perfect adjective for problem E. Awesome problem! :D

What does

`S`

mean for C?Fixed. S should be C

SO SAD!!! Problem C's answer was just 2 simple loop! :(

A very hard problem can easily have a one-loop solution. The main objective is to get it :)

But a very good problem shouldn't because you can guess it accidentally.

Please elaborate the editorial solution for Problem B.

If possible, can someone please explain tourist's solution — 10576165 ?

He is doing the same "DFS", just non-recursively. Imagine that you've walked nearly all the way and there are last two edges in front of you. In order to give them the same sum they must be equal and they don't depend on previous edges. So you can make edges the same in all pairs in the lowest layer, than just add numbers on lowest edges to their parents and "eliminate" the lowest layer (you don't need it anymore). And so tourist is doing.

Here is my solution that is doing exactly the same as tourist's: 10579416, two cycles are just for better understanding of layers idea, it all works in

O(N). One-cycle version: 10595439.Problem C: "If there is a kind of candy which weighs greater than sqrt(C)...." Why happens this special case? Can anyone explain it to me? :S

Suppose that there is a kind of candy which weighs more than sqrt(C), and for better explication suppose this is the red candy, and QR, WR , QB, WB are the quantities and weights of the candies, respectively red and blue. You must satisfy this:

And you want to find QR and QB. But we know that: WR > sqrt(C), so if you multiply by sqrt(C) in each side you maintain the inequality and get this: WR * sqrt(C) > C so if you use sqrt(C) or more red candies you will not satisfy the condition I. , no matter how many blue candies you use. Then QR must be less than sqrt(C), so you only need to iterate from 0 to sqrt(C) to find QR.

Thx a lot.Finally I know.

Thank you! :D

WOW !! That was really good explanation ... Didnt understand a single thing reading the editorial ... but you broke it down very nicely ... thnx man :) mras

Thanks!! :D

what about the case where both WR and WB are less than sqrt(C)?

In problem D, how this string

`abaabaabaabaabaa`

can be divided to A+B+A+B+A (since k=2)?

abaa+ba+abaa+ba+abaa

Thanks.

Problem C

Please explain the editorial when wr and wb is less the sqrt(c).

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

Assume that

w> sqrt(C), the maximum number of blue candies that can be eaten is floor(C /_{b}w), which is less than sqrt(C)._{b}We can also say, since

w> sqrt(C), then_{b}w* sqrt(C) > C. Therefore, Om Nom can eat at most sqrt(C) blue candies._{b}We iterate over the number of blue candies and get all possible answers, then get the largest one of them.

I think the situation he said is WR and WB are less than sqrt(c).And what you talk about is one candy is larger than sqrt(c) :).

Oh sorry... I made a mistake.

When neither of

WbandWris larger than sqrt(C), we can assume that Hb × Wr <= Wb × Hr. (If not, swap them.)As the editorial says, 'If the number of the blue candies that Om Nom eats is more than

Wr, he could eatWbred candies instead ofWrblue candies, because Hb × Wr < Wb × Hr.'If Om Nom eats

Wrbluecandies, which weighWr×Wbin all, he getsWr×Hbjoy units.However, if he eats

Wbredcandies, which also weighWr×Wbin all, he getsWb×Hrjoy units.Since Hb × Wr <= Wb × Hr, the choice of

Wbred candies is never worse thanWrblue candies.Therefore Om Nom should never eat more thanWe iterate over the number of blue candies eaten (which is always less thanWrblue candies.Wr< sqrt(C)), and find the best answer.In fact I did't figure it out,but now I do. You really help me a lot.

Wow. It would be really nice to be able to help other people ;)

WOWWWW !! that was really very nice explanation. I got the case for first part, where one of the weight is greater sqrt(C) from mras's comment ... and now i have understood the full solution of it. thanks a lot :) @cyand1317

i don't understand why they've written such short and unclear editorial :( The editorial above for problem C should be replaced with your (cyand1317) and mras's comment :/

I don't understand the C's solution , can any one clarify it more please

cnt_{r}andcnt_{b}are the answer.cnt_{r}*w_{r}+cnt_{b}*w_{b}≤cif

cnt_{b}>w_{r}thencnt_{b}=w_{r}+xandcnt_{r}*w_{r}+w_{r}*w_{b}+x*w_{b}≤c, so we can takew_{b}red candies instead ofw_{r}blue ones, sincew_{r}*h_{b}<w_{b}*h_{r}we will get more joy units — which is contradiction, thuscnt_{b}≤w_{r}.I may have posted it in wrong place (sorry, it was my first comment), but you can take a look here http://codeforces.com/blog/entry/17281#comment-220872

Can someone explain better the approach with KMP for D?

What does "Q" mean for problem D?

Q means K, you need to make AB block as long as you can

s= SSSS.....ST/ (S as small as posible and T is a prefix of S)

len(AB) = (total S blocks in string s)/K

len(A) = (total S blocks in string s)%K + len(T)

then just check if you have len(AB) >= len(A)

Thank you! finally I got the idea.

I just would add that:

len(AB) = (total S blocks in string s)/K * len(S)

(where len(S) is length of block S in chars)

len(A) = (total S blocks in string s)%K * len(S) + len(T)

There is another solution of problem C:

Obviously, it's impossible that the total weight of red candies is more than

`lcm(Wr, Wh)`

and simultaneously the total weight of blue candies is more than`lcm(Wr, Wh)`

. Because, lets suppose that`lcm / Wr * Hr > lcm / Wb * Hb`

, we can reduce the amount of blue candies and add some red that the total weight remains the same but this new answer is greater than the last one. So after that we need just to fill the rest weight --`max(0, C % lcm + lcm)`

. But`C % lcm + lcm < 2 * lcm`

and if two nubers have`lcm = x`

then it means that one of this numbers is greater or equal than`sqrt(x)`

. So that means that we need just to iterate over a multiplier of`max(Wr, Wb)`

to fill the rest (we need to iterate only over`max(C, 2 * lcm)`

values).I really can't understand in problem C the case If there is a kind of candy which weighs less than sqrt(C) !! :(

Let's assume both

W_{r}andW_{b}are less than .Assume

W_{r}×H_{b}<W_{b}×H_{r}is satisfied (otherwise we can just swap the candy's color).Then consider case where we take

W_{r}blue candy. This means we eatW_{r}×W_{b}grams candy with joyfulnessW_{r}×H_{b}. However, we can takeW_{b}red candy instead, because it still weightsW_{r}×W_{b}grams, with better joyfulness (rememberW_{r}×H_{b}<W_{b}×H_{r}). So whenever we eat more thanW_{r}blue candy, we can always exchangeW_{r}blue candy intoW_{b}red candy for optimality.Because of that, the number of blue candy taken in the optimal solution will always less than

W_{r}. We can brute force this, which runs inO(W_{r}). Remember that , so we can also say this works in . Really greedy solution :)I got it ! thank you so much

We need to iterate over

`min(C, 2*lcm)/Wmax`

values, and final complexity is`O(min(C/Wmax, Wmin))`

, i.e. lcm/Wmax is Wmin in the bad case.Yes, you are absolutely right. But

`O(min(C/Wmax, Wmin))`

is still`O(sqrt(C))`

.Hi everyone, I hope someone help me please.

I'm doing the problem D with hash and my solution give WA15, Is this test AntiHash?

I change the alphabet and test with some base too, in every judge give me WA15

This my solution

Indeed.

As a general rule, don't use polynomial hashes modulo a power of two. While it's faster this way, a well-known regular sequence (Thue-Morse) is known to break such hashing.

Here is your solution using hash modulo a prime 10

^{16}+ 61, accepted now.Thanks Gassa, I didn't kwow about the anti-hash tests.

But I dont understand your function mul(a,b,m) when I convert from HASH to long double and multiply two long doubles, Don't lose precision?

Maybe you can explain your function mul :).

(There's a link in the solution, however it goes to the Russian part of Codeforces.)Let

Q(quotient) andR(remainder) be such thata·b=Q·m+R, with 0 ≤R<m. Our solution will first`(1)`

find an approximate quotientq, then`(2)`

a valuerwhich differs from the real remainderRbyk·mfor some small integerk, and finally`(3)`

, the real remainderR.At first, we do

Now,

qis an approximate quotient (k= |Q-q| is small).Next,

Here, we try to define

rso thata·b=q·m+r. It would follow thatr=R+ (Q-q)·m.Actually though, , since the calculations take place in a 64-bit integer.

Ifhowever the value |Q-q| was so small that |a·b-q·m| < 2^{63}, then the above statementr=R+ (Q-q)·mis true, and we can then calculate the real remainder by taking .Here, note that

`r % m`

can be negative, and we often want the remainder in the mathematical sense (0 ≤r<m). So, we assume |Q-q| ≤ 5, and sor+ 5·m≥ 0.When the

`long double`

type is available, it has the same 64 bits of precision as`int64_t`

, so the approximate quotientqis almost exact. Empirically, |Q-q| is at most 1 for numbers up to 2^{62}.A version working for integers up to 2

^{62}·1.41 is discussed here (in Russian again).Can someone please explain the solution for problem E? I didn't understand it from the Editorial.

"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" Could anybody explain, how do this using KMP algorithm?

What does "For a prefix P, let's split it into some blocks, just like P = SSSS... SSSST, which T is a prefix of S" means? Can anyone show it on some examples?

Let's look at an example: 'abcabcabcab'

We use KMP algorithm to find the

`pre[]`

array in O(n) time.Obviously, for

P=`beads[0..10]`

, our program should getS= 'abc' andT= 'ab'.And for

P=`beads[0..5]`

, it should getS= 'abc' andT= 'abc'.In both samples

Tis a prefix ofS(they may be equal).We know that in the first example,

S=`beads[0..2]`

('abc') andT=`beads[9..10]`

=`beads[0..1]`

('ab').In the second sample

S=T=`beads[0..2]`

('abc').Then through observing we know that

S=`beads[0..idx - pre[idx]]`

andT=`beads[0..idx % (idx - pre[idx] + 1)]`

.After finding out the lengths of

SandT(their exact values don't matter), we can calculate how many times they appeared inPand then follow the instructions in the editorial to find the answer.Thank you. Good explanation)

Glad to be helpful =u=

Oh, I forgot a point. After finding

SandTwe can letA=TandB=S-T, andSSS...SST=ABABA...BA. Therefore if the sequenceSSS...SSTdoes exist forP=`beads[0..i]`

(see the editorial), the answer at position`i`

is '1'. Otherwise, it's '0'. By iterating through the value of`i`

we solve the problem in O(n) time.Found bug

Thanks for the skillful E!

For problem D: Could anyone explain why KMP can divide the original string into SSSSS...SST?

Gotcha. A great problem

Hey, can you explain, I still can't figure it out.Thanks

I solved F using divide & conquer (same as editorial), but I still have no idea how it could be solved using Segment tree (like tourist did). Can anyone give some idea? Thanks :)

For each prefix, we will count number of permutation suffixes. While iterating from left to right, imagine we are at the

ith index.val_{j}=max([j..i]) -min([j..i]) + (i-j)Its obvious that subsequence [

j..i] is a permutation if and only ifval_{j}= 0.Also notice that .

We can update each

val_{j}while iterating from left to right using two monotone queues,(one for minimum and one for maximum). Every change of minimum and maximum can be handled with interval increasing queries.We will use segment tree to apply those queries and asking for number of 0. Because number of zeros is our interest.

At each segment tree node we need to store 2 integers : minimum value, number of elements under this subtree with minimum value.

If minimum of segment tree's root is more then 0 then number of j's where

val_{j}= 0 is also zero. Also that minimum value can not be less then 0, because .Thanks! This solution is very amazing :)

Problem B in golfscript(click run to execute).

Test 14 as example.

http://goo.gl/zwMv93

In problem E:

How should I understand this sentence?

Consider the second query in the sample test, the length of maximal blocks start at 1, 2, 3, 4, 5, 6 are 1, 1, 2, 2, 1, 2, respectively. So one of shortest block starts at 1 with length 1. However, making 1 as start of a block costs 5 blocks, when the optimal solution is 4.

Do I misunderstand anything here?

In your example, if you starts with the 2nd block (with length 1), the result is 4. I think what roosephu meant is that there exist a solution, which starts with a block having shortest length (not all configurations, which starts from minimum block result in optimal solution).

I have no idea how to prove this though, it looks so magical.

If so, we have to iterate over ALL shortest blocks, not ONLY ONE, don't we? In this situation, the time complexity should be

O(N^{2}/T) instead ofO(T*N/T) =O(N), right?Yes, we have to iterate over ALL shortest block. But no, the complexity is

O(N): There areO(N/T) shortest block, and for each iteration, we needO(T).Really??? How to do everything in

O(T) for each block??? We need to find the number of blocks needed when starting in each shortest block, needn't we?As I understand this example indeed shows that the above claim from the editorial is wrong, but that's actually kind of special case, when the whole block

A(using notation from the editorial) is a suffix of some block from the optimal solution.So, we should actually try (

T+ 1) possible start positions —Tpositions inside the blockAand farthestk, such that the block starting fromkentirely covers blockA.It's sufficient to consider one point right after the shortest block in addition. Then any solution will have a block starting in one of these T+1 points. Proof: otherwise all T+1 points are contained in a single block; it means that their sum is <= b, and hence the block T could be extended — a contradiction.

Hi there, being curious here, for your example N = 6 right? what about k? under no circumstances your lengths array can be [1,1,2,2,1,2] for that input, since k must be >= to the max value into the array.

Letting that beside, I followed the tutorial, and I didn't have to check every minimal length block, just one, preserving O(N).

This last fact (using only one minimal block) doesn't seems obvious at all to me, can somebody educate me on this aspect. Best regards.

An alternative explanation to D: Let z[i] be the maximum size of a substring starting at i that is also a prefix. (array z is generated by z-algorithm in O(n), find it here) Let string s be the concatenation of A and B. The maximum size of s is O(n/k). For every possible size of s, we need to check if the next k blocks of size |s| are equal. This is equivalent to checking for(p = 0;;p+=|s|) if z[p]>=|s|. If so, let's look at position p = |s|*k in the string. We know that the answer is 1 for the interval [p-1,p+z[p]-1]. (We can choose the length of A arbitrarily, if |A| is 0 then p-1 works and then we can increase |A| while it still is a prefix.) Now that we have all the possible intervals, let's sort them and iterate through position i to see if it is inside any interval. Complexity: The checking can be done in O(k) for every |s|. Since maximum |s| is O(n/k) the total cost O(n/k * k) = O(n). We also need to sort the intervals.

Is there any solution with O(1) complexity for 526C - Om Nom and Candies?

So there is no such solution? Disappointed :/

норм

Problem tag for problem c says it can be solved using ternary search. Has anyone solved it using ternary search?

I still can't understand Problem C ,what's the meaning of "If the number of the blue candies that Om Nom eats is more than Wr, he could eat Wb red candies instead of Wr blue candies, because Hb × Wr < Wb × Hr" ,if he eats Wb red candies,maybe the total weights he eats becomes larger .So maybe he will eat less other candies. So how to prove it's the best solution? Thank you.

Wb red candies have the same total weight as Wr blue candies, namely Wb*Wr.

I got it,thank you !!!

HI, every one! I'd like to ask for you help. For problem D: First, I figure out the pre pointer by using KMP. Second, for each prefix S, check if len(S) % (len(S)*m-pre[len(S)*m-1]) == 0, then use binary searching find the maximum length of T(the prefix of S), that makes S*K+T meets the requirement.

But it WA on the test 16. Could anyone help me find the bug? here is my code: http://codeforces.com/contest/526/submission/10636215

Thank you!

Am I the only one who thinks some parts of this editorial is poorly written? I have to second guess many things to understand what the author really wants to present. For example, if you read the editorial for D:

Sand somehow its prefixPcan beSSSSSS...ST. Do all theSrefer to the same thing?SSS...S,SS..SS,SS..S. These creates confusion, why not give an example?Q=K...I am confused, too.

Here's my attempt to give a better explanation of problem E after reading the confusing editorial.

The key observation is: Suppose you know the largest

lsuch thata_{1}+a_{2}+ ... +a_{l}≤b. Then the optimal answer must be such that we either we have to take exactly theselnumbers in a single pack or we split this segment into two parts {a_{1}, ...,a_{i}} and {a_{i + 1}, ...,a_{l}}, and they become the suffix and prefix of some other packings respectively.Note that we don't split it into three parts. Let's assume we can get better solution if we do so, i.e. there are three packings:

a_{i + 1}, ...,a_{j}}we can rearrange the packing so that it still becomes three valid packings:

a_{1}, ...,a_{j}}This splits the {

a_{1}, ...,a_{l}} packing into two, but gives the same solution, so it's a contradiction.To prove the original claim, it's intuitive too. Assume we don't do "keep or split into two" strategy, there must be a packing of the form

But as we assumed, we cannot add more elements outside

a_{1}, ...a_{l}, so another contradiction.This implies that you can try all

lpossible splittings, which implies that for thei-th splitting, start ati-th element, and greedily pack the elements. How fast can this be? Suppose we know that, givenb, how far we can pack when we start at thei-th element for alli. Let's denote them asl_{i}. Then you just need to know how many "jumps" you need to perform from thei-th position to pack all numbers.If we know

min{l_{i}} =l^{}* , it is guaranteed that it takes at most jumps to compute the answer. Back to our original splitting strategy, as we tryldifferent splittings, it takes to find the optimal solution. The problem is,l≥l^{}* , it could be as slow as where and . Ifl=l^{}* , the algorithm becomesO(N). To do this, note that by rotating {a_{i}} the observation still holds, so one can just rotate {a_{i}} untill_{1}=l^{}* , and you can get solve it inO(N).To construct the killer case I described above, consider the following sequence:

Try

N= 1000000,b= 500000. It becomes if you don't rotate the first 500000 1s to the left.Can any one explain solution of tourist of problem D(Om Nom and Necklace).

U also c it? scr1, scr2.

yup! i see that too :O why?

For anyone having trouble in reading problem C's editorial, the black strips are all $$$\sqrt{C}$$$.