PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: hellolad
Tester: watoac2001
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
A binary string is called good if it can be partitioned into several substrings, each of even length, and each containing the same character.
You’re given a binary string S of even length.
Exactly once, you can choose an alternating subsequence of S, and flip it.
Find a way to make S good using such a move, or claim it’s impossible.
EXPLANATION:
First, let’s analyze what exactly it means for a string to be good.
Suppose S can be partitioned into even-length substrings, each containing the same character within themselves.
Notice that we can go even finer: each even-length substring can be broken up into a bunch of substrings of length 2, and we’ll still have a valid partition.
So, if S is good, it can be broken up into length 2 substrings, each consisting of the same character twice.
Notice that this is only possible when S_{2i} = S_{2i-1} for each 1 \leq i \leq \frac{N}{2}, i.e, the first character should equal the second, the third should equal the fourth, and so on.
Clearly, a string that’s in such a form is also good, since it can be broken up into the corresponding length 2 substrings to form a valid partition.
So, S is good if and only if S_{2i} = S_{2i-1} for each possible i.
Now, let’s see how we can get S into this form.
If S_{2i} = S_{2i-1} for some i, to maintain this we should either flip both of them, or neither of them.
Flipping both isn’t possible since the chosen subsequence wouldn’t be alternating; so our only choice is to flip neither.
If S_{2i} \neq S_{2i-1}, we need to flip either index 2i or index 2i-1, but not both.
Suppose there are K pairs of such indices (2i-1, 2i), such that one of them needs to be flipped.
These pairs are disjoint, so we’ll need to choose a subsequence of length exactly K; one index from each pair.
Now, it’s always possible to choose an alternating subsequence - since each pair contains one 0 and one 1, choose the position of the 0 from the first pair, the 1 from the second pair, the 0 from the third pair, and so on.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
int main(){
IOS
int t;
cin>>t;
while(t--){
int n;
string s;
cin>>n>>s;
int cnt=0;
for(int i=0;i<n;++i){
cnt+=s[i]=='1';
}
vector<int> subs={n};
cnt=1;
s.push_back('#');
for(int i=1;i<=n;++i){
if(s[i]==s[i-1]){
cnt++;
}else{
if(cnt&1){
if(s[i-1]==s[subs.back()]){
subs.push_back(i);
cnt=1;
i++;
}else{
subs.push_back(i-1);
cnt=2;
}
}else{
cnt=1;
}
}
}
cout<<subs.size()-1<<'\n';
for(int i=1;i<subs.size();++i){
cout<<subs[i]+1<<' ';
}
cout<<'\n';
}
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
s = input().strip()
ind = []
for i in range(0, n, 2):
if s[i] != s[i+1]: ind.append(i)
print(len(ind))
ans = []
for i in range(len(ind)):
if i%2 == 0:
if s[ind[i]] == '0': ans.append(ind[i]+1)
else: ans.append(ind[i]+2)
else:
if s[ind[i]] == '1': ans.append(ind[i]+1)
else: ans.append(ind[i]+2)
print(*ans)
(Simply amazing:astonished:).