https://www.codechef.com/viewsolution/28454735
How is this wrong? I cannot find a testcase where it fails.
hey for which test case my code went wrong?
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
for(int k=0;k<t;k++)
{
int n;
string s;
cin>>s;
n=s.size();
int c0=0,c1=0;
vector v0,v1;
for(int i=0;i<n;i++)
{
if(s[i]==‘0’)
{
c0++;
if(s[i+1]!=‘0’)
{
v0.push_back(c0);
c0=0;
}
}
if(s[i]==‘1’)
{
c1++;
if(s[i+1]!=‘1’)
{
v1.push_back(c1);
c1=0;
}
}
}
sort(v0.begin(),v0.end());
sort(v1.begin(),v1.end());
int sum1=0,sum0=0;
if(v0.size()==0||v1.size()==0)
{
cout<<0<<endl;
return 0;
}
for(int i=0;i<v0.size()-1;i++)
{
sum0=sum0+v0[i];
}
for(int i=0;i<v1.size()-1;i++)
{
sum1=sum1+v1[i];
}
cout<<min(sum0,sum1)<<endl;
}
}
According to the editorial, P[w][n]-P[w][j] is the number of w in (j,n] interval, P[w][i-1] is the number of w in [1,i) and (j-i+1) - (P[w][j]-P[w][i-1]) is the number of 1-w in the interval [i,j]. Let’s consider an example,
00011100111000,
the best case possible is when w = 1, i = 3, j = 10, i.e
P[w][n]-P[w][j] = 0
P[w][i-1] = 0
(j-i+1) - (P[w][j]-P[w][i-1]) = 2
This is how the above equation works, in short,
if you choose a particular (i,j) and when w = 0. delete all the 0’s before i and all the 0’s after j, you will be left with only 1’s before i (if there are any 1’s) and only 1’s after j (if there are any 1’s). When you finally delete all the 1’s in [i,j] you will be only left with 0’s (if there are any). In the end you will be left with a sequence like 11111000011111 with only 3 blocks (considering the 0’s and 1’s exist as explained above) or 2 blocks or 1 block or 0, which can never have that pattern.
here, this testcase would fail
11110110000100 - the answer is 2(remove first 0 and last 1)
#include <iostream>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
char pat1[4] = { '0', '1', '0', '1' };
char pat2[4] = { '1', '0', '1', '0' };
bool p1[4] = { false, false, false, false };
bool p2[4] = { false, false, false, false };
int ip1 = -1;
int ip2 = -1;
int count = 0;
string s;
// 010111101
// 1011100001011101
cin>>s;
for(int i=0;i<s.length(); i++) {
if(pat1[ip1+1] == s[i]) {
p1[ip1+1] = true;
ip1++;
}
if(pat2[ip2+1] == s[i]) {
p2[ip2+1] = true;
ip2++;
}
if(ip1 == 3 || ip2 == 3) {
count++;
p1[ip1--] = false;
p1[ip1--] = false;
p2[ip2--] = false;
p2[ip2--] = false;
}
}
cout<<count<<endl;
}
return 0;
}
Tried to solve it in O(n). Don’t know the failing test cases. Can you please help in checking failing test cases @kmaaszraa ?
Logic with which I implemented -
I kept track of both the patterns and if any of these is formed, just remove the second last char.
Example -
Test case - 1011100001011101
Intially
1010
f f f f
0101
f f f f
Iterating over the test case - at pos 6 1010 pattern is formed and at this scenario over state would be
1010
t t t t
0101
t t t f
So just remove the last 1 and set the state to
1010
t t f f
0101
t f f f
and counter is maintained for every removal.
I can’t find the error of failing case with this approach. Any help appreciated.
Can any one help me to find on which test-case it is showing Wrong-Answer?
my Approach::>
i am splitting string by 0 and 1:
input: 1101000011
one[]= { **11,1**,11} if i am deleting all string excluding max-size string
**deleted_digit= 2+1=3**
zero[]={ **0**,0000} if i am deleting all string excluding max-size string
**deleted_digit= 1**
answer will be min(1,3)=1
import java.util.*;
public class solve{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++){
String que=sc.next();
String[] zero=que.split("1");
String[] one=que.split("0");
int zeroSum=0,oneSum=0;
int zeroMax=0,oneMax=0;
for(int j=0;j<zero.length;j++){
zeroSum+=zero[j].length();
if(zeroMax<zero[j].length())
zeroMax=zero[j].length();
}
for(int j=0;j<one.length;j++){
oneSum+=one[j].length();
if(oneMax<one[j].length())
oneMax=one[j].length();
}
int val1=zeroSum-zeroMax;
int val2=oneSum-oneMax;
System.out.println(Math.min(val1,val2));
}
}
}For what test case my code is failing,can anyone check please…
I can’t find any error in logic and I did it in O(n) complexity.
#include <stdlib.h>
#include <bits/stdc++.h>
#include
#include
#define FOR(i, u, v) for (int i = u; i < v; i++)
#define FORD(i, v, u) for (int i = v; i > u; i–)
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define N 100005
#define maxc 1000000007
#define ll unsigned long long
using namespace std;
int siglength(string s)
{
int ans = 1;
int n = s.length();
for(int i=1;i<n;i++)
{
if(s[i]!=s[i-1])
ans++;
}
return ans;
}
int maxl(string s,char c)
{
int ans =0, l=0;
for(int i=0;i<s.length();i++)
{
if(s[i]==c)
l++;
if(s[i]!=c)
{
if(l>ans)
ans=l;
l=0;
}
}
if(l>ans)ans=l;
return ans;
}
int main()
{
cin.tie(NULL);cout.tie(NULL);
ios_base::sync_with_stdio(false);
int t;
cin>>t;
while(t–)
{
string s;
cin>>s;
int ans=0;
int n1=0,n0=0,ml1=0,ml0=0;
for(int i=0;i<s.length();i++)
{
if(s[i]==‘0’)n0++;
}
n1 = s.length()-n0;
ml1 = maxl(s,‘1’);
ml0 = maxl(s,‘0’);
int sl = siglength(s);
if(sl>3)
{
ans = min(n1-ml1,n0-ml0);
}
//ans = sl/2 -1;
cout<<ans<<endl;
}
return 0;
}
Can anyone help me understand meaning of Pure?
In the first sample test case, 010111101, if we just remove the 3rd char, the sequence becomes 01111101, which is pure. So the answer should be 1, instead of 2.
Most frustrating part about this question is “DIFFICULTY : Simple”. I am unable to get my head around this question using dp. I solved using brute force but that gives tle. I am having difficulty understanding dp solution and when i saw “DIFFICULTY:Simple” it makes me feel stupid 
Clean implementation with explanatory comments for understanding easily.
private static int getFromDp(String s) {
int n = s.length();
int zero[] = new int[n+1];
int one[] = new int[n+1];
Arrays.fill(zero, 0);
Arrays.fill(one, 0);
for (int i=1;i<=n;i++) {
int d = s.charAt(i-1) - '0';
if (d == 0) zero[i] = zero[i-1] + 1;
else zero[i] = zero[i-1];
}
for (int i=1;i<=n;i++) {
int d = s.charAt(i-1) - '0';
if (d == 1) one[i] = one[i-1] + 1;
else one[i] = one[i-1];
}
int min = n;
//for every i and j, we will form 3 blocks of form 010 or 101 and compute minimum deletion
//3 blocks will be 1,i-1 and i,j-1 and j,n
for (int i=1;i<=n;i++) {
for (int j=i;j<=n;j++) {
//form 3 blocks in the form 010
//number of ones in 1 to i-1 we need to remove it
int o1 = one[i-1];
//number of zeroes in i to j-1, remove it
int z1 = Math.abs(zero[j-1] - zero[i]);//using abs for handling case i == j
//number of ones in j to n, remove it
int o2 = one[n] - one[j];
int diff = o1 + z1 + o2;
min = Math.min(min, diff);
//form 3 blocks of form 101
z1 = zero[i-1];
o1 = Math.abs(one[j-1] - one[i]);
int z2 = zero[n] - zero[j];
diff = z1+o1+z2;
min = Math.min(min, diff);
}
}
return min;
}
Hope it helps
Pure means only 3 blocks(or less) in form of either 0s1s0s or 1s0s1s. (s denote any number of character s>=0).
In your sequence 01111101 it has four blocks 0 11111 0 1 so its not pure.
I requested someone to help me but since, no one replied to me after so long, I myself found an answer to this question which is more intuitive as well extremely fast i.e. O(n) solution. It has got AC on this platform and is easy to understand and not like the editorial solution which has a more mysterious explanation than the question itself.
You can find my code here.
If someone wants to understand my approach then he can read the post further as this is too looooong.
The solution is based on two well known problems of dynamic programming.
One is Longest Common Subsequence which is a must know for surviving in this competitive environment as well as this question. If someone still is unaware of it then he can go here or to youtube as several videos are available there.
Another problem namely regular expression matching is not mainly extremely required but using it actually makes it easier to think and then write a coded solution for it. You can watch it here.
Now, the solution works like this. What we want is to club the given string into blocks of similar type so that it is either of the form 010 or 101.
What I mean by type is that either all are 0s or all are 1s.
For example, s=“10001001110000111”
We can say its type to be 1010101 i.e. clubbing (grouping/merging together) all contiguous blocks having same characters as long as you don’t find a different character.
s=“0001” has type 01
s=“111” has type 1
s=“0101” has type 0101
and so on.
Let me repeat myself “What we want is to club the given string into blocks of similar type so that it is either of the form 010 or 101”
Now, we can as well have the string of type 0 or 1 or 10 or 01 perfectly suitable for the answer.
Now, there are only 6 cases which you need to check ( you : but you(the writer) didn’t even tell it once?. me: Have patience I will tell it further.) But let’s say you appear in some other contest and get an almost similar question like this with small change to convert it into let’s say type 010101 or 101010.
Now, there will be a whole lot of cases to check individually. But we can actually merge them into just two of them.
By using the technique of the regular expression match. 
You can define it as 1* 0* 1* 0* 1* 0* (let’s call it pattern) where * denotes 0 or more occurences of the character before.
From now on I will be talking only about the original question.
{
you: Why are talking so much? And over explaining and moreover trying to create a conversation out of nowhere?
me: 1. Quarantine side-effects 2. My style 
}
So, the case of type as “0” is just 1* 0* 1* with 0 (zero) occurrences of 1s at both the ends.
Similarly, you can see that all cases will be covered using this notation.
Now, the main logic.
We find the Longest common subsequence of the given string string and the type you declared with *.
Here we are find the Longest Common Subsequence (LCS) only and not any other thing because of two reasons
- We are required to delete minimum no. of characters possible and we can do that if we are able to accommodate(or think of it as the characters of the given string getting absorbed in the pattern’s characters. This is more clear if you have thoroughly understood the LCS problem) maximum number of characters in the pattern. So, whatever is left after this operation must e deleted to get the answer. So, the answer will be n - length of LCS. n is length of given string.
- We need a subsequence and not a substring because after deletion of let’s say a block of contiguous 1s, the two blocks of 0s of either side of it merges and we need to take into account this merge effect. Now, the subsequence by definition has this property of selecting non-contiguous blocks.
If you want a better intuition you can go here as this article is on a standard site.
This * will accommodate the maximum number of contiguous 0s or 1s while the 1 or 0 in the pattern will take care of not allowing the string to contain 1010 or 0101.
Now, we can start tracing the algorithm. Initialize a dp matrix using memset with all 0s as LCS of an empty string is always 0. I am saying again that the below algorithm is a cakewalk if you know LCS problem.
Here s is the given string. Also, please bear with the indexing as it starts from 1 to avoid buffer overflow and easy solution. So, the ith character of s or the pattern is represented by index i-1.
So, I will be using this i-1 notation forward to avoid confusion ahead and everytime the (i-1)th or (j-1) th character is written, it means the ith or the jth character of the string (as its indexing starts from 0, atleast in C++, JAVA, C and Python).
Now, if the (i-1)th character of s and the (j-1)th character of the pattern match
then we would be more than happy to take the ith character of s
because we want to no matter how, increase our LCS length. So,
dp[i][j] = 1 + dp[i-1][j-1]
Or if they don’t match then
if the (j-1)th character of the pattern is *
two cases arise,
the (j-2)th character i.e. the character of the pattern before the * matches the
(i-1)th character in the string or not
if it matches
then we should include (i-1)th character in our LCS length as well
i.e. dp[i][j]= 1+ dp[i-1][j]
if it does not match
then we can either
1. assume to have 0 occurrences of this (j-2)th character (the one before star)
i.e. and find the LCS of string s till (i-1) th character with 0 occurrences of
(j-2)th character represented by dp[i][j-2]
2. leave the (i-1)th character of s from our LCS length i.e. find the LCS without
this (i-1) th character but including (j-2)th character any number of times so
we need * as well which is represented by dp[i-1][j]
Now, it is clear that these two cases are mutually exclusive as well exhaustive and
since we need to find the "Longest"CS, we can take the maximum of these two cases.
So, dp[i][j] = max( dp[i][j-2], dp[i-1][j] ) .
or the (j-1) the character of the pattern is a normal one i.e. 0 or 1 and since we are here,
this case denotes that neither (i-1)th character of s and (j-1)th character
of the pattern match nor the (j-1)th character of the pattern is * which
reduces this case to normal mismatch of characters case in the
standard LCS problem.
You can go ahead to derive it properly like I did above or just use your
understanding from the LCS problem.
So, dp[i][j] = max( dp[i-1][j], dp[i][j-1] ).
Just bear with me for a second more and then I will set you free.
Now since we had two cases of 1* 0* 1* or 0* 1* 0*.
We can just run the above algorithm for both of the them and then subtract the maximum of the two from the length of the string s which is n.
This code although if the first look seems to be O(n* m) which is the standard time complexity of LCS problem but if look closely, my m never exceeds 6 (the length of 1* 0* 1* or 0* 1* 0*).
So, this is in a nutshell O(2* 6* n) which is equivalently O(n). 2 is multiplied to take into account the running of the algorithm twice, each time with different pattern.
Now, the space complexity by the same logic above is also O(2* 6* n) which is again O(n) but you go ahead and reduce it to strictly O(n) since we only need the previous row only at any time. To do so see this.
The post is complete then you are free to leave but if you want you can remain for my last observation which I have not confirmed yet.
Don’t you think that both 1* 0* 1* and 0* 1* 0* can be merged into simply 0* 1* 0* 1* as this also can make both of them with the same logic of using * as 0 (zero) or more occurrences.
i.e. you can take the last 1* (the rightmost one) and count as 0(zero) occurrences of it to convert it into 0* 1* 0* or take the first 0* as 0 (zero) occurrences to make it 1* 0* 1*.
You can check that this works on s= 011100001011101 or s= 0110 and s=111111 as well.
In fact this works for s=1010 as well and you can now pretty much see that is is giving correct answers.
But there’s a catch here this would not work and we would prove this by “contradiction using example” technique { 
? you: but you (writer) never bothered about proving the above AC solution since just being AC doesn’t surely mean it works for any n because the test cases might be missing some cases or even more important thing is that one only knows AC verdict after submission only and if it turns out to be wrong you are at double loss. One because of incurring penalty for a wrong submission and secondly and more significant thing is that time was wasted in building an incorrect solution in a limited time contest and also that if one can not atleast prove it intuitively (no one is asking for a strict mathematical proof) then one himself does understand how the solution actually works, me: the way I represented it cover all cases and this is DP which finds answer by exhaustive(covering all cases) searching and you can always state a one line proof (but only after stating a correct and working algorithm) by saying that I found this answer by considering all the possible cases so whatever answer I have is the most optimal, one can find}
Let s=0101 and this would give 0 while its correct answer is 1.
Actually this reduction works only for the subsequence restricting 1010 and it considers as 0101 as pure. Thus be careful with what you are making a pattern for to match. You can see the below problem as it is kind of related to the same merging or two sequences into single one.
You can refer Shortest Common Supersequence (here) .
Enough of it. It ends now!!!.
1 Like
This is code is just like an abstract(abstract by defintion means hiding the details) implmentation of my code. You can check it out in my reply to myself which is just above your post but lemme make you know in advance that this demands patience.
See my reply to the above post.
You can even make the time complexity to be O(1) by using the optimized space version of LCS of swapping the string i.e. making the dp array of length m which is exactly always.
No, its not counting bits. Check my reply to the above post.
Brute force will be of exponential time complexity i.e. you can either delete ith character of not.
So, you have 2 choices for each character of s (the given string) and length = n, so the time complexity is O(2^n) but if you observe this is standard DP property and this can be solved in O(n) time and O(1) space. See my post somewhere above if you want to know a more intuitive solution rather than the editorial’s one.