1 for both
String1 (11011000)->1111000
String2 (011011000)–> 01111000
I also did the same and its the wrong approach I think!
It wail fail for the test cases i mentioned above!
i have done the same thing but WA
Here is my code. Did the same thing but got WA.
int main() {
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
int count0 = 0;
int count1 = 0;
vector<char>p;
int k=0;
for(int i=0 ; i<s.length();i++){
p.push_back(s[i]);
while(s[i]==s[i+1]) {
i++;
}
}
for (int j = 0; j < p.size(); ++j) {
if(p[j]=='0') {
count0++;
}
else
count1++;
}
if(min(count1,count0)-1 == -1){
cout<<"0"<<endl;
}
else
cout<<min(count1,count0)-1<<endl;
}
return 0;
}
11011000 - output: 1 i.e removing index 2 (starting from 0)
011011000- output: 1 i.e removing index 3
in both cases 1 is the minimum no of character to delete so that both 1010 & 0101 subsequences are avoided.
Well I used DP to calculate 6 counts for every run of either 0 or 1, the counts respectively represented the min deletion for a sequence of 0s, 1s, 0s and then 1s, 1s and then 0s, 0s then 1s then 0s and 1s then 0s then 1s; the updations are easy.
My Submission
The final string can either be solely of 0s, solely of 1s, of 0s and then 1s and so on; those are the 6 possibilities
Your approach fails for case 1001001111.
Could anyone please point out the test case for which this will fail-
`#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
int count = 0;
int n = s.length();
int f = 0, j = 0, aa[10000] = { 0 }, bb[10000] = { 0 };
for (int i = 0; i < n; i++) {
if (s[i] == '0' && f == 0) {
count++;
f = 1;
aa[j]++;
}
else if (s[i] == '1') {
j++;
f = 0;
}
else {
aa[j]++;
count++;
}
}
if (count == 1 || count == 0 || j == 0) {
count = 0;
}
else if (s[0] == '0' && s[n - 1] == '0') {
sort(aa + 1, aa + j);
count = min(count - aa[0] - aa[j], count - aa[j - 1]);
}
else {
sort(aa, aa + 10000);
count = count - aa[9999];
}
j = 0;
int count1 = 0;
f = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '1' && f == 0) {
count1++;
f = 1;
bb[j]++;
}
else if (s[i] == '0') {
j++;
f = 0;
}
else {
count1++;
bb[j]++;
}
}
if (count1 == 1 || count1 == 0 || j == 0) {
count1 = 0;
}
else if (s[0] == '1' && s[n - 1] == '1') {
sort(bb + 1, bb + j);
count1 = min(count1 - bb[0] - bb[j], count1 - bb[j - 1]);
}
else {
sort(bb, bb + 10000);
count1 = count1 - bb[9999];
}
if (count < count1) {
cout << count << endl;
}
else {
cout << count1 << endl;
}
}
}`
Bro can you tell where you learned and practiced DP.
Can’t understand that much from the code, really weak in CPP and DP. My approach was to keep a stack tracking the current state of elements taken, until that is invalid (1010 or 0101) in which case I return INT_MAX, if my state is 010 and a 0 comes, I keep it same as 010 and if it was 101 and a 1 comes I keep it same as 101.
Then I was recursively calling the function with res = MIN(select current element, not select current element) and I was incrementing a deletion variable keeping track of number of deletions. If I exceed the length of array, I return deletions.
Can you tell me if this approach is totally insane or maybe it can be used?
Can someone help me identify where I am going wrong?
Can’t it be solved using this approach?
I check if there is a lcs of given string with 0101 or 1010.
If length of lcs <=3, then no deletions in s are required else delete any character i (0<i<n) and recursively solve for it and take the minimum out of it like the loop inside recursive solution in rod-cutting problem;
int delete(string s, int i, int n){
if (lcs(s,“0101”)<=3 && lcs(s,“1010”) <=3)
return 0;
else
int i,mi=999999;
for(i=0;i<n;i++){
string p=s;
erase(i,1); // The string s is copied to p and ith character is erased.
mi=min(mi, 1+del( p, i, n-1 ));
}
}
I think it might work, but you would need to memoize, also you can directly work on runs(blocks of same character).
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.