salt_n_ice's blog

1430D — String Deletion

By salt_n_ice, history, 4 years ago, In English

Problem Here is what I tried: 

#include<iostream>
#include<vector>
#include<string>
using namespace std;
using ll = long long;

int main()
{
    ll t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        string s;
        cin>>s;
        vector<ll> len, p;
        ll i=0, j=0;
        while(i<n && j<n)
        {
            while(j<n && s[i]==s[j])
                j++;
            p.push_back(j-i);
            i=j;
        }
        ll ans = 0;
        for(ll i=0; i<p.size(); ++i)
        {
            if(p[i]<2)
            {
                ans++;
                i++;
            }
            else
                ans++;
        }
        cout<<ans<<endl;
    }
}

Can someone briefly explain where am I going wrong?

  • Vote: I like it
  • -9
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

You idea behind the solution is incorrect. case:- 10101000

correct answer = 4

your answer = 3 (you are skipping the last block which could be used to maximize the operations on the prefixes)

refer to the editorial for an understanding.

→ Reply