Даже Флеш завидует скорости, с которой опубликовали разбор.

Kак можно полностью увидеть тест/претест к задаче?

The most brilliant solution to problem D must be the one with max-flow min-cut theorem in my opinion :)

D can be solved with O(n) compexity. Imagine a graph where it is n * 2 vetices. From source you have edges to 1, 3 .. 2 * k — 1 vetices with capacity INF. From i'th vertice if i is odd you have edge to i + 1 vertice with capacity a[i]. From i'th vertice if i is even you have edges to i + 1, i + 3, i + 2 * k — 1 with capacity INF. if i is even and i / 2 >= n — k you have edge to sink (smth like that i can make little mistakes) And you can instead of building such a big graph and running max flow algorithm just try to find minimum cut. And after some greedy thoughts it is clear that you must choose segment [i, i + k — 1] with minimum sum of a[j] where j belongs to [i, i + k — 1]. It can be done with just a pair of loops in your code. See my implementation for details.

http://mirror.codeforces.com/contest/965/submission/37610259

Can someone explain why my solution passed tests. I want to believe that complexity is but i can't proove it.
Shortly it is dynamic programming on tries. dp_v, x = minsum. Where v is number of vertice in tries. x — number of words that we didn't written in final set of prefix (it means that we will write it higher in tries — with smaller prefix).
There I do stupid smth like knapsack on a tree. dp_v, x = min(dp_v, x, dp_to, y + dpprev_z for all y, z witch satisfies condition y + z == x. It is usual knapsack on a tree.
So it should work in O(n²). But i added condition dp[v].size() = min(depth, cnt[v]) where cnt[v] — number of terminal vertices in subtree. And it gives states in dp because it is a trie. But there is also transitions and i've stuck here how to estimate number of transitions?

This is implementation http://mirror.codeforces.com/contest/965/submission/37615468.

Can i solve problem div. 2 C using bisection method?

Is this logic correct?

For C, Bonus 1:

Same logic as given.

Just one change: to find xMax formula used earlier was: n / ( k * (i — 1) + 1 ), where i is the current D (in a for loop of D). (I did + 1 at-last to include Arkady as leftover use was not allowed). It should be less or equal to M.

Here, we just have to first check:

if(n % (k * (i — 1)) != 0) then Arkady will get leftover in last level and (n / (k * (i — 1)) in other levels. (Need to handle a case when value of n / (k * (i — 1)) exceeds M as it will be added to leftover and so on...)

else same as earlier.

If this is correct then can anybody tell me how to make it work for large values of D? (1 <= D <= n)

For E, I had right idea but failed in implementing minimizing depth.

There is a much simpler, two pointer solution to D. Probably similar to the one bicsi gave.

The idea is to maintain a 0...w array 'reach' where reach[i] tells us the number of frogs that have reached the i'th unit at the i'th step. Note that reach[i] can't be greater than a[i], because we can't accommodate more frogs than the number of stones. We start by having infinite number of frogs having reached the 0th unit. For any i <= l, reach[i] = a[i]. This is because the frogs from 0th unit can directly jump till here.

The key insight here is that for any i > l, we should start letting the leftmost frogs who can reach i, jump till i. I.e first all frogs from the (i — l)th unit jump till i, then (i — (l-1))th and so on. We do this till either i'th unit's capacity is reached, or we've run out of frogs. You can use a pointer 'j' to track where the leftmost frogs are. Just make sure that j >= i — l. Answer is reach[n].

http://mirror.codeforces.com/contest/965/submission/37625008

I don't get why in C one doesn't need to compute min x for the iterated d like in the editorial. Computation of max x always works, but for me it seems that sometimes max x could make us take candies more than d times for the first person. Why is it never the case?

Hi! What is "smaller-to-larger optimization"? Does someone has a link to read about it?

Thanks

Does a binary search solution works for C ?

how can i solve C's bonus 2 part?

Anyone else solved D with BIT?

can someone please explain E!

Haha, this problem is also solvable via DP. Let dp[i] — the max number of frogs that can get up to distance i. We calculate dp[i] based on values of dp[i — l]...dp[i — 1], only we delete dp[i] frogs from the dp array starting from index i — l, not to count duplicate frogs. This TLs on test #16, so I simply keep track of the current sum dp[i — l]...dp[i — 1] in a variable, which runs in ~200 ms.
Code: https://mirror.codeforces.com/contest/965/submission/46261137

Editorial to https://mirror.codeforces.com/contest/965/problem/C is one of the most arrogant ones I ever did read on codeforces.

Wow, so many solutions to problem D. Here is yet another one :P

I do a DP on a greedy. I break the entire $$$w$$$ length into $$$w/l$$$ segments of length $$$l$$$ each. And for each segment, I try to fill up this segment in the rightmost way, greedily. This can be done by DP.

88428808