PRFYIT - Editorial

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Kasra Mazaheri

Tester: Arshia Soltani

Editorialist: Kasra Mazaheri

DIFFICULTY:

Simple

PREREQUISITES:

Bruteforce, Dynamic Programming

PROBLEM:

Given a binary string S of length N, we want to delete minimum number of characters from it so that it wouldn’t contain subsequence 0101 or 1010 (so that it becomes pure). Find this minimum value.

QUICK EXPLANATION

  • A string is pure if and only if there are at most 3 maximal blocks of consecutive equal characters in the string.
  • We can calculate the number of 0's and 1's of an interval using partial sum (or dynamic programming).
  • We can fix the endpoints of the 3 maximal blocks along with their character (0 or 1) and calculate the minimum number of indices which should be deleted in this configuration of blocks using partial sums.

EXPLANATION

We define a block to be a maximal consecutive block of equal characters in a string. For example, the string 000110100111 consists of 6 blocks : 000, 11, 0, 1, 00 and 111.

It’s clear that two consecutive blocks have different characters, or else they wouldn’t have been maximal. As a result, any string with more than 3 blocks will not be pure, since we can pick the first character of each of the first 4 blocks and it would either be 0101 or 1010. So the resulting string should consist of at most 3 blocks.

We can fix the interval of the middle block (say [L, R]) and it’s character (say 0, the case of 1 is exactly the same). Now all we have to do is to count the number of indices i such that S_i is different than the character of it’s corresponding block. So we should count the number of 0's in the intervals [1, L-1] and [R + 1, N] and the number of 1's in the interval [L, R]. We can calculate this value with partial sums. Namely, define P_i to be the number of 0's in the interval [1, i]. Then the number of 0's in an interval [A, B] will be P_B - P_{A - 1}. The number of 1's can also be calculated as (B - A + 1) - (P_B - P_{A - 1}). Thus we can calculate the number of indices that have to be deleted in O(1). Fixing the interval is O(N ^ 2) so we arrive at a final O(N ^ 2) solution.

TIME COMPLEXITY

The time complexity is O(N ^ 2) per test case.

SOLUTIONS:

Setter's Solution
// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int q, n, P[2][N];
char S[N];
int main()
{
	scanf("%d", &q);
	for (; q; q --)
	{
		scanf("%s", &S[1]);
		n = strlen(S + 1);
		for (int i = 1; i <= n; i ++)
			for (int w = 0; w <= 1; w ++)
				P[w][i] = P[w][i - 1] + (S[i] == w + '0');
		int Mn = n;
		for (int w = 0; w <= 1; w ++)
			for (int i = 1; i <= n; i ++)
				for (int j = i; j <= n; j ++)
					Mn = min(Mn, P[w][i - 1] + (j - i + 1) - (P[w][j] - P[w][i - 1]) + (P[w][n] - P[w][j]));
		printf("%d\n", Mn);
		memset(S, 0, sizeof(S));
		memset(P, 0, sizeof(P));
	}
	return 0;
}
Tester's Solution
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
 
long long gcd(long long a, long long b) {return b == 0 ? a : gcd(b, a % b);}
 
#define ll int
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll>
 
using namespace :: std;
 
const ll maxn=1e4+500;
 
ll p[maxn];
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll q;
	cin>>q;
	while(q--){
		string s;
		cin>>s;
		ll n=(ll)s.size();
		for(ll i=0;i<n;i++){
			p[i+1]=p[i];
			if(s[i]=='1'){
				p[i+1]++;
			}
		}
		ll mx=0;
		for(ll i=0;i<n;i++){
			for(ll j=i+1;j<=n;j++){
				mx=max(mx,p[j]-p[i]+i-p[i]+n-j-p[n]+p[j]);
				mx=max(mx,j-i-p[j]+p[i]+p[i]+p[n]-p[j]);
			}
		}
		cout<<n-mx<<endl;
		for(ll i=0;i<=n;i++)
			p[i]=0;
	}
}

Feel free to share your approach. As usual, suggestions are warmly welcomed. :slight_smile:

16 Likes

for which test case this will fail?
import java.util.* ;
class Test{

public static void main (String args[])  {

Scanner in = new Scanner(System.in);
int t = in.nextInt();
in.nextLine();
for(int tc =0 ;tc<t;tc++){

int ans =0 ;
String s = in.nextLine();
int nn= s.length();
int one=0;
int zero =0 ;

//creating new string by squeezing original string, if s = 100010011110 the solo = 101010
    String solo = "";
    for(int i=1 ;i<nn;i++){
        if(s.charAt(i)=='1' && s.charAt(i-1)=='0')
            solo+=1 ;
        if(s.charAt(i)=='0' && s.charAt(i-1)=='1') solo+=0 ;
            }
solo = s.charAt(0)+solo ;

//counting number of zeros and ones
    int n = solo.length();
    for(int i=0 ;i<n;i++)
        if(solo.charAt(i)=='1')
            one++;

    zero = n - one ;


    ans = Math.min(one - 1 ,zero -1);


System.out.println(Math.max(0,ans));

    }
}
}

