Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Блог пользователя 74TrAkToR

Автор 74TrAkToR, 20 часов назад, По-русски

Спасибо за участие!

Идея: 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...
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
27 минут назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
27 минут назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем Akulyat (предыдущая версия, новая версия, сравнить).

»
только что, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.