# MINIMISEINV - Editorial

Author: satyam_343
Testers: apoorv_me, tabr
Editorialist: iceknight1093

TBD

None

# PROBLEM:

You’re given a binary string S of length N, of which you can flip at most K elements.
Minimize the number of inversions in the final string.

# EXPLANATION:

Suppose we choose some elements to flip, of which x are initially 1's and y are initially 0's. (Of course, x+y \leq K.)
Then, it can be observed that:

• It’s optimal to choose the leftmost x 1's in S.
• It’s optimal to choose the rightmost y 0's in S.
• Every chosen 1 should appear before every chosen 0.
Proof

Suppose a 1 at position i is flipped and a 1 at position j isn’t flipped, but i \gt j.
Then, choosing to flip the 1 at index j instead will strictly reduce the number of inversions in the resulting binary string.
This can be verified by looking at which pairs of inversions i and j contribute to before and after the flip - in particular, the pair (i, j) was itself an inversion initially and won’t be now; while no pair that was initially a non-inversion turns into an inversion.

This proves that it’s optimal to choose the first x 1's in S to flip.
A similar proof shows that flipping the last y 0's in S is optimal.

Finally, note that if we flip a 0 at index i and a 1 at index j, but i \lt j, then we’d have fewer inversions by simply not performing the flip at index i (which is allowed, since we can perform \leq K flips and not exactly K).

This tells us that there are only really only \mathcal{O}(K) candidate strings to check.
These candidate strings are obtained by flipping the first x 1's in S (for each 0 \leq x \leq K), and then flipping the last (K-x) 0's in S (or every 0 after the x'th 1, if there are less than (K-x) of them.)

Further, each candidate can be checked in linear time - after all, the inversion count of a binary string can be computed in linear time.

How?

Since the string is binary, the number of inversions is just the number of times \texttt{10} appears as a subsequence in it.
This can be computed with a simple loop: for each i from 1 to N, if S_i = 0, add to the answer the number of ones before index i.

We have \mathcal{O}(K) candidates, and each is checked in \mathcal{O}(N) time, giving us an \mathcal{O}(N\cdot K) algorithm.
Since K \leq N and the constraints guarantee that the sum of N^2 is bounded, this is fast enough.

# TIME COMPLEXITY:

\mathcal{O}(N\cdot K) per testcase.

# CODE:

Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define nline "\n"
#define all(x) x.begin(),x.end()
const ll MOD=998244353;
const ll MAX=500500;
ll inv(string s,ll n){
ll consider=0,ans=0;
for(ll i=1;i<=n;i++){
if(s[i]=='0'){
ans+=consider;
}
else{
consider++;
}
}
return ans;
}
ll sum_n=0;
void solve(){
ll n,k; cin>>n>>k;
string s; cin>>s;
s=" "+s;
sum_n += n;
assert(sum_n <= (ll)2e5);
vector<ll> track[2];
for(ll i=1;i<=n;i++){
track[s[i]-'0'].push_back(i);
}
ll ans=MOD*MOD;
reverse(all(track[0]));
auto do_op=[&](ll l,ll rem,string t){
for(auto it:track[0]){
if(it < l){
break;
}
if(rem==0){
break;
}
t[it]='1';
rem--;
}
ans=min(ans,inv(t,n));
};
do_op(1,k,s);
for(auto it:track[1]){
s[it]='0';
k--;
if(k<=-1){
break;
}
do_op(it,k,s);
}
cout<<ans<<nline;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}

Tester's code (apoorv_me, C++)
#include<bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "../debug.h"
#else
#define dbg(...)
#endif

#ifndef LOCAL
struct input_checker {
string buffer;
int pos;

const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";

input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}

int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
now++;
}
return now;
}

assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}

string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}

int readInt(int minv, int maxv) {
assert(minv <= maxv);
assert(minv <= res);
assert(res <= maxv);
return res;
}

long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
assert(minv <= res);
assert(res <= maxv);
return res;
}

auto readInts(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
}
return v;
}

auto readLongs(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
}
return v;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}

assert((int) buffer.size() == pos);
}
};
#else

struct input_checker {
string buffer;
int pos;

const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";

input_checker() {
}

int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
now++;
}
return now;
}

assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}

