PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: rudra_1232
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
You’re given a binary string S, and parameters K and X. The following operation can be performed:
- Choose any subsequence of S that has at most X inversions, and the inversion count is a multiple of K.
Then, delete this subsequence from S.
Find the minimum number of operations needed to empty S.
EXPLANATION:
The condition on inversions is quite hard to work with: keeping the count \leq X is one thing, but also ensuring the count is a multiple of K while doing this seems nearly impossible.
However, it can be observed that there is one case that’s quite simple: when the number of inversions is 0.
After all, 0 is certainly \leq X, and is also a multiple of K no matter what K is.
A subsequence having zero inversions essentially just means it’s sorted - or, specifically in the case of binary strings, has all its zeros before all its ones.
In particular, if a binary string contains only zeros or only ones, it certainly has zero inversions.
This immediately tells us that the answer is no larger than two: use one move to delete all the ones, and then another move to delete all the zeros.
So, all that needs to be done is to check if the answer is 1: if it isn’t, then the answer is 2.
For the answer to be 1, the only possible move is to delete the entire string at once.
This can easily be checked by computing the inversion count of the whole string and checking if it satisfies the conditions.
While there are general methods to compute the inversion count of an array in \mathcal{O}(N\log N) time, we can also utilize the fact that we’re working with a binary string to obtain a simple linear algorithm, because an inversion in a binary string is simply a subsequence that’s \texttt{"10"}.
- Let \text{inversions} = 0 and \text{onect} = 0.
- For each i from 1 to N,
- If S_i = 1, increment \text{onect} by 1.
- Otherwise, add \text{onect} to \text{inversions}.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, x, k = map(int, input().split())
s = input()
invs = ones = 0
for c in s:
if c == '1': ones += 1
else: invs += ones
if invs <= x and invs%k == 0: print(1)
else: print(2)
Tester's code (C++)
//Har Har Mahadev
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define precise(i) cout<<fixed<<setprecision(i)
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define take(a,n) for(int j=0;j<n;j++) cin>>a[j];
#define give(a,n) for(int j=0;j<n;j++) cout<<a[j]<<' ';
#define vpii vector<pair<int,int>>
#define db double
#define be(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define pob pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bpc(x) __builtin_popcountll(x)
#define btz(x) __builtin_ctz(x)
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int, int>, null_type,less<pair<int, int> >, rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
const long long INF=1e18;
const long long M=1e9+7;
const long long MM=998244353;
int power( int N, int M){
int power = N, sum = 1;
if(N == 0) sum = 0;
while(M > 0){if((M & 1) == 1){sum *= power;}
power = power * power;M = M >> 1;}
return sum;
}
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() && !isspace(buffer[now])) {
now++;
}
return now;
}
string readOne() {
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);
string res = readOne();
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);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
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) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
}
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) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
}inp;
int smn = 0;
void solve()
{
int n,x,k;
// cin >> n >> x >> k;
n = inp.readInt(1,500'000);
smn += n;
inp.readSpace();
x = inp.readInt(0,1000'000'000);
inp.readSpace();
k = inp.readInt(1,1000'000'000);
inp.readEoln();
string s;
// cin >> s;
s = inp.readString(n,n,"01");
inp.readEoln();
int inv = 0;
int o = 0;
for(auto &x : s){
if(x == '1')o++;
else inv += o;
}
if(inv <= x && ((inv%k) == 0))cout << 1 << "\n";
else cout << 2 << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef NCR
init();
#endif
#ifdef SIEVE
sieve();
#endif
int t;
// cin >> t;
t = inp.readInt(1,500'000);
inp.readEoln();
while(t--)
solve();
inp.readEof();
assert(smn <= 500'000);
return 0;
}
