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.
thanks for sharing
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?
can you explain what is dp[i][j] for i from 0 to 5 in your code?
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
what is j representing here?
(In specific what is meant by dp[some number ][5],let length of string >5)?
j is the number of runs(blocks of either 0 or 1) at the current point