Yes that works but it's just easier to code if you sort it.

Thanks it's edited now

Run second loop(nested one) from i. Not i+1.

we could solve in n^2*log(n) by tutorial method

We can solve this in nlog^2(n) with sparse table + binary search or segment tree.

Which part do you not understand? When cnt1>0 (as given in the editorial) or in the other case?

Sure. Say that we end in the state (a₁ - b₁, a₂ - b₂, ..., a_n - b_n), obviously with Then one can check by induction that regardless of the path taken to get there, we will have

Therefore, it suffices to compute

Note that in the last sum, this is precisely the [x^k] coefficient of the following generating function:

Now multiply out the last polynomial: say that

This is O(n²) time to do, or with FFT (unnecessary here). Then we can compute that the [x^k] coefficient of the last expression (by expanding out e^nx) is

Putting this all together gives that the answer is

It's solution without generating function is really nice!

:D

It doesn't mean sort and then shift, even though that what it says. It means: for a sorted array we can just cyclic shift. For an un-sorted array, we do the same thing: replace the i-th smallest element with the (i + 1)-th smallest, and replace the largest with the smallest.

I finally understand. Thank you so much.

In the begining of main function you put "ios::sync_with_stdio(false);" without "cin.tie(0); cout.tie(0);".. This may be the reason.

I can explain my online solution — it would be a good way to verify if it's correct.

An edge is in some MST if and only if it is not the heaviest edge in every cycle. To check that I used Kruskal. I process all the edges with weight X at the same time. If an edge connects 2 vertices which are already in the same component, it is the heaviest in the cycle. Otherwise it will not be the heaviest in every cycle as we constructed everything we could so far, using edges with weight < X and these vertices are still in separate components. It means that every cycle in which that edge can exist would have edges of weight >= X.

The following part has been modified — not fully verified:

In addition to that, not all of these edges with weight X can exist within the same MST but they can exist separately in some MST's. The problem is that they can create a cycle, when we include cheaper edges. In order to detect such edges we can remember the state of each vertex (the id of components of both vertices when we process an edge in Kruskal).

Now I process queries — I check that every edge can exist in some MST. If that's the case, there is one more thing to check: that these edges do not form cycles — I just run another Kruskal on them, using remembered component numbers.

We can solve using segment tree with binary search in O(nlogn*logn). And also we can solve it in O(nlogn).

actually the original problem was with limitation n < 1e5 and a[i] < 1e9 but we decided to change it. You can see O(nlogn) solution here by omidazadi

You can do that without additional memory. Iterate line from the end and maintain killer index. Set index to current person if current person's claw extends further than current killer's claw. See this submission for implementation example.

I can give you my understanding of that, consider edges with weight X in query, we remove all edges with weight greater than or equal to X in graph. In this new graph, we consider if the edges with weight X in query is "neccessary". If the edge connect two nodes which have already been connected, we called this edge "unnecessary", if there is an "unnecessary" edge in query, the answer will be NO.

Reason is here.

Agree with you (unless we wrongly understood what was mentioned in the editorial). In fact I tried to implement it the way described in the editorial, but it does not pass the tests.

When you sort the input array 'a' you'll have to keep track of indices where the elements were originally present in 'a'. For this, you can use a vector of pairs having first and second 'a[i]' and 'i'.

We shift so that all the indices (except one) the newly formed array(after sorting and shifting) will have elements greater than 'a'.

The sorted vector 'v' from first para will help to arrange in this manner. the 'ith' element of v (i.e. v[i].first )would be placed at the position where the i-1th element was present (i.e. v[i-1].second).

http://codeforces.com/blog/entry/56000#comment-397225

Hope this helps.

The same problem was here: there are two sets of indexes which their corresponding elements have equal sums. S1 = {2,5}, S2 = {3,5}. But I still haven't the accepted solution.

I just ACed with my own persistent dsu implementation and a bunch of optimizations.

https://codeforces.com/contest/891/submission/109523741

Enjoy :)

This solution is fully online :D

Size of the set should be < n

If you're given an array of unique elements like $$$[1,2,3,4]$$$ then it's easy to see that a shifted array like $$$[2,3,4,1]$$$ would work. So if you're given an unordered array, do the same value shifting as if it were sorted, except the indices are not necessarily sorted.