string readString(int minl, int maxl, const string &pattern = "") {
string X; cin >> X;
return X;
}

int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res;  cin >> res;
assert(minv <= res);
assert(res <= maxv);
return res;
}

long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res;  cin >> res;
assert(minv <= res);
assert(res <= maxv);
return res;
}

auto readInts(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
}
return v;
}

auto readLongs(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
}
return v;
}

}

}

}
};
#endif

int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);

auto __solve_testcase = [&](int test) {
int N, K; cin >> N >> K;
string S; cin >> S;

auto doit = [&](int x, int y, string S) {
dbg(x, y, S);
for(int i = 0 ; i < N ; ++i) if(x > 0 && S[i] == '1') {
S[i] = '0'; --x;
}
for(int i = N - 1 ; i >= 0 ; --i) if(y > 0 && S[i] == '0') {
--y;  S[i] = '1';
}
dbg(S);
int inv = 0, one = 0;
for(int i = 0 ; i < N ; ++i) {
if(S[i] == '1')   one += 1;
else  inv += one;
dbg(S[i], one, inv);
}
return inv;
};

int res = doit(0, 0, S);
for(int x = 0 ; x <= K ; ++x) {
res = min(res, doit(x, K - x, S));
}
cout << res << '\n';
};

int NumTest = 1;
cin >> NumTest;
for(int testno = 1; testno <= NumTest ; ++testno) {
__solve_testcase(testno);
}

return 0;
}

Tester's code (tabr, C++)
#include <bits/stdc++.h>
using namespace std;

#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

long long inverse(string &s) {
long long res = 0, sum = 0;
for (char c : s) {
if (c == '0') {
res += sum;
} else {
sum++;
}
}
return res;
}

void solve(int n, int k, string &s) {
auto ans = inverse(s);
for (int x = 0; x <= k; x++) {
string t = s;
for (int i = 0, j = 0; i < n; i++) {
if (j < x && t[i] == '1') {
t[i] = '0';
j++;
}
}
for (int i = n - 1, j = 0; i >= 0; i--) {
if (j < k - x && t[i] == '0') {
t[i] = '1';
j++;
}
}
ans = min(ans, inverse(t));
}
cout << ans << "\n";
}

////////////////////////////////////////

#define IGNORE_CR

struct input_checker {
string buffer;
int pos;

const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";

input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
#ifdef IGNORE_CR
if (c == '\r') {
continue;
}
#endif
buffer.push_back((char) c);
}
}

assert(pos < (int) buffer.size());
string res;
while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
assert(!isspace(buffer[pos]));
res += buffer[pos];
pos++;
}
return res;
}

string readString(int min_len, int max_len, const string& pattern = "") {
assert(min_len <= max_len);
assert(min_len <= (int) res.size());
assert((int) res.size() <= max_len);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}

int readInt(int min_val, int max_val) {
assert(min_val <= max_val);
assert(min_val <= res);
assert(res <= max_val);
return res;
}

long long readLong(long long min_val, long long max_val) {
assert(min_val <= max_val);
assert(min_val <= res);
assert(res <= max_val);
return res;
}

vector<int> readInts(int size, int min_val, int max_val) {
assert(min_val <= max_val);
vector<int> res(size);
for (int i = 0; i < size; i++) {
if (i != size - 1) {
}
}
return res;
}

vector<long long> readLongs(int size, long long min_val, long long max_val) {
assert(min_val <= max_val);
vector<long long> res(size);
for (int i = 0; i < size; i++) {
if (i != size - 1) {
}
}
return res;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}

assert((int) buffer.size() == pos);
}
};

int main() {
input_checker in;
cerr << tt << endl;
int sn = 0, sn2 = 0;
while (tt--) {
auto s = in.readString(n, n, "01");
sn += n;
sn2 += n * n;
solve(n, k, s);
}
cerr << sn << " " << sn2 << endl;
assert(sn <= 2e5);
assert(sn2 <= 5e7);
return 0;
}

Editorialist's code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
s = input()
ans = n*(n-1)//2

for i in range(k+1):
cur = list(s)
rem, last = i, -1
for j in range(n):
if cur[j] == '1' and rem > 0:
cur[j] = '0'
rem -= 1
last = j
rem = k - i
for j in reversed(range(last+1, n)):
if cur[j] == '0' and rem > 0:
cur[j] = '1'
rem -= 1
invs, ones = 0, 0
for j in range(n):
if cur[j] == '0': invs += ones
else: ones += 1
ans = min(ans, invs)
print(ans)


