CF Edu Round 97 Ques E

https://codeforces.com/contest/1437/problem/E

In this ques if we have to only find min number of changes required to make the array strictly increasing and array elements should be in some range. How to do this part?

@carre @everule1

anyone

I don’t understand your question. It’s explained in the tutorial that you can doit the same way LIS algorithm

I didn’t understand how can it be solved using LIS.

I meant if k=2 which are 1 and n, then all the elements at indices [2, n-1] must be greater than at index 0 and less than at index n.

It would be helpful if you can explain little more.

First of all, forget about fixed positions and try to understand why the LIS algorithm is useful here. The minimum number of positions you need to change are those that are not in increasing order yet, so the answer is number_of_positions - LIS.

Now suppose you have 2 successive fixed positions on the indices x and y and let i be an index between x and y , that is, x <i <y . Since you need all positions between x and i to have increasing numbers (similar between i and y ), you need these relationships to hold
a_x + (i-x)< = a_i
a_i + (y-i) <= a_y

Reorganizing
a_x -x <= a_i-i
a_i -i <= a_y-y

To make it easier to verify those relations we can replace a [i] with a [i] -i for every i .
For every i that is not a fixed position you have 2 possibilities

  • if it doesn’t satisfy the above relations then you should change it
  • otherwise, consider it to calculate the LIS of this segment

I think that in this particular problem, the code might be even more helpful than explanations. Take a look at the code given in the tutorial of the problem, it’s really clear.

1 Like

For the first eq. should the sign be opposite ?

yes, sorry, fixed

Thanks, finally got it

1 Like