decoder__'s blog

By decoder__, history, 4 years ago, In English

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?

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
4 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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