SEINC - Editorial

editorial
greedy
may14
medium-hard
seinc

#1

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 ≤ 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

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 a1,a2…an and you can decrease a subsegment by one, what will be the answer?
Our answer will be sum max(0, a* - 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:

  1. Get one array instead of two, where we will apply -1 operations, say a’.
  2. and we need to make it zero by applying these operations.
  3. 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* < 2: // if the value of c* is *small*, we can use it as it is    
          ret + = max ( 0, c* )  // ie. max ( 0, a* - 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* == -3): k1++    
          if (c* == -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* 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* - = 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* -= 4 // this is the end of subsegment, so we decrease by 4    
          // after making the segment the value of c* might become small      
          // and therefore, the current cell can be a beginning of some further segment      
          if (c* == -3) k1 ++    
          if (c* == -2) k2 ++    
          ret += max( c* , 0 )     
print ret     

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution


#2

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

I use dp after this. Consider the array dp[2][n]. Where dp*[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*[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*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?


#3

I didnt understand the purpose of steps used in solution at all…Can anyone explain me in some other words please how did one get to the above described approach…thanking you in advance


#4

I didnt understand the purpose of steps used in solution at all…Can anyone explain me in some other words please how did one get to the above described approach…thanking you in advance


#5

I didnt understand the purpose of steps used in solution at all…Can anyone explain me in some other words please how did one get to the above described approach…thanking you in advance


#6

I didnt understand the purpose of steps used in solution at all…Can anyone explain me in some other words please how did one get to the above described approach…thanking you in advance


#7

I didnt understand the purpose of steps used in solution at all…Can anyone explain me in some other words please how did one get to the above described approach…thanking you in advance


#8

I am unable to understand either…It is very bad explained. Can somebody help me?