Duplicate problem, can be found here:

2 Likes

Can anyone please explain me why this [Code] fails (CodeChef: Practical coding for everyone)

This problem should be made unrated

1 Like

include <bits/stdc++.h>
using namespace std;

define mod 1000000007
define int long long

void printvec(vector &A)
{
for (int i = 0; i < A.size(); i++)
cout << A[i] << " ";
cout << “\n”;
}
int minInversions(string &s, int k, int ind, vector<vector> &dp)
{
if (k == 0)
{
int inversions = 0;
int cnt = 0;
for (int i = 0; i < s.size(); ++i)
{
if (s[i] == ‘1’)
{
cnt++;
}
else
{
inversions += cnt;
}
}
return inversions;
}

if (ind >= s.size())
{
return INT_MAX;
}

if (dp[ind][k] != -1)
{
return dp[ind][k];
}

int minInv = INT_MAX;

for (int i = ind; i < s.size(); ++i)
{
s[i] = (s[i] == '0') ? '1' : '0';
minInv = min(minInv, minInversions(s, k - 1, i + 1, dp));
s[i] = (s[i] == '0') ? '1' : '0';
}

minInv = min(minInv, minInversions(s, k, ind + 1, dp));

return dp[ind][k] = minInv;


}
void solution()
{
int n, k;
cin >> n >> k;
string s;
cin >> s;
vector<vector> dp(n, vector(k + 1, -1));
int result = minInversions(s, k, 0, dp);
cout << result << endl;
}

signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t–)
{
solution();
}
// solution();
return 0;
}
what is wrong in this code???

Please make this problem unrated instead of making the whole round unrated.

Duplicated problem should right away be made unrated.

The contest remains rated

can anyone give me a test case where greedy will fail.

Can I know why?

I followed a two-pointer approach, flipping the character of left-most 1/right-most 0, reducing the most inversions.

Submission ID : 1074357079

Please let me know the wrong interpretation of the logic of my solution.

i have also tried to solve using two pointer approach based on which element is adding maximum inversion count and then flip it from the left or from the right. but failed. didn’t able to create any testcase where this fail. if you get any testcase or any proof please mention thanks

@d2s2 @deeping_dive
1
16 2
1110000011010110

Your Solution will Probably give 19. (by Flipping the First One and the Last Zero). But The Optimal way is to flip Two First Consecutive Ones

2 Likes

@an_k_ush
What’s the expected output for this testcase?
Why greedy approach will choose first 1 and last 0?
It will pick first two 1’s i guess…

The last attempt made by someone on this question was 2 years ago.

@anishray042

F(P) => No of Inversions reduced if P is flipped
P1 is left Ptr
P2 is right Ptr

Ok, you prolly have condition like if (F(P1)>=F(P2)) then Flip P1.
The Case I had mentioned before will not work if you dont have equality sign.

For your Solution. It will probably fail on the following Input
1
8
10011100
Your Soln will give you 3, By Flipping the First 1 and The Last 0
But the Optimal is to Flip the Last 2 0’s. Which gives Answer = 2

@an_k_ush
I already have the failing test case.
The thing is if I add both scenarios, I will get correct answer as 2.
What I mean is if I use (F(P1)>=F(P2)) to get one ans1 and get other ans2 via (F(P1)>F(P2)). Your test case will pass after min(ans1,ans2).

I am trying to generate a case which will fail the code having both checks.
I know the reason for greedy approach is equality sign. We can’t actually decide which pointer to proceed at that point as it impacts further iteration.

I am generating a case which requires logic check reversal as we go further with iteration of pointers.

P.S.- Logic check here means (F(P1)>=F(P2)) or (F(P1)>F(P2)). Basically which pointer to give priority when F(P1)==F(P2).

Thanks mate.

Well, To your Surprise. You can’t know which Pointer to give priority to. You have to check All the possibilities. That’s why the expected soln has to be run in O(K.N).
But Even then there is way to do this in O(N+K). But Its also exploring all the K possibilities of Flipping

1 Like