Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

74TrAkToR's blog

By 74TrAkToR, 20 hours ago, translation, In English

Thank you for participating!

Idea: 74TrAkToR. Preparation: NicoRobin, 74TrAkToR.

Tutorial is loading...

Idea: 74TrAkToR. Preparation: voventa, 74TrAkToR.

Tutorial is loading...

Idea: 74TrAkToR. Preparation: orolik, 74TrAkToR.

Tutorial is loading...

Idea: _supersonic_. Preparation: TimVen74, 74TrAkToR.

Tutorial is loading...

Idea: bogatrv. Preparation: bogatrv, 74TrAkToR.

Tutorial is loading...

Idea: voventa, 74TrAkToR. Preparation: 74TrAkToR.

Tutorial is loading...
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
27 minutes ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Akulyat (previous revision, new revision, compare).

»
a moment ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Editorial for D: Let's say the elements of array are: a1, a2, a3, and a4. If we perform the operation at a3, then array changes to: a1, a2 + a3, -a3, a4 + a3.

Now the overall sum of array didn't change so what happened after 1 single operation? We basically swapped pref2 and pref3 because: Initially, pref2 = a1 + a2 and pref3 = a1 + a2 + a3. After operation, pref2 = a1 + a2 + a3 and pref3 = a1 + a2.

Once you get this, the overall problem is already solved. We can swap any two prefix. Now since we want every element of array to be non-negative, at any point, the prefix sum shall be always non-decreasing. And since we can swap two adjacent prefix sum, all we need to check is how many swaps it will take to make prefix sorted.

This is basically counting number of inversions in an array which can be achieved either by classical Merge Sort algorithm or an Ordered Set.