#
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