really really curious about this case. I didn't use such algorithm so didn't meet this problem.

I'm not an author, but if I needed to generate such test, that's how I would do it

Essentially you just need to find some group of possible tests such that there exists a test with a needed property and you can calculate an answer in $$$O(1)$$$, then you can generate random tests of this type until you find the one that satisfies the condition.

For example, in this problem, consider $$$s = [2] \times a + [1] \times b$$$, $$$t = s + [1]$$$. Then it almost works, except the answer is $$$\binom{a+b}{a}$$$, which can't be zero. So instead of this $$$t$$$, take a string, which is lexicographically previous: $$$[2]\times (a-1) + [1] + [2] + [1]\times b$$$. Then the answer is $$$\binom{a+b}{a} - 1$$$ and now you can generate random $$$a$$$ and $$$b$$$ until you get answer $$$0$$$.

Also maybe there is a faster way to find $$$a$$$ and $$$b$$$ such that $$$\binom{a+b}{a} = 1$$$, or maybe there is another type of tests where the formula is easier and you can directly find parameters for it without random generation, but it's not needed here

This is great! Helped me find why my D submission was failing. Just one line change and AC :_)

loved it brother

Consider the $$$i$$$ corresponding to maximum $$$a_i$$$. By letting $$$i$$$ pass the ball to any other person, and these people then pass back to $$$i$$$, we can maximize the $$$i$$$'s passes. And if even in that case, the passes don't meet his requirement, one ball can definitely not complete the task, and the extra ball we need is the rest passes required. However, if we can use all the passes or even the passes is not enough, we can turn to another person and keep the process, which will make one ball acceptable.

I'm also confused about this place.

Excuse me but when we relax $$$dp_i$$$ by $$$dp_j$$$, maybe we should pay attention to $$$pref_{1,i}-pref_{1,j}$$$, or I misunderstand the algorithm?

Sorry for my poor English.

Yes, you are right. We fixed this mistake, sorry.

Maybe you misunderstand the tutorial.

By saying "not count", he don't mean that the answer don't include the case, but mean that the algorithm can't take the case into considering.

Here is my submission which is a little difference to the editorial, but uses the same ideas. 148564648

Consider this expression as max <= sum — max. Now it's obvious for an optimal solution, if we can complete the passes of the player with max passes, all other players' passes have been completed by that time. So consider the following pattern of passes:

____ M ____ M ____ M ____ M ......... ____ M

The above pattern represents the order in which the ball was passed. Here, M represents the player who made max passes. Now obviously, we will want to have atleast one player make a pass between two consecutive passes by the player M. And we can notice that there are max blanks available to fill in. Also, the value sum-max represents the total number of passes made apart from the player with max passes. Therefore, we can say that if remaining passes(sum-max) >= number of blanks(max), then all our blanks can be filled easily and the entire pattern will represent a single chain of passes. However, if sum-max < max, then some blanks will remain empty, which would mean that the chain of passes broke at that point, and we needed an extra ball to begin a new chain.

I hope you understood the point. Try working out some examples by this logic and you'll get the logic

Actually, I did not know how to prove, but my gut feeling told that answer is either max(1,2*mx-s) or 0. F****** adhock

Are you sure ? mine didn't get accepted

https://codeforces.com/blog/entry/100592?#comment-893503

And when we relax the overall answer, how can we get the $$$k$$$? Besides both $$$i$$$ and $$$j$$$ are uncertain.

Not sure if you figured it out. I finally understood by reading other's submission (https://codeforces.com/contest/1648/submission/148574211).

Let's state the sub-problem this way: given two arrays $$$a$$$ and $$$b$$$, we are to answer queries $$$(L,R)$$$ with $$$max_{L<=i<=j<=R}{a_i+b_j}$$$.

Suppose we already have a segment tree, and on each tree node (corresponding to interval $$$[l,r]$$$), we maintain three values: $$$maxa$$$ (the maximum of $$$a$$$ in this interval), $$$maxb$$$ (the maximum of $$$b$$$ in this interval), $$$max$$$ ($$$max_{l<=i<=j<=r}{a_i+b_j}$$$). $$$maxa$$$ and $$$maxb$$$ can be calculated straightforwardly.We will come to $$$max$$$ later.

Now let's consider how to answer queries, and this is the tricky part. It's using the property of the recursion. In the example below, we are answering the query $$$[0,6]$$$ on the given tree. Boxes next to the tree node mean the interval, green means it's not matching the whole interval on the node, and red means it is matching. You can see we process, in order, $$$[0,3]$$$, $$$[3,5]$$$, $$$[5,6]$$$. So we can maintain a running variable, of the maximum values of $$$maxa$$$ seen in the nodes we already processed. The pseudocode is:

void query(
  int c /*index*/,
  int cl, int cr, /*the interval of the node*/
  int l, int r /*the interval to query*/
  int& runningMaxa,
  int& result
) {
  if (cl + 1 == cr || (l == cl && r == cr)) {
    result = max(result, v[c].max);
    result = max(result, runningMaxa + v[c].maxb);
    runningMaxa = max(runningMaxa, v[c].maxa);
    return;
  }
  int mid = (cl + cr) / 2;
  if (l < mid) {
    query(c * 2, cl, mid, l, min(r, mid), runningMaxa, result);
  }
  if (r > mid) {
    query(c * 2 + 1, mid, cr, max(l, mid), r, runningMaxa, result);
  }
}

When we are at node $$$[3,5]$$$, at this moment, $$$runningMaxa$$$ is the maximum of $$$a$$$ in $$$[0,3]$$$. So the above logic give us $$$max_{0<=i<=j<=3}{a_i+b_j}$$$, $$$max_{3<=i<=j<=5}{a_i+b_j}$$$, and finally $$$max_{0<=i<=3, 3<=j<=5}{a_i+b_j}$$$. You can see it's exhaustive for all possible pairs.

And for maintenance of $$$max$$$ on nodes, you just do the same as querying when propagating from child to parent.

For every $$$r$$$ you check each $$$y \leq \frac{c}{r}$$$. In other words you do at most $$$\frac{c}{1} + \frac{c}{2}+\cdots+\frac{c}{c} = c\cdot h_c$$$ iterations. $$$h_c$$$ is the harmonic series. Search it up, it's a very important series which is almost equal to $$$\log c$$$ as $$$c$$$ grows large.

Don't reassign the whole arrays prefix, exist in the test cases. That's $$$t\cdot 2 \cdot 10^6$$$ operations. That's why there is a bound on $$$C$$$.

It is done by considering array $$$cnt_x$$$ — the amount of occurrences of $$$x$$$ in $$$a$$$, and prefix sums for that array.

By using prefix sums.

Now I have understood it and got accepted.

Its main idea is, we maintain the number of chains that cover $$$e_2$$$ but not cover $$$e_1$$$ (then we can calculate the answer for $$$e_1$$$ and $$$e_2$$$ since we know $$$c_{e_1}$$$ and $$$c_{e_2}$$$), and we only need to make sure that this value is correct for $$$e_1$$$ which $$$h_{e_1}=h_{e_2}$$$. So we can show that for some chain there is only $$$O(1)$$$ $$$e_2$$$ that will update the segment tree.

The Russian editorial has explained the details of how we can find these edges that will update the segment tree. If you are good at Russian or you have a nice translator, I advise you to read the Russian editorial. XD

Thank isaf27 very much for his guidance.

What do you mean by "minimal path"?