in general, The Question generally focusses on making every consecutive 3 elements of the array divisible by 3.
Important Claim: Every time we take the consecutive three elements of the array, we can fix or increment every element of the array except the first two elements to make it divisible by 3.
Consider an Example ,
4
1 2 5 8
Here on taking 1 + 2 + 5 = 8 , on incrementing 5 → 6 , it becomes divisible by 3
similarly 2 + 6 + 8 = 16 , we can increment 8 twice to → 10,
1 2 6 16 ( possible final array)
This is just one of the possibility , Just try to play around with different numbers fixing first two numbers and you will get the hang of it.
So, In general first element of final array can have remainder → 0, 1, 2
similarly, second element of final array can have remainder → 0, 1, 2
Hence , 3 x 3 = 9 states are possible
so , we are just applying a brute force solution to find the minimum increments by traversing through each 9 states and finally adjusting the remaining numbers according to it.
You can imagine it like a window being formed and we are trying to slide that window.
C++ Code
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int32_t main(){
int test;
cin >> test;
while(test--){
int size;
cin >> size;
int arr[size];
//in order to input the elements
for(int idx = 0; idx < size; idx += 1){
cin >> arr[idx];
}
//main logic of the problem
//there are in total nine possible states
int result = INT_MAX;
for(int first = 0; first < 3; first += 1){
for(int second = 0; second < 3; second += 1){
int increment = 0;
int x = arr[0];
int y = arr[1];
//now we have to adjust the value of x
while(x % 3 != first){
increment += 1;
x += 1;
}
//now we have to adjust the value of y
while(y % 3 != second){
increment += 1;
y += 1;
}
for(int idx = 2; idx < size; idx += 1){
int z = arr[idx];
int total = x + y + z;
while(total % 3 != 0){
z += 1;
total += 1;
increment += 1;
}
x = y;
y = z;
}
result = min(result, increment);
}
}
cout << result << '\n';
}
}
Hope! I am able to clarify the doubt.
Note: I came with this solution from solution video and little bit of brainstorming. Feel free to ping me for any doubts. Cheers !! ;D
1 Like
Wow, nice solution! I butchered this problem with straightforward dp sadly XD
My DP solution+code here: Solution
UPD: My dp solution is an extravagant way of writing the editorial solution in hindsight XD
1 Like
can you explain a bit more how you thought of that dp method while tackling the problem in your explanation for the answer ? basically how you got that there is possibility of repeating common subproblems in this question
yeah i would also like to know the way
Why the following approach fails:
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
static int recUtil(int i,int arr[]){
if(i+2==arr.length){
return 0;
}
int sum=arr[i]+arr[i+1]+arr[i+2];
int toAdd=3-sum%3;
int min=Integer.MAX_VALUE/2;
if(toAdd==3){
return recUtil(i+1,arr);
}
//incrementing single
for(int k=i;k<=i+2;k++){
arr[k]+=toAdd;
min=Math.min(min,toAdd+recUtil(i+1,arr));
arr[k]-=toAdd;
}
if(toAdd==2){
arr[i]+=1;
arr[i+1]+=1;
min=Math.min(min,toAdd+recUtil(i+1,arr));
arr[i]-=1;
arr[i+1]-=1;
arr[i+1]+=1;
arr[i+2]+=1;
min=Math.min(min,toAdd+recUtil(i+1,arr));
arr[i+1]-=1;
arr[i+2]-=1;
arr[i]+=1;
arr[i+2]+=1;
min=Math.min(min,toAdd+recUtil(i+1,arr));
arr[i]-=1;
arr[i+2]-=1;
}
return min;
}
public static void main (String[] args) throws java.lang.Exception
{
Scanner input= new Scanner(System.in);
int T=input.nextInt();
while(T--!=0){
int size=input.nextInt();
int arr[]=new int[size];
for(int i=0;i<size;i++){
arr[i]=input.nextInt();
}
System.out.println(recUtil(0,arr));
}
}
}
I’ve added more detail. I’m confused, do you mean overlapping subproblem property? If you can’t see why it’s overlapping then you should learn dp basics and recursion. If you meant you can’t see the optimal substructure property intuitively, same applies.
By the way for anyone wondering about the math formula mentioned in dan’s solution to make
(i % mod) = (j % mod) for any general mod by adding 1’s to i is = (j - i + mod) % mod for bigger mods
2 Likes
Can you explain,why your solution passes without taking long ?
Bro can you please explain more of why did you think it as dp problem,and can you please explain your code ,please
why sliding window solution not get accepted . infact it ran for 2 test cases. but ultimately failed
was this solution accepted?
You should Learn about time complexity. In case of normal sliding window, the time limit gets exceeded.
if you see the first part of the code , I have defined int itself as long long int and that’s why I used int32_t for main function . This is usually a hack used by me as I find it very convenient.
i understood now how you think of the recursion approach and which finally led to a dp approach basically here i was not cleared from first what dp states i would need to choose but your sol seems make it clear . is there a good way of analyzing what dp states one needs to consider in a problem ?
Ok, solving more dp problems leads to making things more intuitive. There are various blogs out there on how to come up with dp solution eg: (Dynamic Programming: Prologue - Codeforces) ← There are 2 other blogs inside this one, btw.
I also started out by actually mastering recursive style dp first which is more intuitive especially when you already understand recursion well so you could try that.
2 Likes
bro in your code when setting values of dp for first 3 elements why you didn’t chose the min ones. You just iterated for possible combinations of i+j+k%3==0 and just set the dp value to ch(a[0],i)+ch(a[1],j)+ch(a[2],k) wouldn’t we want to set this value to minimum.
I checked all those states the same reason why this editorial bruteforced for all 3^2 possible starting points. It is possible the optimal solution might start from ANY of those combinations and NOT just the ones that give immediate minimum answer. If it always did, then there is no point using dp and we could have just done greedy in O(N) time complexity.
If you mean, why i didn’t set all those states to the minimum of all those states. That would be simply incorrect and not follow the dp statement i made in the explanation. I’ve updated the dp statement to make it easier to understand.
I also now tried without dp finally got it accepted . logic was like what was explained in the editorial . below is the code if anyone needs. https://www.codechef.com/viewsolution/100869962 . will try dp based approach too later .
bro in your code when setting values of dp for first 3 elements why you didn’t chose the min ones.