It works, right? My solution is similar, except you could have optimized it by working on blocks rather than each character!
My Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
// #ifndef ONLINE_JUDGE
// // for getting input from input.txt
// freopen("input.txt", "r", stdin);
// // for writing output to output.txt
// freopen("output.txt", "w", stdout);
// #endif
int t;
cin>>t;
while(t--){
string s;
cin>>s;
int i;
ll n = s.length();
int m=s[0]-'0';
ll cnt=1;
for(i=1;i<n;i++){
int val = (m+1)%2;
if(s[i]-'0'==val){
m+=1;
cnt++;
}
}
if(cnt<4){
cout<<"0"<<"\n";
continue;
}
int no1=0,no0=0,max1=0,max0=0;
ll count=0;
for(i=0;i<n;i++){
if(s[i]=='1'){ no1++;
count++;}
else count=0;
if(max1<count) max1=count;
}
ll ans1,ans0;
ans1 = no1-max1;
count=0;
for(i=0;i<n;i++){
if(s[i]=='0'){
no0++;
count++;
}
else count=0;
if(max0<count) max0=count;
}
ans0 = no0-max0;
cout<<min(ans1,ans0)<<"\n";
}
return 0;
}
CAN SOMEONE PLEASE TELL THE MISTAKE IN MY APPROACH AND TESTCASE IT IS FAILING .
Never mind, I solved it 2 minutes after making the above post. I donāt know what was the stupid mistake, but here is my solution (easy to understand) using a stack to keep track of current elements and DP (memoization):
https://www.codechef.com/viewsolution/28459202
111000010011000000111000000000101
in your approach answer is 8, but actually answer is 7.
2 Likes
This editorial is wierdā¦ Itās not properly explained in 3 paragraphā¦ What do you mean by considering interval of [L, R]ā¦!!! And how are you calculating the no of deletionsā¦ You mentioned some formulas with A, Bā¦ Pa etcā¦ But itās very confusingā¦!! Plz understand that when you are making editorialā¦ You should keep in mind that viewers have no idea about itā¦!!
If anyone can explain it simplyā¦ That would be truly appreciatedā¦!
If you have same number on the either end, you can purify the string by removing all other blocks except these two. You donāt need to remove N-1 blocks such as in the case 000111100111110000. You can just remove the middle block.
i tried the same approach. Why the answer should be 7?
Because you can remove the 1ās in the middle and leave the 1ās at both ends.
ohhā¦got itā¦thanks
For which test case does this code fail? I canāt seem to find an error in my code ;(
https://www.codechef.com/viewsolution/28460061
Code:
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
for(int z = 0 ; z<n ; z++){
string s;
cin>>s;
int altz = 0;
vector<int> alternateO,alternateZ;
for(int i = 0 ; i<s.size() ; i++ ){
if(s[i]=='0'){
altz++;
}
int c = 1;
int flag = -1;
if(s[i]=='0')
flag = 0;
while( s[i] == s[i+1] && i+1 < s.size() ){
i++;
c++;
}
if(flag == 0){
alternateZ.push_back(c);
}
}
int alto = 0;
for(int i = 0 ; i<s.size() ; i++ ){
if(s[i]=='1'){
alto++;
}
int flag = -1;
if(s[i]=='1')
flag = 0;
int c = 1;
while(s[i] == s[i+1] && i+1<s.size()){
i++;
c++;
}
if(flag==0)
alternateO.push_back(c);
}
int delTemp = 1000000;
if(s[0]=='0' && s[s.size()-1]=='0'){
delTemp = 0;
for(int i = 1; i<alternateZ.size()-1 ; i++)
delTemp+=alternateZ[i];
}
else if(s[0]=='1' && s[s.size()-1]=='1'){
delTemp = 0;
for(int i = 1 ; i<alternateO.size()-1 ; i++)
delTemp+=alternateO[i];
}
sort(alternateO.begin(),alternateO.end());
sort(alternateZ.begin(),alternateZ.end());
int delO = 0, delZ= 0;
auto it = alternateO.begin();
while( alto>1 ){
delO += *it;
it++;
alto--;
}
it = alternateZ.begin();
while( altz>1 ){
delZ += *it;
it++;
altz--;
}
cout<<min(min(delO,delZ),delTemp)<<endl;
}
}
Sure. P[w][i] is the number of characters equal to w in the first i letters of the given string (where w is either 0 or 1). To calculate it, we can see that there are P[w][i-1] characters equal to w in the first i-1 letters of the string, and if S[i] = w, then the i letter is also a w so we should increment P[w][i] by one.
The second line you quoted, calculates the answer. It assumes that all the w characters in the intervals [1, i) and (j,n) are to be deleted and all the 1-w characters in the interval [i,j] are to be deleted as well. We have P[w][i-1] w characters in the interval [1,i) as explained above and P[w][n] - P[w][j] in the interval (j,n]. You can see here for more details on partial sums (or prefix sums as some call them).
3 Likes
Sorry about that. I tried to write the editorial as simple as possible. As explained in the previous paragraphs, the string should at most consist of three blocks. We can fix the first and last indices of the middle block (the indices that wonāt be deleted and would be a part of the middle block in the end). Consider the first one to be L and the last one to be R. Now if we want the middle block to be equal to for example 0, we have to delete all the 1's in the interval [L,R] of the string. In order to count the number of 1 's in an interval of the string, we can use prefix sums (or a straightforward dp). For more details on prefix sums you can visit here.
1 Like
what is Si?
@codechef The explanation should be elaborated with an example explaining each step of the method. Otherwise how can i learn something newer and master it. If it is like this how can i improve? People who has interest in cp will eventually loose it. Please consider my words. I am unable to understand it clearly.
S_i denotes the i-th letter of the given string S. These are basic notations used in almost every problem.
I think this editorial is actually over-explained a little, itās not very good to lengthen it too much. But perhaps I can help you understand it. What part donāt you understand?
i aggree with u bro
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
while(t--){
string s;
cin>>s;
ll biggest_bunch1=0;
ll biggest_bunch0=0;
ll count0=0, count1=0;
ll total_count0=0;
ll total_count1=0;
for(unsigned ll i=0;i<s.length();i++){
if(s[i]=='0'){
count1=0;
count0++;
biggest_bunch0=max(biggest_bunch0, count0);
total_count0++;
}
else if(s[i]=='1'){
count0=0;
count1++;
biggest_bunch1=max(biggest_bunch1, count1);
total_count1++;
}
}
// cout<<"0->"<<biggest_bunch0<<endl;
// cout<<"1->"<<biggest_bunch1<<endl;
cout<< min(total_count0-biggest_bunch0, total_count1-biggest_bunch1)<<endl;
}
return 0;
}
Can anyone tell me where does my code fail??
i still didnāt get how Mn is giving answer
For which test case will this fail ?
Please helpā¦
Language : C++14
#include<bits/stdc++.h>
#define ll long long int
#define mod 1000000007
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define endl ā\nā
using namespace std;
bool checklast(ll i, ll diff, ll ans[], ll ans2[])
{
ll j;
for(j=1; j<diff-1; j++)
{
if(ans[i]==ans2[j])
{
ans2[j]=-1;
return 0;
}
}
return 1;
}
int main()
{
fastio
ll t;
cin>>t;
while(tā)
{
string a;
cin>>a;
ll i;
ll n=a.size();
ll diff=1;
for(i=0; i<n-1; i++)
{
if(a[i+1]!=a[i])
{
diff++;
}
}
if(diff<=3)
{
cout<<0<<endl;
continue;
}
ll ans[diff];
ll x=0;
ll k=1;
for(i=0; i<n-1; i++)
{
if(a[i+1]==a[i])
{
k++;
}
else
{
ans[x++]=k;
k=1;
}
}
ans[x++]=k;
ll ans2[diff];
copy(ans, ans+diff, ans2);
sort(ans, ans+diff);
ll g=0;
ll flag=4;
ll left=diff;
for(i=0; left>3; i++)
{
if(checklast(i, diff, ans, ans2))
{
if(diff%2==0 && flag==4)
{
g+=ans[i];
left-=1;
flag=3;
}
else
{
continue;
}
}
else
{
g+=ans[i];
left-=2;
}
}
ll neww=i;
ll cont=0;
for(; i>=0; iā)
{
if(checklast(i, diff, ans, ans2))
{
cont++;
}
}
if(cont==2 && diff%2!=0)
{
g-=ans[neww-1];
g+=ans2[0];
g+=ans2[diff-1];
}
cout<<g<<endl;
}
return 0;
}