1
11111111111100001000010000111111111100000
Your Output is 12 but answer should be 7 by removing 2-1 in mid and 5-0 at last
1111111111110000000000001111111111
1 Like
Oh good, didn’t notice that 
; but you should be able to prove the correctness of your solution(which I think it is correct)! Can you?
Please explain with an example.it would be a great help. please
bro please explain your code in detail.please
I think this can be solved in o(n) time complexity.
we want (101) or (010) as our resulted block string.
this can be achieved by -
case 1 :- the string starts with ‘1’
delete all the ‘0’ blocks between first ‘1’ and last ‘1’ except the block having
maximum frequency + all the ‘0’ blocks after the last ‘1’ .
case 2:- the string starts with ‘0’
same as above with (‘1’ replaced with ‘0’) .
here is my code -
#include <bits/stdc++.h>
using namespace std ;
int main()
{
int t ;
cin>>t ;
while(t--)
{
int n ;
string str ;
cin>>str ;
n = str.length() ;
int num_1,num_2,num_3,num_4 ;
int cnt_0=0, cnt_1=0, cnt_temp=1 ;
vector<int> cnt0,cnt1,cnt ;
int start ;
str[0]=='0'?start=0:start=1 ;
string str1 ;
if(n<=3)
{
cout<<"0\n" ;
continue ;
}
for(int i=0;i<n;i++)
{
if(i>0)
{
if(str[i-1]!=str[i])
{
str1.push_back(str[i]) ;
cnt0.push_back(cnt_0) ;
cnt1.push_back(cnt_1) ;
cnt.push_back(cnt_temp) ;
cnt_0 = cnt_1 = 0 ;
cnt_temp = 1 ;
if(str[i]=='0')
cnt_0 = 1 ;
else
cnt_1 = 1 ;
}
else
{
if(str[i]=='0')
cnt_0++ ;
else
cnt_1++ ;
cnt_temp++ ;
}
}
else
{
str1.push_back(str[i]) ;
if(str[i]=='0')cnt_0++ ;
else cnt_1++ ;
}
}
cnt.push_back(cnt_temp) ;
if(str[n-1]=='1')
cnt1.push_back(cnt_1) ;
else
cnt0.push_back(cnt_0) ;
n = str1.length() ;
if(start == 1)
{
int temp = 0, maxi=0, len ;
for(int i=1;i<n-2;i++)
{
if(str1[i]=='0')
{
maxi = max(maxi,cnt[i]) ;
temp+=cnt[i] ;
}
}
if(str1[n-2]=='1')
temp= temp - maxi + cnt[n-1] ;
else
{
temp+=cnt[n-2] ;
maxi = max(maxi,cnt[n-2]) ;
temp-=maxi ;
}
num_1 = temp ;
cout<<num_1<<"\n" ;
}
else
{
int temp = 0, maxi=0, len ;
for(int i=1;i<n-2;i++)
{
if(str1[i]=='1')
{
maxi = max(maxi,cnt[i]) ;
temp+=cnt[i] ;
}
}
if(str1[n-2]=='0')
temp= temp - maxi + cnt[n-1] ;
else
{
temp+=cnt[n-2] ;
maxi = max(maxi,cnt[n-2]) ;
temp-=maxi ;
}
num_2 = temp ;
cout<<num_2<<"\n";
}
}
return 0 ;
}
but I am getting W.A can anyone explain why??
Cannot we do it using simple brute force approach??
Please help as this problem seems to be quite straight forward.
Thanks.
hey. I did exactly like this but it will give WA,
example - 11110110000100
as per our code, answer will be 3(remove 2 ‘0’ blocks or ‘1’ blocks), but the answer should be 2(remove first 0 and last 1)
11111111111100001000010000111111111100000
Your output is 12 but correct output is 7
My solution: CodeChef: Practical coding for everyone
Where does my code fail?
Please let me know if someone finds out.
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 