PRFYIT (COOK OFF)

22

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

23

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.

24

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.

25

Output should be 1 removing the middle 1

26

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.

27

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

28

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

29

thanks for sharing

30

I am using this approach.
ans = min(no of one’s - maximum consecutive no of one’s , no of zero’s - maximum consecutive no of zero’s)
# cook your dish here
t= int(input())

for i in range (0,t):
string = input()
dict ={‘0’ : 0 , ‘1’:0}
n= len(string)
for j in string :
if j in dict :
dict [j] = dict[j]+1
else:
dict[j] = 1

max0 =0 
temp0=0 
for j in range(0,n):
    if string[j]=='0':
        temp0=temp0+1
    else:
        if max0<temp0:
            max0 = temp0
        temp0 = 0

if max0<temp0:
    max0 = temp0
    temp0 = 0
if (max0==1 and string[0]=='0' and string[-1]=='0'):
    max0=2
max1 =0 
temp1=0 
for j in range(0,n):
    if string[j]=='1':
        
        temp1=temp1+1
    else:
        if max1<temp1:
            max1 = temp1
        temp1 = 0
if max1<temp1:
    max1 = temp1
    temp1 = 0
if (max1==1 and string[0]=='1' and string[-1]=='1'):
    max1=2
print (min(dict['0']-max0 , dict['1']-max1))

can someone tell me what is wrong with this?

31

can you explain what is dp[i][j] for i from 0 to 5 in your code?

32

Yes sure, so here dp[i][j] represents the min characters to be deleted for forming a sequence of type i, where i denotes ->
For i = 0 -> the sequence of only 0s
For i = 1-> the sequence of only 1s
For i = 2-> the sequence of the form 0…01…1
For i = 3-> the reverse of above seq(ie 1…10…0)
For i = 4 -> the seq of the form 0…01…10…0
For i = 5 -> the seq of the form 1…10…01…1

The last two sequences are what we essentially need, and the rest are states in between which are needed for dp

33

what is j representing here?
(In specific what is meant by dp[some number ][5],let length of string >5)?

34

j is the number of runs(blocks of either 0 or 1) at the current point