I don’t to how to solve this question can anyone tell me the logic behind this problem
Link is above…
1 Like
Observe that the non decreasing subsequence is of the form 000…111… .So, we have to remove possibly some zeros and some ones such that the resulting string is of the above form. My approach is for every character in the string, calculate what is the longest non decreasing string if we include that character. Irrespective of the character at an index i, say x denotes zeros for indices <= i and say y denotes ones from indices >= i, then our longest string for i would be x + y. If we take max value for each index, we get the longest increasing subsequence. Subtracting it from the initial string length, is the minimum deletions required to obtain this. Hope this helps 
Code(python): https://www.codechef.com/viewsolution/42115234
8 Likes
Find the longest increasing sub sequence (NlogN) By using DP, and subtract it with the length of string, you will get your answer.
1 Like
you are given a string S like “10101” and you have to make it sorted by removing minimum length subsequence.
s="10101"
sorted ="00111"
we can directly calculate Longest Common subsequence between “S” and Sorted string .
minimum deletion = length_of_string - LCS(s,s1).
Time complexity to find LCS is N^2.
we can further improve the complexity using the concept of Longest increasing subsequnce.
like for any particular index, if it is “0” then we can only take “0” before that to make sorted.
and if it is “1” we can choose all zero before that or all one before that or (combination of one and zero that is in sorted order).
Link: CodeChef: Practical coding for everyone
Video Link: Binary Subsequence | Codechef January Lunch Time 2021 | Hindi | C++ - YouTube
6 Likes
what i did is to just observe how things going with 3-4 testcases ,
its so easy after you find out whats going ,
basically i solved backwards , what YOU BASICALLY need is as many as zeros at the front then all one ,
lets suppose 10101110001
how will u find it answer ? lets forget about this
think about 111110000001 , the shortest way make it valid bstring to remove the ones , but why ? becuase number of zeros are more ,
now think about 111111000101 , to make it valid you have to erase the zeros only and this time you know why ,
so basically if you observe closely if a zero after one , we are just doing (no of zeros) - (no of ones)
for small section but you can compare it with greedy thats why its satisfy with rest of optimal solution too , if the problem can be modified a bit more may be we had to go for DP ,
heres my solution CodeChef: Practical coding for everyone
even though many have solved using DP too , i checked in youtube , you can also understand that if you find my words hard to understand , or theres alot more experienced people to guide you ,
have a great day !
6 Likes
pretty amazing brother ,
1 Like
I solved using Prefix and suffix , make prefix array of count of ‘0’ , and suffix array of count of ‘1’ , now we know that the resulting sequence may of three types only -
type1 : all ‘0’ s → 000000000…
so just count all ‘0’ and store value n - count (we have to print the deletions so if we take count ‘0’ than how many characters we want to delete ? obviously n - count )
type2 : all ‘1’ s → 111111111…
so just count all ‘1’ and store value n - count (we have to print the deletions so if we take count '1’s than how many characters we want to delete ? obviously n - count )
type3 : some’0’s + some '1’s → 01111… or 00111111… or 000111111… and so on
so just make prefix array of count of ‘0’ , and suffix array of count of ‘1’ and while iterating take prefix_count_zero[i] + suffix_count_ones[i+1] (this is the resultant string we want so how many characters we want to delete ? obviously n - (prefix_count_zero[i] + suffix_count_ones[i+1] ) and take minimum from all of that )
prefix_count_zero[i] denotes the total ‘0’ till i’th index (including i too)
suffix_count_ones[i] denotes how many ‘1’ are there after i’th index (including i too)
My solution : “https://www.codechef.com/viewplaintext/42033593”
6 Likes
Let’s think about how we can find the length of the longest increasing subsequence(LIS). Then, the answer will be the total length - the length of the LIS.
I initially solved it using dynamic programming O(N²) . but I got TLE.
Then I solved it in O(N). Notice, we have only two different numbers 0 and 1.
The increasing subsequence will be in one of the three forms
-
- All 0’s (0000)
-
- All 1’s(11111)
-
- Some 0’s followed by 1’s (000111)
So, the subsequence will either end at 0 or 1.
We maintain two variables say A and B,
- A - Length of LIS that ends with 0
- B - Length of LIS that ends with 1
Initially, both A and B are 0.
Iterate over the string and at each iteration find out whether it is optimal to add the current char to 0 ending subsequence or 1 ending subsequence.
If the current value is 0, obviously you can add it to only 0 ending sequence. Because 0 followed by 0 will still be an increasing subsequence. So we increment A by 1.
If the current value is 1 there could be two cases,
- we can make LIS like(11111) All 1’s.
- we can make LIS like(0011) some 0’s followed by some 1’s.
So, we have to determine whether it is optimal to make a LIS like in case 1 or a LIS like in case 2.
if A >= B , then it is optimal to add the current value to LIS ending with 0 making it like a LIS in case 2 . so we make B = A+1( A contains the length of LIS that ends with 0).
else, we can add the current value to LIS ending with 1 to make it like LIS in case 1. So we make B=B+1.
At the end of the last iteration,
- A - contains the length of LIS ending with 0 of the whole string.
- A - contains the length of LIS ending with 1 of the whole string.
we return n- max(A, B), where n is the length of the string.
My solution in Python : CodeChef: Practical coding for everyone
3 Likes
I did the same but got TLE for the last test case.
Great work!
1 Like
I was thinking in this way, nice one
1 Like
This is my solution
#include<bits/stdc++.h>
#include
using namespace std;
#define ll long long int
int main()
{
ll t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
string s;
cin>>s;
stack<char> st;
st.push(s[0]);
for(ll i=1;i<n;i++)
{
if(!st.empty() && st.top()=='1' && s[i]=='0')
{
counti++;
st.pop();
}
else
{
st.push(s[i]);
}
}
cout<<counti<<endl;
}
}
3 Likes
I did the same thing.
1 Like
I almost had the same thing on my mind but was not able to do it, thank you for posting your solution!
1 Like
hi, i did something similar, can u provide some edge test cases for this problem. Thanks!
1 Like
edge test cases are not a big deal here , you can take it by yourself ,
in the edge cases don’t have to bother about decrements specially ,
i had the solution in my mind by observing , me myself not pretty sure why the solution is pretty promising every time , i just does , i checked many test cases in rough work , you can call it a greedy approach or something like that .
my approach - 1 k baad zero aaye (“10” pair) to use hta kr count bda do kyu ki yhi string hamari resultent string ko increasing order m nhi rhne degi.
main string 1101000010110111010 - remove first 10 and increase the value of count so count=1
now string - 11000010110111010 - now again remove 10 now count=2
now string - 100010110111010 - remove 10 now count=3
now string - 0010110111010 - remove 10 now count=4
now string - 00110111010 - remove 10 now count=5
now string- 001111010 - remove 10 now count=6
now string- 0011110 - remove last 10 now count=7
now your final string 00111
print the value of count jo ki 7 hai is test case me.
I also solved this problem using the algorithm you described. A fast O(N) solution.
1 Like
nice observation
Good one!