Increasing by Modulo

This problem is from codeforces contest 1169C

Problem Statement

We are given an array of integers, each integer is between 0 and m−1 inclusive. The integers are a1,a2,…,an

In one operation you can choose k indices i1,i2,…,ik such that 1≤i1<i2<…<ik≤n. We can then modify each element E at the each of the chosen k indices from E to ((E+1)mod m). The integer m is fixed for all operations and indices and is given to you in the beginning.

Here (x mod y) denotes the remainder of the division of x by y

We want to make the array non-decreasing with the minimum number of such operations. Find this minimum number of operations.

Solution

Observations

1. The number of operation depends on the final values that each of the elements take. There are multiple solution to make it non-decreasing.
2. The number of operations for the element that needs maximum changes is the final answer.
3. With practice its easy to see that in problems like this we want to try all possible answers X and check if its possible to make the array non-decreasing in at most X operations. We then want to find the smallest X.
4. If its possible in X operations. It is also possible to do it in X+1, X+2 … X+inf operations.

Problem for practice : Atcoder- ARC075 Widespread

Now given X operations what is the best policy for modification of elements?

If we are at index i we need to be only concerned with element at i-1 and ensure that a(i-1) ≤ a(i). If this is ensured at all i between 1 to n then X is correct answer else it’s wrong.

Instead of considering the previous value let us hold a variable “prev” which is the value which is as small as possible to the left.

Case 1: if prev ≤ a(i)

This is ok for us and everything is going great. The ideal way to keep prev as small as possible would be to have a(i) == prev. So in case if prev < a(i) let us modify it to a(i) with our operation. So how many operations do we need to modify a(i) to prev ? Assume it as k. Then (a(i) + k)%m= prev %m .

We know that prev and a(i) are less than m and greater than 0 from problem statement. We also know that since prev < a(i), hence a(i) + k will be greater than m, but it is also less than twice m : m ≤ a(i) + k < 2*m ; prev < m

Therefore we can write (a(i) + k ) %m = a(i) + k- m and prev%m = prev

Hence (a(i) + k)-m = prev; k = mod- (a(i)-prev)

Now we have to check if k > X . If it is true then we do not have enough operations to make a(i) == prev and since its ok to leave prev < a(i) we leave a(i) unmodified . Therefore we modify our prev to a(i). Meaning the smallest possible element towards left is a(i) here on.

Case 2: prev > a(i)

This is a problem for us. Therefore we have to make a(i) ==prev, since that will result in minimum number of operations. Here the number of operations would be k = prev-a(i).

If k > X then we know that the value of X we took is too small and X is a wrong answer.

We have to increment the value of X and try again.

This check runs in O(n). Call this function ok(X) which returns true if X is enough and false otherwise.

How to reach optimal X?

One way would be to start with X = 0 and increment by +1 if ok(X) returns false. Since we want minimum the first ok(X) that returns true is the final answer.

This takes O(n²) or O(n*m) since X increments from 0 to m and each time ok(X) takes O(n). This is too slow for the time given by online judge.

You can note that the return for ok(X) from 0 to m will look something like false false false false false false true true true true true for some given array. We then want the index of first true, which will be our answer. We can do this using binary search, since its similar to finding index of first 1 in an array [0,0,0,0,1,1,1,1,1].

And hence O(n*m) becomes O(n*log(m)) since we need to try only log(m) X’s compared to before.

You can submit your solution here. But remember to be logged in.

CODE

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i = a; i <= b; i++)
using namespace std;
typedef long long ll;
const ll N = 3e5+5;
ll n, m;
vector<ll>a(N);
bool ok(ll maxi) {
    ll prev = 0;
    FOR(i,0,n-1) {
        if(prev <= a[i]) {
            ll k= m - (a[i] - prev);
            if(k > maxi) prev = a[i];
        } else {
            ll k= prev - a[i];
            if(k > maxi) 
                return false;
        }
    }
    return true;
}
int main()
{
   cin>>n>>m;
    FOR(i,1,n) cin>>a[i-1];
    
    ll l,r;
    l = 0, r = m;
    while((r-l)>1) {
        ll mid = l + (r-l)/2;
        if(ok(mid)) {
            r = mid;
        } else {
            l = mid+1;
        }
    }
    
    if(ok(l)) 
        return !printf("%lld",l);
    printf("%lld",r);
    return 0;
}