SEINC - Editorial

darkshadows · May 17, 2014, 9:54am

PROBLEM LINK:

Practice
Contest

Author: Sergey Nagin
Tester: Sergey Kulik
Editorialist: Lalit Kundu

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

Greedy

PROBLEM:

You have two array of N ≤ 10⁵ integers A₁,A₂…A_N and B₁,B₂…B_N. In a single step Sereja can choose two indexes i and j (1 <= i <= j <= n) and we make A_p equal to (A_p + 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 ≤ A_i,B_i ≤ 3

EXPLANATION:

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 a₁,a₂…a_n 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, a_i - 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 c_j and increasing some c_i 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

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

mathman · May 17, 2014, 3:35pm

My approach was similar for the first part that is we have to minimize the sum of max(0,a[i]-a[i-1]). For the next part I assumed that we may have to increase some a[i] by 4 atmost once (I do not have a proof though). I have also tried the same thing for the case that some a[i]s may be increased by 4 atmost 10 times. I am unable to get any example where some a[i] maybe increased by more than once.

I use dp after this. Consider the array dp[2][n]. Where dp[i][j] denotes the minimum number of operations required to get the array a[0…j] if i no. of 4s are added to a[j]. So we have the recursion dp[i][j]=min(dp[0][j-1]+max(0,a[j]+4*i-a[j-1]),dp[1][j-1]+max(0,a[j]+4*i-a[j-1]-4)). Using this, I compute the whole dp array and output min(dp[0][n-1],dp[1][n-1]).

This method looks fine to me if my first assumption is correct. I have implemented the same here for the case where a[i]s maybe incremented atmost 10 times. But the code gives WA in the 5th test file.

Is there any test case where my assumption doesn’t hold true?

smiley007 · May 26, 2014, 11:13am