# MAKELENGTH1 - Editorial

Author: Satyam
Testers: Takuki Kurokawa, Utkarsh Gupta
Editorialist: Nishank Suresh

1530

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>
{
while (first != last)
{
cin >> (*first);
++first;
}
}

template<class T>
{
}
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

Thanks sir

#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