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

Автор decoder__, история, 4 года назад, По-английски

Need help with the solution of this problem https://codeforces.net/contest/1392/problem/C How to reach intuitively at the solution mentioned in the editorial?

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

What do we need? We need to get the non-decreasing array. Then, let's use the given operation on each element x, such that element before x is bigger than x. In other words, let's use the operation on index i, if a[i — 1] > a[i]. We can easily keep the difference between any two adjacent elements after index i by using the operation on suffix(a[i], a[i + 1], ..., a[n — 1]). It works, because each element on suffix will increase by equal value. To skip the part with addition on suffix(it's too slow to do it), let's solve the problem from right to left.

90106658