You have two array of N ≤ 105 integers A1,A2…AN and B1,B2…BN. In a single step Sereja can choose two indexes i and j (1 <= i <= j <= n) and we make Ap equal to (Ap + 1) modulo 4 if p is an integer from the range [i:j].
What is the mininal number of steps necessary in order to make the array A equal to the array B?
0 ≤ Ai,Bi ≤ 3
First, we make one array instead of two in such a way that you increase the subsegments in it till it’s of the form 0-0-0-…-0. Then consider a problem without modulo that is, the problem : given a1,a2…an and you can decrease a subsegment by one, what will be the answer?
Our answer will be sum max(0, a[i] - a[i - 1]) over i = 2 … n, which we arrive at greedily. How?
Here we should increase some subsegments by 4 for this sake. It’s clear that the answers for the initial array and the array where the subsegments are increased by 4 may differ but the arrays themselves will NOT differ because we increase by 4 modulo 4.
So now we:
- Get one array instead of two, where we will apply -1 operations, say a’.
- and we need to make it zero by applying these operations.
- Also, we have to add 4 to some subsegments in order to minimize this term: sum max(0, ai - a_i-1) for i = 1 … n. a is fictive and equals to zero.
Let’s get the array c = a’ - a’i - 1 where a’ is the array we’ve obtained in step 1.
And increasing subsegment by 4 means decreasing some cj and increasing some ci where i < j.
The next part, we can see by pseudo code:
ans=k1=k2=0 for i = 1 to n: if c[i] < 2: // if the value of c[i] is *small*, we can use it as it is ret + = max ( 0, c[i] ) // ie. max ( 0, a[i] - a[i-1] ) // we can use this cell later as the beginning of some segment (segment where we increase all terms by 4) // if it's value is an appropriate for this, let's remember it if (c[i] == -3): k1++ if (c[i] == -2): k2++ else: // we will use this cell as end of some segment if k1>0 : // we use this because ret will increase less if we use these cells. // if we use some cell c[j] having c[j]=-3, where j<i, c[j] will increase by 4 and c[i] will decrease by 4 k1--; // one cell has been used ret ++ // because c[j] will become 1 afterwards, earlier it was contributing 0 to ret. c[i] - = 4 // this is the end of subsegment, so we decrease by 4 elif k2>0: k2-- // used ret += 2 // earlier contribution was 0, but now it will contribute (-2+4) to the ret. c[i] -= 4 // this is the end of subsegment, so we decrease by 4 // after making the segment the value of c[i] might become small // and therefore, the current cell can be a beginning of some further segment if (c[i] == -3) k1 ++ if (c[i] == -2) k2 ++ ret += max( c[i] , 0 ) print ret