PRFYIT (COOK OFF)

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

could anyone please tell me what is wrong if we count occurrence of 101 and check occurrence of 0 ??
while(t–)
{
string s;
cin>>s;
int n=s.length();
int i=0,c=0;
int flag=0;
while(i<n)
{
if((s[i]==‘1’)&&(s[i+1]==‘0’)&&(s[i+2]==‘1’)&&i<n-2)
{
c++;
i+=3;
}
else
{if(s[i]==‘0’)
flag=1;
i++;
}
}
if(flag==0)
{
if(c==1)
c=0;
else if(c>1)
c-=1;
}
cout<<c<<endl;
}

Can someone help me understand editorial solution?

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

The approach I used is-
I tried to find longest strings of type 0…0 , 1…1 , 0…01…1 ,1…10…0 , 1…10…01…1 ,0…01…10…0 because the are the only strings where no subsequence of type 0101 && 1010 are possible
Now the answer would be max length of these strings. To find those strings I maintained 4 arrays. Two to count no. of ones at a position from start & end and other two for count of zeros.

Output should be 1 removing the middle 1

My approach to this was to find the blocks of same string characters(0’s and 1’s) and according to their index values, remove the minimum block of strings until there are 3 blocks remaining.

Can someone share their approach to solve PRFYIT (COOK OF) problem…?

Yeah, exact same approach but couldn’t optimise it and got TLE.