PRFYIT (COOK OFF)

How to solve?

Need Help! For which test case this will fail?
import java.util.*;

public 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));



    }

  }

}
1 Like

111100010001111 ??
What output?

1
String–>111100000111

11011000
and
011011000

What output?

Is there DP solution? Can we memoize the recursive solution somehow?

i calculated number of 0 and 1
then i calculated length of longest continuous sequence of 1 and 0 respectively
and answer = min(no. of 0 - maximum continuous length of 0s , no. of 1 - maximum continuous length of 1s)
e.g suppose string is 1011100001011101
no. of 0=7
no. of 1=9
max. no. of continuous 0 =4
max. no. of continuous 1=3
so answer=min(7-4,9,3)=3
which is given in test case also
but my code is giving WA any improvement/changes ?

1 for both
String1 (11011000)->1111000
String2 (011011000)–> 01111000

I also did the same and its the wrong approach I think!
It wail fail for the test cases i mentioned above!

i have done the same thing but WA

Here is my code. Did the same thing but got WA.

int main() {
     int t;
     cin >> t;
     while (t--) {
         string s;
         cin >> s;

        int count0 = 0;
        int count1 = 0;
        vector<char>p;
        int k=0;
        for(int i=0 ; i<s.length();i++){
            p.push_back(s[i]);
                while(s[i]==s[i+1]) {
                    i++;
                }
          }

        for (int j = 0; j < p.size(); ++j) {
            if(p[j]=='0') {
                count0++;
            }
            else
            count1++;
        }
        if(min(count1,count0)-1 == -1){
            cout<<"0"<<endl;
        }
        else
        cout<<min(count1,count0)-1<<endl;
    }
    return 0;
}

11011000 - output: 1 i.e removing index 2 (starting from 0)
011011000- output: 1 i.e removing index 3
in both cases 1 is the minimum no of character to delete so that both 1010 & 0101 subsequences are avoided.

Well I used DP to calculate 6 counts for every run of either 0 or 1, the counts respectively represented the min deletion for a sequence of 0s, 1s, 0s and then 1s, 1s and then 0s, 0s then 1s then 0s and 1s then 0s then 1s; the updations are easy.
My Submission

The final string can either be solely of 0s, solely of 1s, of 0s and then 1s and so on; those are the 6 possibilities

1 Like

Your approach fails for case 1001001111.

Could anyone please point out the test case for which this will fail-
`#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;

while (t--) {
    string s;
    cin >> s;
    int count = 0;
    int n = s.length();
    int f = 0, j = 0, aa[10000] = { 0 }, bb[10000] = { 0 };

    for (int i = 0; i < n; i++) {
        if (s[i] == '0' && f == 0) {
            count++;
            f = 1;
            aa[j]++;
        }
        else if (s[i] == '1') {
            j++;
            f = 0;
        }
        else {
            aa[j]++;
            count++;
        }
    }

    if (count == 1 || count == 0 || j == 0) {
        count = 0;
    }
    else if (s[0] == '0' && s[n - 1] == '0') {
        sort(aa + 1, aa + j);
        count = min(count - aa[0] - aa[j], count - aa[j - 1]);
    }
    else {
        sort(aa, aa + 10000);
        count = count - aa[9999];
    }

    j = 0;
    int count1 = 0;
    f = 0;

    for (int i = 0; i < n; i++) {
        if (s[i] == '1' && f == 0) {
            count1++;
            f = 1;
            bb[j]++;
        }
        else if (s[i] == '0') {
            j++;
            f = 0;
        }
        else {
            count1++;
            bb[j]++;
        }
    }

    if (count1 == 1 || count1 == 0 || j == 0) {
        count1 = 0;
    }
    else if (s[0] == '1' && s[n - 1] == '1') {
        sort(bb + 1, bb + j);
        count1 = min(count1 - bb[0] - bb[j], count1 - bb[j - 1]);
    }
    else {
        sort(bb, bb + 10000);
        count1 = count1 - bb[9999];
    }

    if (count < count1) {
        cout << count << endl;
    }
    else {
        cout << count1 << endl;
    }
}

}`

Bro can you tell where you learned and practiced DP.

1 Like

Can’t understand that much from the code, really weak in CPP and DP. My approach was to keep a stack tracking the current state of elements taken, until that is invalid (1010 or 0101) in which case I return INT_MAX, if my state is 010 and a 0 comes, I keep it same as 010 and if it was 101 and a 1 comes I keep it same as 101.

Then I was recursively calling the function with res = MIN(select current element, not select current element) and I was incrementing a deletion variable keeping track of number of deletions. If I exceed the length of array, I return deletions.

Can you tell me if this approach is totally insane or maybe it can be used?

Actually I am still learning tbh, but there is this awesome book
CP 3

2 Likes

Can someone help me identify where I am going wrong?

Can’t it be solved using this approach?

I check if there is a lcs of given string with 0101 or 1010.
If length of lcs <=3, then no deletions in s are required else delete any character i (0<i<n) and recursively solve for it and take the minimum out of it like the loop inside recursive solution in rod-cutting problem;

int delete(string s, int i, int n){
if (lcs(s,“0101”)<=3 && lcs(s,“1010”) <=3)
return 0;
else
int i,mi=999999;
for(i=0;i<n;i++){
string p=s;
erase(i,1); // The string s is copied to p and ith character is erased.
mi=min(mi, 1+del( p, i, n-1 ));
}
}

I think it might work, but you would need to memoize, also you can directly work on runs(blocks of same character).

1 Like