I did it using DP by maintaining the minimum deletions needed to convert the given string to strings of type 0, type 1, type 01, type 10, type 010 and type 101.
My Solution

5 Likes

Can someone help me understand this solution?

Third paragraph of explanation is unclear to me. Please elaborate along with how is it achieved using c++ code of setter’s solution.

5 Likes

cook your dish here

for _ in range(int(input())):
bi = input().strip()
dp = [0 if i < 2 else len(bi) for i in range(6)]
for c in bi:
if c == ‘1’:
dp[3] = min(dp[3], dp[0])
dp[0] += 1
dp[5] = min(dp[5], dp[2])
dp[2] += 1
dp[4] += 1
else:
dp[2] = min(dp[2], dp[1])
dp[1] += 1
dp[4] = min(dp[4], dp[3])
dp[3] += 1
dp[5] += 1
print(min(dp))

how this code is working i think its really efficient??reply asap

2 Likes

I was also wondering how this worked. It might calculate the length of all the indices but that doesn’t make much sense either because it only has 6 elements.

iam getting it slowly…its the verygood implementation of the above explanation…one bit for counting number of ones …one bit for number of 0 and so on… its my interpretation of code please correct me if am going wrong…

111000111000
For this case,answer will be 3.
Your output is 1.

3 Likes

Is my Logic correct?

What I’m doing is calculating total no. of blocks as specified in explanation and if they are greater than 3 I’m removing all the blocks of 0 except for the longest one.
Also if it both start and end with 0 then Im checking if len of max block > sum of first and last block.

In 001110011 there is no 101 so your code might print 0 but ans is 2

1 Like

In the question they have given subsequence and not substring and hence the string you have generated i.e 01111101 has 0101 as it’s subsequence if we take the elements at indices 0,1,6,7.

Can someone tell me what’s wrong with my approach.
firstly i got all the blocks converted to single digit, example- 1110001111000 to 1010
then if this pattern is <=3 , there is no need to delete.
Else , in real pattern, i counted each block of 0 and 1 and stored in individual lists named zero and one
in above example- zero has = [3,3] and one has [3,4] inside it.
now i sorted these and found min(( deleting all zeros except biggest block of zeros) , (deleting all ones except biggest block of ones) )
then printed that value.

def testcase():
string=input()
string2=string[0]
for i in string:
if string2[-1]!=i:
string2+=i

if len(string2)<=3:
print(0)
else:
first=string2[0]
second=string2[1]
block={‘1’:[],‘0’:[]}
i=1
previous=string[0]
count=1
while i<len(string):
if string[i]==previous:
count+=1
else:
block[previous].append(count)
count=1
previous=string[i]
i+=1
block[previous].append(count)
one=block[‘1’]
zero=block[‘0’]
one.sort()
zero.sort()
#print(one[:-1])
#print(zero[:-1])
one=one[:-1]
zero=zero[:-1]
#print(one)
answer=min(sum(one),sum(zero))
print(answer)

t=int(input())
for i in range(t):
testcase()

2 Likes

Please someone check my code and tell in which test case my code will fail?

if we can convert to type 101 or 010 …it should be enough

can you please explain these two lines !! how it is working and it is calculating what?

To which TestCase will this fail?

#include<bits/stdc++.h>
using namespace std;
int main()
{ int t,i;
cin>>t;
while(t–)
{ string s;
cin>>s;
int n = s.length();
int count =0;
for(i=0; i<n; i++)
{ if(s[i]==‘0’)
count++;

     }
     if(count==0 || count ==n)
      {
          cout<<"0\n";
      }
      else
      {


        count =0;
       vector<int> v1, v2;
       for(i=0; i<n; i++)
        {  if(s[i] == '1' )
              {  while(s[i] == '1' && i<n)
                 {  i++;
                    count++;
                    //cout<<"Overr Here";
                 }
                 v1.push_back(count);
                 count=0;
               }

              if(s[i] == '0')
               { while(s[i] =='0' && i<n)
                 {
                   i++;
                   count++;
                 }
                 v2.push_back(count);
                 count=0;
               }
               i--;

        }
        if(v1.size()>0)
        sort(v1.begin(), v1.end());
        if(v2.size()>0)
        sort(v2.begin(), v2.end());
        int sum1 =0, sum2 =0;
        //cout<<" v1 is ";
        for(i=0; i<v1.size()-1; i++)
         {  //cout<<v1[i]<<" ";
           sum1 = sum1 + v1[i];

         }
         //out<<"\n";
         //cout<<"v2 is ";
         for(i=0; i<v2.size()-1; i++)
        {  //cout<<v2[i]<<" ";
           sum2 = sum2 + v2[i];
          }
          //cout<<"\n";
         cout<<min(sum1,sum2)<<"\n";





      }



}

return(0);
}

https://www.codechef.com/viewsolution/28447929
Can anyone please tell me for which testcase my solution is failing.

Yes, but for dp we need other states too…

2 Likes

I also used the same idea, but am getting WA

Test Case:
1
001111101111000

Your Ans: 3

Correct Ans: 1

1 Like