PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: kryptonix171
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
BFS (or willingness to do casework…)
PROBLEM:
You’re given a string S. You can do the following:
- Choose i (1 \lt i \lt N) and set S_{i-1} = f(S_{i-1}, S_i) and S_{i+1} = f(S_{i+1}, S_i).
f(x, y) = 1 if x = y = 0, and 0 otherwise.
Find a sequence of at most 3N moves that maximizes the number of ones in S.
EXPLANATION:
Our aim is to maximize the number of ones; and the function f(x, y) outputs a 1 only when both arguments are 0.
So, it makes sense to try and get two zeros next to each other, so that one of them can be turned into a 1.
Let i be the index of the leftmost 0 in S (meaning everything to the left of i is already 1).
Let’s try to turn this into a 1.
- If S_{i+1} = 0, we can directly operate on index i+1 (as long as i+1 \lt N), and S_i will turn into a 1.
Note that this doesn’t change anything to the left of i: those remain ones. - If S_{i+1} = 1, we want to turn it into a 1 instead.
One way of doing this is by operating on index i - but this will lead to S_{i-1} also becoming 0, which we don’t want.
The only other way is to operate on index i+2 - which is only possible when i+2 \lt N.- If i+2 \lt N, we can then perform one operation on i+2 followed by one on i+1, turning S_i into 1 without changing anything before it.
Notice that as long as i is “small enough” (meaning i+2 \lt N), we’re in fact able to turn S_i to 1 without much effort.
So, repeatedly choosing the leftmost zero like above, we can always make some very large prefix of the string contain only 1's, using at most 2 operations for each index.
This leaves us with a small suffix to solve: say, of length 5.
As it turns out, every binary string of length 5 can be made to have at least 4 ones by using the above operation (the only way to have 5 ones is to start with them; everything else can be made to have 4 which is clearly optimal).
One simple way of solving this is to just run a bruteforce: for example, start with the last 5 characters, and run a BFS by repeatedly performing every possible move.
At the end, you can trace back the moves you made to reach some optimal final string.
This is fast because there are only 2^5 = 32 possible strings of length 5, which is really small.
When N \leq 4, it’s not always possible to end up with N-1 or more ones (for example, 1010 for N = 4 cannot ever be made to have three ones).
However, you can simply run the exact same bruteforce for these strings too, since they’re small.
It is also possible to casework your way out of N \leq 5 if you try hard enough, but I don’t really recommend that.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
void solve(istringstream cin) {
int n;
cin >> n;
string s;
cin >> s;
if ((int) count(s.begin(), s.end(), '1') >= n - 1) {
cout << 0 << '\n';
return;
}
vector<int> a;
auto add = [&](int i) {
if (s[i] == '0') {
s[i + 1] ^= 1;
s[i - 1] ^= 1;
} else {
s[i + 1] = '0';
s[i - 1] = '0';
}
a.emplace_back(i);
};
for (int i = n - 1; i >= 3; i--) {
if (s[i] == '0') {
if (s[i - 1] == '0') {
add(i - 1);
} else {
add(i - 2);
add(i - 1);
}
}
}
if (s[1] == '0' && s[2] == '0') {
// ?0011...
add(1);
// ?0111...
}
if (n >= 4 && s[0] == '0' && s[1] == '0') {
// 0011
add(2);
// 0010
add(1);
// 1000
add(2);
// 1101
}
if (n >= 5 && s[0] == '0' && s[2] == '0') {
// 01011
add(3);
// 01010
add(2);
// 00000
add(3);
// 00101
add(1);
// 10001
add(2);
// 11011
}
cout << a.size() << '\n';
for (int i : a) {
cout << i + 1 << '\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);
}
}
string readOne() {
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);
string res = readOne();
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);
int res = stoi(readOne());
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);
long long res = stoll(readOne());
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++) {
res[i] = readInt(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
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++) {
res[i] = readLong(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
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);
}
};
int main() {
input_checker in;
int tt = in.readInt(1, 1e4);
in.readEoln();
int sn = 0;
while (tt--) {
int n = in.readInt(1, 3e5);
in.readEoln();
sn += n;
string s = in.readString(n, n, "01");
in.readEoln();
ostringstream sout;
sout << n << '\n';
sout << s << '\n';
solve(istringstream(sout.str()));
}
cerr << sn << endl;
assert(sn <= 3e5);
in.readEof();
return 0;
}
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
string s; cin >> s;
vector<int> ops;
auto op = [&] (int i) {
ops.push_back(i);
if (s[i] == '1') s[i-1] = s[i+1] = '0';
else {
s[i-1] = '0'^'1'^s[i-1];
s[i+1] = '0'^'1'^s[i+1];
}
};
for (int i = 0; i < n-5; ++i) {
if (s[i] == '1') continue;
if (s[i+1] == '1') op(i+2);
op(i+1);
}
// Brute the remaining
string rem = s.substr(max(0, n-5));
string chosen = rem;
map<string, int> dist, opr;
map<string, string> par;
dist[rem] = 0;
queue<string> qu;
qu.push(rem);
while (!qu.empty()) {
auto st = qu.front(); qu.pop();
if (count(begin(st), end(st), '1') > count(begin(chosen), end(chosen), '1')) {
chosen = st;
}
for (int i = 1; i+1 < st.size(); ++i) {
auto nw = st;
if (nw[i] == '1') nw[i-1] = nw[i+1] = '0';
else {
nw[i-1] = '0'^'1'^nw[i-1];
nw[i+1] = '0'^'1'^nw[i+1];
}
if (dist.find(nw) == dist.end()) {
dist[nw] = dist[st] + 1;
opr[nw] = i;
par[nw] = st;
qu.push(nw);
}
}
}
int xtra = 0;
while (chosen != rem) {
ops.push_back(opr[chosen] + max(0, n-5));
chosen = par[chosen];
++xtra;
}
reverse(rbegin(ops), rbegin(ops) + xtra);
cout << size(ops) << '\n';
for (int x : ops) cout << x+1 << ' ';
cout << '\n';
}
}
.