Она и жадным моделированием заходит за куб :)

I think they should be published soon. You can also ask me if you would like some tips!

спасибо

I am not sure about the approach of C in the editorial, but here's my O(n) approach:

Observation: a[] can be converted into b[] by grouping a[] in non-overlapping segments.

If we start from the left, it is obvious that the answer exists only if the prefix sum (the sum of the first few elements) is equal to b[0] since a[] only consists of positive numbers. This fact could also be inducted to other segments if we consider that previous segments were cut away from a[] and treat the next element as the start of the segment for b[1...n].

Now the only thing we have to care is whether the monster could start the momentum by eating others. By greedy we will assume that we are starting the eating processes of each group from the largest monster (as there are no non-positive elements), if you can't start the eating process (note that the eating process is only needed when the size of the group is larger than 1).

Remember to store the correct positions of the monster during the eating process as the editorial has mentioned.

The editorial for D pretty much nailed it and I don't think my explanation could beat that. Perhaps you should take a look at other's code.

Like this. 21968223

Not very different than what is explained in the editorial. For a group S that needs to get reduced to one monster, find a monster which has maximum value and doesn't have an equal neighbour(if there is no such monster, then no solution). Once he eats this unequal neighbour, he can eat everything else in any order. So you'll either eat everything to the left and then everything to the right, or eat everything to the right and then everything to the left. And this way it's easy to keep track of his position in the final array, without simulating the transformations on the array.

try to use two pointers one starting at first of 1st array and other at start of 2nd array.

first time traverse whole b array to check if solution exists.if doesnt exist print NO and exit

else if yes traverse again second time through 2 nd array and print the solution.

for printing the solution,follow a greedy approach finding the maximum in it and assume it eats all the others in that union

here is the link to my solution of it:http://codeforces.me/contest/733/submission/21949174

Can you prove its correctness? I'm not sure about this.

I can't understand what exactly are you representing with extra[i] array.Can you please elaborate a bit?

It's incorrect. consider following case
4 4
0 0 1 10
100 100 5 1
1 2
1 3
2 3
2 4
10

your solution gives sum 1 and selects edge 3, 1, 4, but the optimal solution should give sum 0 and select 1 2 4.

What's the approach using binary search?

That's a dumb question indeed :P . What you are saying is like this .. 19/3 can be greater than 15/5 + 4/4 . just because you are using all the money it doesn't provide you with more number of dissatisfaction units(because the cost is also high). Mathematically it goes like this.. a*x + (a-1) = Sigma(Bi*Yi). where each Bi is greater than 'a' implies Sigma(Yi) <= x. It's easy to prove :) . However my submission was giving wrong answer on test 75. can anyone please check ? what's special about testcase 75? here's my submission- [submission:21965336]

Even if S % c[i] != 0, floor(S/c[i]) is maximized when c[i] is minimal.

There's a simple argument: Assume you allocate some budget to road j such that c[j] > c[i]. Note that this budget could be moved to road i at no loss (indeed, possibly at a gain).

Thanks @Artemis_Fowl and @OMGTallMonster for explaining! That was indeed dumb.

I was also confused about that one.

The OP says that fix an edge to be reduced and find MST corresponding to that edge.

Now, it would be correct if the cost of that reducing edge was minimal. But what if there was an edge with smaller cost of reducing in that same spanning tree. Then we could reduce the dissatisfaction by reducing that edge. So I thought this, fix a road, find a MST containing that road, where all edges have cost of reduction >= c, where c is the cost of reducing dissatisfaction of the edge we initially chose. But it turns out I don't have to do actually that. What we need to do is that if there are multiple spanning trees of the same weight, then for all those spanning trees, we should choose the tree containing the edge with smallest reducing cost. So, we select an edge P, find MST corresponding to that edge. Suppose w(P) > w(Q) (w(p) = cost of reducing dissatisfaction of the edge p) for some other edge in the MST, then we know that MST(P) >= MST(Q)(either MST(P) = MST(Q), or at least one edge is different with smaller weight, so MST(Q) < MST(P) ), therefore we know that when we finally find MST corresponding to Q, the answer is obviously better and hence no need to find MST with weight >= c.

O(nlogn)

You don't have to do the whole operation. Instead, you just find the LCA to identify the unique cycle that will be created in log time, and then use binary lifting to identify the best edge to be removed.

(When you create the binary lifting lookup table, you lift it in the way that the edges are directed to the parents, that's the way you want to do it anyways, you don't need to reverse it everytime you lookup the table then.)