# Codeforces DIV3 Round 642 C and D Video editorials

Code : Submission #80100571 - Codeforces

Code : Submission #80114767 - Codeforces

Thank you for your valuable time.
Any suggestion / Query is welcome.
CodeNCode.

I have tried problem E by top down dp approach but was unable to do it and all the online solutions
I searched took the same approach but I was unable to understand their solution.
Please do a video tutorial for problem E as well.
A recursive+memoization solution would be preferred because that is more intuitive.

@posiedon99
You can do these

1. Cluster all K-apart characters into single string
2. Use kadane to find maximum subarray where cnt(1) - cnt(0) is greatest, and Turn all 0s in that subarray to 1 and all 1’s outside that subarray to 0
3. Check for all clusters
Implementation
``````void solve(int test_case){
int n,k;
cin >> n >> k;
string a;
cin >> a;
string c[k];
int total = 0;
int ans = INT_MAX;
loop(i,0,n)c[i%k]+=a[i],total+=a[i] == '1';
loop(i,0,k){
int l=0,r=0,la=0,ra=0,s=0,ss=0,t=0;
loop(j,0,c[i].size()){
t+=c[i][j]=='1';
if(c[i][j] == '0')s-=1;
else s+=1;
if(ss < s)ra = j,la=l,ss=s;
if(s < 0)l=j+1,s=0;
}
if(t == 0){
ans = min(ans,total);
continue;
}
int z = 0, o = 0;
loop(j,la,ra+1)z+=c[i][j]=='0';
loop(j,0,la)o+=c[i][j]=='1';
loop(j,ra+1,c[i].size())o+=c[i][j]=='1';
ans = min(ans,total-t+o+z);
}
if(ans == INT_MAX)ans = 0;
cout << ans << "\n";
}

``````