Thanks for the insight.
@an_k_ush
That’s quite obvious.
That’s why I am trying to generate a test case for my satisfaction. I know this approach is incorrect if iteration needs reversal internally.
Nice problem though. Gave contest after long time. Nice experience. 
@anishray042
Check for this Test Case. Optimal Answer is 29. May give you wrong
1
32 8
01101101101100001001100111001110
Here is my O(N) solution during contest.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL solve() {
int n, k;
string str;
cin >> n >> k;
cin >> str;
vector<int> v0, v1;
vector<int> num0(n, 0), num1(n, 0);
for(int i = 0; i < n; ++ i) {
num0[i] = i ? num0[i-1] : 0;
num1[i] = i ? num1[i-1] : 0;
if(str[i] == '0') {
v0.push_back(i);
num0[i] ++;
} else {
v1.push_back(i);
num1[i] ++;
}
}
reverse(v0.begin(), v0.end());
if(v0.size() <= k || v1.size() <= k) return 0LL;
int lft = v1[0], rgt = v0[k];
LL res = 0LL, zCnt = 0;
for(int i = rgt; i >= lft; -- i) {
if(str[i] == '0') zCnt += 1LL;
else res += zCnt;
}
if(lft > rgt) return 0LL;
LL tot = res;
for(int i = 1; i <= k; ++ i) {
tot -= (LL)(num0[rgt] - num0[lft]);
lft = v1[i], rgt = v0[k-i];
if(lft > rgt) return 0LL;
tot += (LL)(num1[rgt] - num1[lft] + 1LL);
res = min(res, tot);
}
return max(0LL, res);
}
int main() {
int T; cin >> T; while(T --) {
cout << solve() << endl;
}
}
this means to say that when you choose x 1’s from left side then no 1’s from this x should lie after the leftmost chosen 0, bcoz you we will choose only those 0’s from right side which can make ‘1111…’ like string on the right side so as to minimise the inversions
can you please explain me what approach you have followed for this solution
Can anyone explain where my solution is wrong? I have taken two extreme cases, that is flipping K left most 1’s and K right most 0’s. I tried the mentioned test cases in the thread and getting right answer. My Approach - flipping and then counting number of inversions.
include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int t;
cin>>t;
while(t–){
int n,k,cnt1=0,t_i=0,j=0,t_cnt1=0,t_ti=0;
cin>>n>>k;
string s,t;
cin>>s;
t = s;
//cout<<t<<endl;
for(int i =0;i<n;i++){
if(j==k){
break;
}
if(s[i]==‘1’){
s[i]=‘0’;
j++;
}
}
j = 0;
for(int i = t.size()-1;i>=0;i–){
if(j==k){
break;
}
if(t[i]==‘0’){
t[i]=‘1’;
j++;
}
}
//cout<<s<<endl;
for(int i =0;i<n;i++){
if(s[i]==‘1’)
cnt1++;
}
for(int i =0;i<n;i++){
if(t[i]==‘1’)
t_cnt1++;
}
for(int i = s.size()-1; i>=0; i–){
if(s[i]==‘0’){
t_i += cnt1;
}
else{
cnt1–;
}
if(cnt1 < 0)
cnt1 = 0;
}
for(int i = t.size()-1; i>=0; i–){
if(t[i]==‘0’){
t_ti += t_cnt1;
}
else{
t_cnt1–;
}
if(t_cnt1 < 0)
t_cnt1 = 0;
}
int ans = min(t_i, t_ti);
cout<<ans<<“\n”;
}
}
It is the same approach as the editorial.
The difference is that in the editorial, he calculated whole inversions for each i.
So there is no relation between whole inversions for i and whole inversions for i+1.
But I found the relation between them and implemented.
Calculating whole inversions for i+1 from whole inversions for i take O(1) time.
So it is O(N) solution.
I am working as a freelancer, so I am a little busy. Sorry for my un-intuitive explanation.
If you can not understand, please DM me via telegram or Discord.
discord: enthusiastmax
telegram: @enthusiastMAX
I am using two pointers approach to solve it in O(n) time
can someone please tell me for which test case it is failing?
js```
const myFunc = (nAndK, str) => {
let [n, k] = nAndK.split(’ ').map(Number)
let l = 0
let r = str.length - 1
let inversions = (() => {
let count = 0
let zerosInWindow = 0
for(let i = str.length - 1; i >= 0; i--) {
if(str[i] === '0') {
zerosInWindow++
continue
}
count += zerosInWindow
}
return count
})()
if(inversions === 0) return 0
const sum = str.split('').map(Number).reduce((acc, v) => v+acc ,0)
let a = str.length - sum
let b = sum
while(k > 0 && l < r) {
while(str[l] && str[l] !== '1'){
l++
a--
}
while(str[r] && str[r] !== '0') {
r--
b--
}
if(b >= a) {
inversions -= b
r--
a--
} else {
inversions -= a
l++
b--
}
k--
}
return inversions
}