PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Satyam
Testers: Takuki Kurokawa, Utkarsh Gupta
Editorialist: Nishank Suresh
DIFFICULTY:
1530
PREREQUISITES:
None
PROBLEM:
You have a string S. In one move, you can choose two adjacent equal characters, turn the first one into 0 and delete the second.
Is it possible to bring the string down to a single character?
EXPLANATION:
If N = 1, the string is already of length 1 so the answer is “Yes”.
Otherwise, let’s look at what the operation does:
- If there are two zeros in a row, it deletes one of them
- If there are two ones in a row, it essentially deletes both of them and inserts a zero there.
In particular, if we have a continuous block of 1's, then the operation can only reduce its length by 2. So, if this block has odd length, then there will always be a 1 left in the string.
However, note that when N\gt 1, the final character will definitely be a 0.
So, we need to delete every 1 from the string.
This gives us a solution:
- Find every (maximal) continuous block of ones in S.
- For example, if S = 011010111010110001, we find blocks of length (2, 1, 3, 1, 2, 1)
- If any of these blocks has odd length, it’s not possible to remove it completely and so the answer is “No”.
- If every block has even length, the answer is “Yes”.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
ones = 0
ans = 'YES'
for c in input():
if c == '1':
ones += 1
else:
if ones % 2 == 1:
ans = 'NO'
ones = 0
if ones % 2 == 1 and n > 1:
ans = 'NO'
print(ans)
1 Like
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fast ios_base::sync_with_stdio(0),cin.tie(0)
#define ll long long
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define sorta(vec) sort(vec.begin(),vec.end())
#define sortd(vec) sort(vec.begin(),vec.end(),greater<int>())
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>pbds; // find_by_order, order_of_key(0-indexed)
//less , less_equal , greater , greater_equal -> rule for insertion
void debug(int x)
{
cout<<"Value Debugged is "<<x<<endl;
}
void debug(vector<int>x)
{
cout<<"Value Debugged is "<<endl;
for(auto y:x)
{
cout<<y<<" ";
}
cout<<endl;
}
template<class ForwardIterator>
void read(ForwardIterator first,ForwardIterator last)
{
while (first != last)
{
cin >> (*first);
++first;
}
}
template<class T>
void read(vector<T> &v)
{
read(v.begin(), v.end());
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
//fast;
int t=1;
cin>>t;
while(t--)
{
ll int n;
cin>>n;
string vec;
cin>>vec;
if(n==1)
{
yes;
continue;
}
bool res=true;
for(ll int i=0;i<n-1;i++)
{
if(vec[i]=='1' && vec[i+1]=='1')
{
i++;
}
else if(vec[i]=='1' && vec[i+1]=='0')
{
res=false;
break;
}
}
if(res)
{
yes;
}
else
{
no;
}
}
return 0;
}
whats wrong in this
Consider the string 01.
More generally it fails on anything where the only odd block of ones is the suffix.
2 Likes
spent 10 mins to write a solution that worked partially. spent 1 more hour and couldn’t find what case it was failing on . Checks the article and finds that I missed the easiest test case of all, n=1. 
1 Like
#include "bits/stdc++.h"
using namespace std;
#define int long long int
void solve(){
int n;
string s;
cin>>n>>s;
for(int i=0;i<s.size()-1;i++){
if(s[i] == s[i+1]){
s[i] = '0';
s.erase(s.begin()+i+1);
i = 0;
}
}
if(s.size() == 1 or s == "0" or s == "1" or s == "00" or s == "11") cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
signed main(){
int t = 1;
cin>>t;
while(t--) solve();
return 0;
}
This is more simple one
Consider a test case 11001100 . after passing pair of one & zero, In next half your condition violates. 1100 
. Hope you got point.
1 Like