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
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