PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Yash Kulkarni
Preparer: Tejas Pandey
Testers: Nishank Suresh, Nishant Shah
Editorialist: Nishank Suresh
DIFFICULTY:
2111
PREREQUISITES:
Case analysis, observation
PROBLEM:
You have a binary string S. In one move, you can choose a subsequence of length 3 and delete its first and last characters. What is the lexicographically maximum string that you can turn S into?
EXPLANATION:
The solution described below involves heavy use of casework, although better solutions do exist.
We can make the following observations:
- It’s always good to keep as many 1-s in the string as we can. Deleting 1-s should be a last resort, and should be done from the back of the string if possible
- Similarly, if any zeros are left we would like them to be present towards the end of the string, if possible. Ideally, they would form a suffix
- An odd-length contiguous block of zeros can be brought down to a single zero
- An even length contiguous block of zeros can be brought down to two zeros
This leads us to a solution by case analysis.
If S consists of only a single character, it is optimal to not perform any operations and just print S
Now, suppose S contains both 0-s and 1-s. We can divide this into two cases: the number of zeros is odd, and the number of zeros is even.
Even number of zeros
If possible, we would like to delete every single non-suffix zero without deleting any of the 1-s. Is this always possible?
Unfortunately, not always. We have several cases.
- Suppose all the zeros form a single contiguous block
- If this block is the suffix, it is optimal to do nothing
- Otherwise, this block can be brought down to size 2. Now, depending on how many 1-s are present after this block, either both zeros can be deleted (if there are \geq 3 ones), one zero can be deleted (if there are 2 ones), or no more deletions are done (\leq 1 zero)
- Otherwise, we have more than one block. In this case, it is always possible to delete every zero - however, we would like to keep some of them in the suffix if possible.
- If S ends with a 1, delete all 0-s
- Otherwise, let the suffix of zeros be of length x.
- If x is odd, all but one zero from the non-suffix zeros can be deleted, and the remaining zero can be deleted by consuming one suffix zero
- If x is even, we further have two cases.
- If the non-suffix zeros form a single block, they can all be deleted
- Otherwise, they form a single block and can be brought down to size 2, and then these last 2 deleted by using two of the suffix zeros
Odd number of zeros
If we do not delete any of the 1-s, at least one zero will be left. Note that it is always possible to delete zeros (without deleting ones) such that exactly one zero is left. We want this zero to be as much to the right as possible. So, once again we have several cases.
-
Suppose the last character of the string is a 0, i.e, there is a suffix of zeros.
- If the zeros form a single block as the suffix, no operations need to be performed
- If there are three or more contiguous blocks of zeros
- If the suffix has odd length, the other zeros are even in number and occur in two or more blocks, hence can all be deleted
- If the suffix has even length, the other zeros are odd in number and can be brought down to a single zero, which can then be removed by using one suffix zero
- If there are exactly two contiguous blocks of zeros
- If the suffix has even length, similar to above we can remove all non-suffix zeros and one suffix zero
- If the suffix has odd length, there are again two cases
- If the suffix has length \gt 1, we can remove all non-suffix zeros and two suffix zeros
- Otherwise, the suffix has length exactly 1, and the non-suffix zeros are reduced to exactly two contiguous zeros. Now, we use the suffix to remove one of these zeros, leaving us with a string of the form 111\ldots 1011\ldots 111, which can be solved as a special case that depends on the length of the suffix of ones.
-
Suppose the last character of the string is a 1
- if there is exactly one block of zeros, it reduces to 111\ldots 1011\ldots 111 which we have solved previously
- If there are exactly two blocks of zeros,
- If the second block has size \gt 1, all zeros except one from this block can be deleted, and now the string is in 111\ldots 1011\ldots 111 form
- If the second block has size = 1, all zeros except one from the first block can be deleted, and now the string is in 111\ldots 1011\ldots 111 form
- If there are more than two blocks of zeros, it is always possible to delete all zeros except one from the very last block, after which the string is in 111\ldots 1011\ldots 111 form and can be solved.
That takes care of every case. Whew!
With careful implementation, this entire solution can be implemented in \mathcal{O}(N).
You may look at the editorialist’s code for an implementation of the casework above. The preparer uses similar but slightly different casework, while the tester had a different solution that computes several candidate strings, checks which ones of them are achievable, and takes the maximum of all of these.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Preparer's Code (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
//freopen("inp7.in", "r", stdin);
//freopen("out7.out", "w", stdout);
int t;
cin >> t;
int sm = 0;
while(t--) {
string s;
cin >> s;
assert(s.size() <= 100000);
sm += s.size();
assert(sm <= 300000);
int tot = 0, sz = 0;
vector<int> grps;
for(int i = 0; i < s.size(); i++) {
if(s[i] - '0') {
if(sz) grps.push_back(sz), tot += sz;
sz = 0;
} else sz++;
}
if(s.size() < 3 || tot == 0) {
cout << s << "\n";
continue;
}
if(!sz && grps.size() == 2 && (grps[0]%2) == 0 && grps[1] == 1) {
for(int i = 0; i < s.size() - tot - 1; i++) cout << "1";
cout << "\n";
continue;
}
if(sz) {
if(tot&1) {
for(int i = 0; i < s.size() - tot - sz; i++)
cout << "1";
for(int i = 0; i < sz - 1; i++)
cout << "0";
cout << "\n";
} else {
if(grps.size() != 1) {
for(int i = 0; i < s.size() - tot - sz; i++)
cout << "1";
for(int i = 0; i < sz; i++)
cout << "0";
cout << "\n";
} else {
int l1 = 0, l2 = 0;
for(int i = 0; i < s.size() - sz; i++)
if(s[i] == '0') l1 = l2, l2 = i;
if(sz == 1) {
if(l2 == s.size() - 3) {
for(int i = 0; i < s.size() - tot - sz - 1; i++) cout << "1";
cout << "01";
} else {
for(int i = 0; i < s.size() - tot - sz - 1; i++)
cout << "1";
}
cout << "\n";
} else {
for(int i = 0; i < s.size() - tot - sz; i++) cout << "1";
for(int i = 0; i < sz - 2; i++) cout << "0";
cout << "\n";
}
}
}
} else {
if(tot&1) {
int lst = 0;
for(int i = 0; i < s.size(); i++)
if(s[i] == '0') lst = i;
if(lst == s.size() - 2) {
for(int i = 0; i < s.size(); i++)
if(i == lst || s[i] == '1') cout << s[i];
}
else {
for(int i = 0; i < s.size(); i++)
if(i != lst + 1 && s[i] == '1') cout << s[i];
}
cout << "\n";
} else {
if(grps.size() != 1) {
for(int i = 0; i < s.size(); i++)
if(s[i] == '1') cout << s[i];
cout << "\n";
} else {
int l1 = 0, l2 = 0;
for(int i = 0; i < s.size(); i++)
if(s[i] == '0') l1 = l2, l2 = i;
assert(l2 == l1 + 1);
if(l1 == s.size() - 3) {
for(int i = 0; i < s.size(); i++) {
if(i != l1 && i != l2 && s[i] == '0') continue;
cout << s[i];
}
cout << "\n";
} else if(l1 == s.size() - 4) {
for(int i = 0; i < s.size(); i++) {
if(i != l1 && s[i] == '0') continue;
if(i == l2 + 1) continue;
cout << s[i];
}
cout << "\n";
} else {
for(int i = 0; i < s.size(); i++) {
if(s[i] == '0') continue;
if(i == l2 + 1 || i == l2 + 2) continue;
cout << s[i];
}
cout << "\n";
}
}
}
}
}
}
Tester's Code (C++)
#include <bits/stdc++.h>
using namespace std;
bool possible_to_remove(string s, string output)
{
if (s == output)
{
return true;
}
if (output.empty())
{
return false;
}
int len = s.length();
int output_len = output.length();
if (len < output_len || (len - output_len) % 2 != 0)
return false;
vector<int> prefix_match(len, 0);
vector<int> suffix_match(len, 0);
int ptr = 0;
for (int i = 0; i < len; i++)
{
if (ptr < output_len && s[i] == output[ptr])
{
ptr++;
prefix_match[i]++;
}
if (i > 0)
prefix_match[i] += prefix_match[i - 1];
}
if (prefix_match[len - 1] != output_len)
return false;
ptr = output_len - 1;
for (int i = len - 1; i >= 0; i--)
{
if (ptr >= 0 && s[i] == output[ptr])
{
suffix_match[i]++;
ptr--;
}
if (i != len - 1)
{
suffix_match[i] += suffix_match[i + 1];
}
}
vector<int> prefix_zero_count(output_len, 0);
for (int i = 0; i < output_len; i++)
{
if (output[i] == '0')
prefix_zero_count[i]++;
if (i > 0)
prefix_zero_count[i] += prefix_zero_count[i - 1];
}
for (int i = 1; i < len - 1; i++)
{
int left_match = prefix_match[i - 1];
int right_match = suffix_match[i + 1];
// we want that deleted segment is not contiguous, so we'll build output such that
// it contains some segment from left and right is deleted
// take some part from left : its length is [0 , left_size - 1]
// take middle char s[i]
// take some part from right : its length is [0 , right_size - 1]
// part taken from left => L
// part taken from right => R
// L + R + 1 = output_len
// 0 <= L <= left_size - 1
// 0 <= R <= right_size - 1
// L <= prefix_match[i - 1]
// R <= suffix_match[i + 1]
int max_L = min(i - 1, prefix_match[i - 1]);
int max_R = min(len - i - 2, suffix_match[i + 1]);
// j => character taken from left
// j => (0 , max_L)
// j >= (output_len - 1 - max_R, output_len)
int j_min = output_len - 1 - max_R;
int j_max = max_L;
if (j_min <= j_max)
{
int range_length = j_max - j_min + 1;
int zeros_in_range = prefix_zero_count[j_max];
if (j_min > 0)
zeros_in_range -= prefix_zero_count[j_min - 1];
if (s[i] == '0')
{
if (zeros_in_range > 0)
return true;
}
else
{
if (zeros_in_range < range_length)
return true;
}
}
}
return false;
}
string solve(string s)
{
int len = s.length();
vector<int> zero_indices;
for (int i = 0; i < len; i++)
{
if (s[i] == '0')
{
zero_indices.push_back(i);
}
}
int zero_count = zero_indices.size();
int one_count = len - zero_count;
if (zero_count == 0)
{
return s;
}
int first_zero = zero_indices[0];
int last_zero = zero_indices.back();
bool zeros_consecutive = (last_zero - first_zero + 1) == zero_count;
if (zeros_consecutive && last_zero == len - 1)
{
return s;
}
vector<string> possible_outputs;
// No zeros
for (int one_count = len - zero_count - 2; one_count <= len - zero_count; one_count++)
{
string temp = "";
for (int j = 0; j < one_count; j++)
temp += '1';
possible_outputs.push_back(temp);
}
// Single zero at last position
for (int one_count = len - zero_count - 2; one_count <= len - zero_count; one_count++)
{
string temp = "";
for (int j = 0; j < one_count; j++)
temp += '1';
temp += '0';
possible_outputs.push_back(temp);
}
// Single zero at second last position
for (int one_count = len - zero_count - 2; one_count <= len - zero_count; one_count++)
{
string temp = "";
for (int j = 0; j < one_count - 1; j++)
temp += '1';
temp += '0';
temp += '1';
possible_outputs.push_back(temp);
}
// Two zeros at last position
for (int one_count = len - zero_count - 2; one_count <= len - zero_count; one_count++)
{
string temp = "";
for (int j = 0; j < one_count; j++)
temp += '1';
temp += '0';
temp += '0';
possible_outputs.push_back(temp);
}
// Two zeros at second last position
for (int one_count = len - zero_count - 2; one_count <= len - zero_count; one_count++)
{
string temp = "";
for (int j = 0; j < one_count - 1; j++)
temp += '1';
temp += '0';
temp += '0';
temp += '1';
possible_outputs.push_back(temp);
}
// Zeros of suffix pending
int zeros_in_suffix = 0;
for (int i = len - 1; i >= 0; i--)
{
if (s[i] != '0')
break;
zeros_in_suffix++;
}
for (int one_count = len - zero_count - 2; one_count <= len - zero_count; one_count++)
{
for (int zero_count = zeros_in_suffix - 2; zero_count <= zeros_in_suffix; zero_count++)
{
string temp = "";
for (int j = 0; j < one_count; j++)
temp += '1';
for (int j = 0; j < zero_count; j++)
temp += '0';
possible_outputs.push_back(temp);
}
}
string res = "";
for (auto x : possible_outputs)
{
if (possible_to_remove(s, x))
{
res = max(res, x);
}
}
return res;
}
signed main()
{
int t;
cin >> t;
while (t--)
{
string s;
cin >> s;
cout << solve(s) << '\n';
}
}
Editorialist's Code (C++)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
string solve(string s)
{
int n = s.size();
int z = count(begin(s), end(s), '0');
auto evenblock = [] (int pref, int suf) {
string ans = "";
if (suf >= 3) ans = string(pref+suf-2, '1');
else if (suf == 2) ans = string(pref, '1') + "01";
else ans = string(pref, '1') + "00" + string(suf, '1');
return ans;
};
auto oneodd = [] (int pref, int suf) {
string ans = "";
if (suf >= 2) ans = string(pref+suf-1, '1');
else ans = string(pref, '1') + "0" + string(suf, '1');
return ans;
};
string ans = "";
if (z%2 == 0) {
int first = -1, last = -1, suf = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '1') ++suf;
else {
last = i;
if (first < 0) first = i;
suf = 0;
}
}
if (z == last-first+1) {
if (last == n-1) ans = s;
else {
int pref = n-z-suf;
ans = evenblock(pref, suf);
}
}
else {
if (s.back() == '1') ans = string(n-z, '1');
else {
int blocks = 0, cur = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '1') {
cur = 0;
continue;
}
if (i == 0 or s[i-1] == '1') ++blocks;
++cur;
}
if (cur%2 == 1) ans = string(n-z, '1') + string(cur-1, '0');
else {
if (blocks == 2) ans = string(n-z, '1') + string(cur-2, '0');
else ans = string(n-z, '1') + string(cur, '0');
}
}
}
}
else {
if (s.back() == '0') {
int blocks = 0, cur = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '1') {
cur = 0;
continue;
}
if (i == 0 or s[i-1] == '1') ++blocks;
++cur;
}
if (blocks == 1) ans = s;
else if (blocks == 2) {
if (cur%2 == 0) ans = string(n-z, '1') + string(cur-1, '0');
else {
if (cur > 1) ans = string(n-z, '1') + string(cur-2, '0');
else {
int pref = 0, suf = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '0') break;
++pref;
}
while (s.back() == '0') s.pop_back();
while (s.back() == '1') ++suf, s.pop_back();
if (suf >= 2) ans = string(pref+suf-1, '1');
else ans = string(pref, '1') + "0" + string(suf, '1');
}
}
}
else {
if (cur%2 == 1) ans = string(n-z, '1') + string(cur, '0');
else ans = string(n-z, '1') + string(cur-1, '0');
}
}
else {
vector<int> v;
int cur = 1;
for (int i = 1; i < n; ++i) {
if (s[i] != s[i-1]) {
v.push_back(cur);
cur = 1;
}
else ++cur;
}
v.push_back(cur);
reverse(begin(v), end(v));
if (v.size()%2 == 0) v.push_back(0);
if (v.size() == 3) ans = oneodd(v[2], v[0]);
else if (v.size() == 5) {
if (v[1] > 1) ans = oneodd(v[2]+v[4], v[0]);
else ans = oneodd(v[4], v[0] + v[2]);
}
else {
int suf = v[0], pref = 0;
for (int i = 2; i < v.size(); i += 2) pref += v[i];
ans = oneodd(pref, suf);
}
}
}
return ans;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
string s; cin >> s;
int n = s.size();
int z = count(begin(s), end(s), '0');
if (z == n or z == 0) {
cout << s << '\n';
continue;
}
cout << solve(s) << '\n';
}
}
