Codeforces DIV3 Round 642 C and D Video editorials

editorial
,
1

C editorial : - YouTube
Code : Submission #80100571 - Codeforces

D editorial : - YouTube
Code : Submission #80114767 - Codeforces

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

2

Please help me in the E problem of this same round(642).
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.

3

@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";
}