Спасибо за участие!
Идея: 74TrAkToR. Разработка: NicoRobin, 74TrAkToR.
Tutorial is loading...
Идея: 74TrAkToR. Разработка: voventa, 74TrAkToR.
Tutorial is loading...
Идея: 74TrAkToR. Разработка: orolik, 74TrAkToR.
Tutorial is loading...
Идея: _supersonic_. Разработка: TimVen74, 74TrAkToR.
Tutorial is loading...
Идея: bogatrv. Разработка: bogatrv, 74TrAkToR.
Tutorial is loading...
Идея: voventa, 74TrAkToR. Разработка: 74TrAkToR.
Tutorial is loading...









Auto comment: topic has been updated by Akulyat (previous revision, new revision, compare).
Автокомментарий: текст был обновлен пользователем Akulyat (предыдущая версия, новая версия, сравнить).
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.