MAKELENGTH1 - Editorial

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. :sweat:

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 :blush: . Hope you got point.

1 Like