Fixed. S should be C

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

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.

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:

I. QB*WB + QR*WR <= C

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.

abaa+ba+abaa+ba+abaa

'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_b > sqrt(C), the maximum number of blue candies that can be eaten is floor(C / w_b), which is less than sqrt(C).

We can also say, since w_b > sqrt(C), then w_b * sqrt(C) > C. Therefore, Om Nom can eat at most sqrt(C) blue candies.

We iterate over the number of blue candies and get all possible answers, then get the largest one of them.

for (i = 0; i <= c / wb; i++) {
    // Eat i blue candies and floor((c - i * wb) / wr) red candies.
    long long cur = i * hb + (c - i * wb) / wr * hr;
    if (cur > ans) ans = cur;
}

Oh sorry... I made a mistake.

When neither of Wb and Wr is 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 eat Wb red candies instead of Wr blue candies, because Hb × Wr < Wb × Hr.'

If Om Nom eats Wr blue candies, which weigh Wr × Wb in all, he gets Wr × Hb joy units.

However, if he eats Wb red candies, which also weigh Wr × Wb in all, he gets Wb × Hr joy units.

Since Hb × Wr <= Wb × Hr, the choice of Wb red candies is never worse than Wr blue candies.

Therefore Om Nom should never eat more than Wr blue candies. We iterate over the number of blue candies eaten (which is always less than Wr < sqrt(C)), and find the best answer.

// Assume that Wr < sqrt(C) and Wb < sqrt(C) and Hb * Wr <= Wb * Hr.
for (i = 0; i <= wr; i++) {
    // Eat i blue candies and floor((c - i * wb) / wr) red candies.
    long long cur = i * hb + (c - i * wb) / wr * hr;
    if (cur > ans) ans = cur;
}

cnt_r and cnt_b are the answer.

cnt_r * w_r + cnt_b * w_b ≤ c

if cnt_b > w_r then cnt_b = w_r + x and cnt_r * w_r + w_r * w_b + x * w_b ≤ c, so we can take w_b red candies instead of w_r blue ones, since w_r * h_b < w_b * h_r we will get more joy units — which is contradiction, thus cnt_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.net/blog/entry/17281#comment-220872

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)

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

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.

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¹⁶ + 61, accepted now.

Let's look at an example: 'abcabcabcab'

We use KMP algorithm to find the pre[] array in O(n) time.

  idx = [0123456789X] (X is ten...)
beads = "abcabcabcab"
  pre = [00012345678]

Obviously, for P = beads[0..10], our program should get S = 'abc' and T = 'ab'.
And for P = beads[0..5], it should get S = 'abc' and T = 'abc'.
In both samples T is a prefix of S (they may be equal).

We know that in the first example, S = beads[0..2] ('abc') and T = 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]] and T = beads[0..idx % (idx - pre[idx] + 1)].

After finding out the lengths of S and T (their exact values don't matter), we can calculate how many times they appeared in P and then follow the instructions in the editorial to find the answer.

Gotcha. A great problem

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

val_j = max([j..i]) - min([j..i]) + (i - j)

Its obvious that subsequence [j..i] is a permutation if and only if val_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 .

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.

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 — T positions inside the block A and farthest k, such that the block starting from k entirely covers block A.

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.

Om Nom is a great mathematician and he quickly determined the answer.

So there is no such solution? Disappointed :/

По-моему, eatmore объяснил довольно неплохо.

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

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 l such that a₁ + a₂ + ... + a_l ≤ b. Then the optimal answer must be such that we either we have to take exactly these l numbers in a single pack or we split this segment into two parts {a₁, ..., 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:

1. 
2. {a_i + 1, ..., a_j}
3. 

we can rearrange the packing so that it still becomes three valid packings:

1. 
2. {a₁, ..., a_j}
3. 

This splits the {a₁, ..., 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₁, ...a_l, so another contradiction.

This implies that you can try all l possible splittings, which implies that for the i-th splitting, start at i-th element, and greedily pack the elements. How fast can this be? Suppose we know that, given b, how far we can pack when we start at the i-th element for all i. Let's denote them as l_i. Then you just need to know how many "jumps" you need to perform from the i-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 try l different splittings, it takes to find the optimal solution. The problem is, l ≥ l * , it could be as slow as where and . If l = l * , the algorithm becomes O(N). To do this, note that by rotating {a_i} the observation still holds, so one can just rotate {a_i} until l₁ = l * , and you can get solve it in O(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.

yup! i see that too :O why?

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