https://www.codechef.com/viewsolution/38086602 Can you tell me the error in this code.
@rishup_nitdgp @manishtanwar @rahuldugar @admin
Hidden test cases of the codechef september 20 cook off were very weak.
On problem CodeChef: Practical coding for everyone.
if the test case is
1
16 2
0010000100001000
Then most of the accepted submissions gives the output 9.
But its correct output should be 8.
We need to cut (2-3) and (12-13) wire and then disconnect 4, 5, 6, 7, 9, 10, 11, 12 bulbs.
One of the submissions that was incorrect and got accepted is CodeChef: Practical coding for everyone.
This was the random person i don’t know.
I was stucked in fixing this test case and my cook off got ruined.
How can this much important test case can be missed by the setters.
This contest should be unrated for all.
3 Likes
congo 
Please help still getting WA. I got the correct output for all the above-hidden test cases.
https://www.codechef.com/viewsolution/38094884
here is my solution
i have tries all possible test cases
and all of them were correct.
but still i got wrong answer.
please help me!
i am very tensed.
Thanks a lot… I was wondering where my solution was going wrong 
2 Likes
Can someone tell me where did i go wrong?
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long int ll;
// Declare a multimap
multimap<int, string> MM;
define M_PI 3.14159265358979323846
const int M=1e9+7;
long long mod(long long x){
return ((x%M + M)%M);
}
long long add(long long a, long long b){
return mod(mod(a)+mod(b));
}
long long mul(long long a, long long b){
return mod(mod(a)*mod(b));
}
int main()
{
ll t;
cin>>t;
while(t–)
{
ll n,k,m,l,r,c=0,i,j,fs=0,vs=-1,ve=-1;
cin>>n>>k;
string s;
ll z[n];
cin>>s;
j=0;
for(i=0;i<n;i++)
{
if(s[i]==‘0’ && i==n-1)
{
c++;
ve=c;
}
else if(s[i]==‘0’)
{
c++;
if(i==0)
fs=1;
}
else if(s[i]==‘1’ && c>0)
{
if(fs==1)
{
fs=0;
vs=c;
}
else
{
z[j]=c;
j++;
}
c=0;
}
//cout<<c<<" “;
}
//cout<<”\n";
sort(z,z+j,greater());
c=0;
//cout<<vs<<" “<<ve<<”\n";
for(i=0;i<j;i++)
{
if(k>=2)
{
if(vs!=-1 && ve!=-1 && (vs+ve)>z[i])
{
i–;
k=k-2;
vs=-1;
ve=-1;
}
else if(vs!=-1 && ve!=-1 && max(vs,ve)>z[i])
{
i–;
k–;
if(vs>ve)
vs=-1;
else if(ve>vs)
ve=-1;
}
else if(vs!=-1 && vs>z[i])
{
i–;
k–;
vs=-1;
}
else if(ve!=-1 && ve>z[i])
{
i–;
k–;
ve=-1;
}
else
{
k=k-2;
}
}
else
{
c=c+z[i];
}
//cout<<z[i]<<"("<<k<<") , ";
}
while(k>0)
{
if(vs!=-1 && ve!=-1)
{
k--;
if(vs>ve)
vs=-1;
else
ve=-1;
}
else if(vs!=-1)
{
k--;
vs=-1;
}
else if(ve!=-1)
{
k--;
ve=-1;
}
if(vs==-1 && ve==-1)
break;
}
if(ve!=-1)
c=c+ve;
if(vs!=-1)
c=c+vs;
cout<<c<<"\n";
}
return 0;
}
//in name of THE GOD
#include
#include
#include <string.h>
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define tinput int t; cin>>t; while(t–)
#define rep(i,n) for((i)=0; (i)<(n); (i)++)
ll min(ll x, ll y) {
return (x<y)?x:y;
}
int max(int x, int y) {
return (x>y)?x:y;
}
// atoi string convert into int
// stol string convert into long
// stoll string convert into long long int
// memset(dp, -1, sizeof(dp));
// cout<<fixed<<setprecision(10)<<ans; for 10 decimal value
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// READ THE QUESTION PROPERLY
tinput
{
int n,k,x,y,count = 0; cin>>n>>k;
string s;
cin>>s;
vectorzmid,zend,gcut;
for(int i=0;i<s.size();i++) if(s[i] == '1') count++;
if(count == 0 || count == n)
{
cout<<0<<"\n";
}
else if(k == 0)
{
cout<<n-count<<"\n";
}
else
{
for(int i=0;i<s.size();i++)
{
if(s[i] == ‘1’)
{
zend.pb(i);
x=i;
break;
}
}
for(int i=s.size()-1;i>=0;i–)
{
if(s[i] == ‘1’)
{
zend.pb(s.size()-1-i);
y=i;
break;
}
}
/int z=x+1;
while(z!=y+1)
{
if(s[z] == ‘1’ && z-x-1!=0)
{
zmid.pb(z-x-1);
x=z;
}
else if(s[z] == ‘1’ && z-x-1 == 0) x=z;
z++;
}/
//cout<<x<<" “<<y<<”\n";
int fp=x,sp=x+1;
while(sp!=y+1)
{
if(s[sp]==‘1’)
{
if(sp-fp-1 == 0)
{
fp=sp;
}
else
{
int zerocount = sp-fp-1;
zmid.pb(zerocount);
fp=sp;
// cout<<zerocount<<"\n";
}
}
sp++;
}
sort(zmid.begin(),zmid.end(),greater());
sort(zend.begin(),zend.end(),greater());
/* for(int i=0;i<zmid.size();i++) cout<<zmid[i]<<" “;
cout<<”\n";
for(int i=0;i<zend.size();i++) cout<<zend[i]<<" “;
cout<<”\n";*/
if(k%2!=0)
{
k–;
gcut.pb(zend[0]);
zend[0]=zend[1];
zend[1] = 0;
}
int i=0;
while(k!=2 && i!=zmid.size())
{
gcut.pb(zmid[i]);
k-=2;
i++;
}
if(k==2 && i!=zmid.size())
{
if(zmid[i] > zend[0]+zend[1])
{
gcut.pb(zmid[i]);
k-=2;
}
else
{
gcut.pb(zend[0]);
gcut.pb(zend[1]);
}
}
else if(k == 2 && i == zmid.size())
{
gcut.pb(zend[0]);
gcut.pb(zend[1]);
}
else if(k!=2 && i==zmid.size())
{
gcut.pb(zend[0]);
gcut.pb(zend[1]);
}
//for(int a=0;a<gcut.size();a++) cout<<gcut[a]<<" “;
// cout<<”\n";
int sum = 0;
for(int a=0;a<gcut.size();a++)
sum+=gcut[a];
cout<<n-sum-count<<"\n";
}
}
return 0;
}
can anyone tell what wrong with this code, I got right ans for all test cases given above,
still gives wrong ans.
How can the overall complexity of the code be O(n) , when there is sorting involved in the code.
The vector storing the lengths of zero’s (which can be of size upto n/2, when the string S is alternate 0’s and 1’s eg. 0101010101…) is getting sorted which would have complexity nlogn.
2 Likes
yes @rishup_nitdgp admin please check for these cases , many of the wrong submissions got accepted , how can you forget to add trivial test cases like these .
1 Like
Hi, I have checked for all test cases shared here but still WA:( Can someone please tell me one case for which my soln might be failing? CodeChef: Practical coding for everyone
I don’t know why is it giving WA
Please tell me what did I do wrong?
#include
#include
#include
#include
using namespace std;
#define ll long long
int main()
{
ll t;
cin>>t;
while(t–)
{
ll n,k;
cin>>n>>k;
string s;
cin>>s;
ll twowire[100005];
ll onewire[3];
ll len=n;
ll szero=0;
ll zero=0;
//calculating side zeros
//left
for(ll i=0;i<len;i++)
{
if(s[i]!=‘0’)
{
//szero=0;
onewire[0]=szero;
break;
}
else
{
szero++;
}
}
//*****************************************************************************************************************************//
// cout<<"Left one wire "<<onewire[0]<<endl;
//right
szero=0;
for(ll i=len-1;i>=0;i–)
{
if(s[i]!=‘0’)
{
onewire[1]=szero;
break;
}
else
{
szero++;
}
}
//*****************************************************************************************************************************//
// cout<<"Right one wire "<<onewire[1]<<endl;
//exception
if(onewire[0]==len || onewire[0]==0)
{
cout<<“0”<<endl;
continue;
}
ll ex2=0;
for(ll i=0;i<len;i++)
{
if(s[i]==‘0’)
ex2++;
}
//*****************************************************************************************************************************//
// cout<<"Number of zeros "<<ex2<<endl;
if(k==0)
{
cout<<ex2<<endl;
continue;
}
// making both the arrays
ll putin=0;
for(ll i=onewire[0]+1;i<=(len-onewire[1]);i++)
{
if(s[i]==‘0’)
{
zero++;
}
else if(s[i-1]==‘0’ && s[i]==‘1’ )
{
twowire[putin]=zero;
putin++;
zero=0;
}
}
sort(onewire,onewire+2,greater<ll>());
sort(twowire,twowire+putin,greater<ll>());
//*****************************************************************************************************************************//
/*cout<<"The two wire array"<<endl;
for(ll i=0;i<putin;i++)
{
cout<<twowire[i]<<" ";
}
*/
//cout<<endl;
ll gcut=0;
if(k%2==1)
{
gcut+=onewire[0];
k--;
}
ll iterate=0;
while(k>2)
{
gcut+=twowire[iterate];
iterate++;
k-=2;
}
if(k==2)
{
if(n%2==0)
gcut+=(max(twowire[iterate],max(onewire[0],onewire[1])));
else
gcut+=max(twowire[iterate],onewire[1]);
}
cout<<ex2-gcut<<endl;
}
return 0;
}
I got 6, and I got WA you telling me my wrong code isn’t right enough to get accepted
Can anyone please help me to find what is the mistake ? I have tried all test cases i can make and mentioned in the discussion, for all these testcases i m getting correct answer.
Explanation of the logic is below the code.
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int main()
{
fast;
ll t;
cin>>t;
ll temp;
while(t--)
{
ll n, k;
cin>>n>>k;
string s;
cin>>s;
vector<ll> v;
ll rightZ = 0, leftZ =0, ones=0, i;
ll rightPos, leftPos;
for(i=0; s[i]=='0'; i++) leftZ++;
leftPos = i;
for(i=s.size()-1; s[i]=='0'; i--) rightZ++;
rightPos = i+1;
for(i=leftPos;i<rightPos;i++)
if(s[i]=='1') ones++;
ll zeros = n-ones;
ll offed = 0;
if(leftZ==n)
{
cout<<0<<endl;
continue;
}
if(k==0)
{
cout<< n-ones <<endl;
continue;
}
if(k==1)
{
cout<< zeros - max(rightZ, leftZ) << endl;
continue;
}
for(i=leftPos;i<rightPos;i++)
{
if(s[i]=='0')
{
temp = 0;
ll j=0;
for(j=i;s[j]=='0' && j<rightPos; j++ )
temp++;
v.push_back(temp);
i = j-1;
temp=0;
}
}
if(rightZ> leftZ)
swap(rightZ, leftZ);
sort(v.begin(), v.end(), greater<ll>() );
i=0;
if(k%2)
{
offed += leftZ;
leftZ = 0;
k--;
}
else
{
if(v.size())
{
if( (rightZ+leftZ) >= v[0] )
{
offed += (rightZ+leftZ);
rightZ = 0;
leftZ = 0;
k -= 2;
}
}
}
while( (k>0) && (i<v.size()))
{
offed += v[i];
k -= 2;
i++;
}
if(k!=0 && rightZ!=0)
{
k--;
offed += rightZ;
rightZ=0;
}
if(k!=0 && leftZ!=0)
{
k--;
offed += leftZ;
leftZ=0;
}
cout<< zeros - offed <<endl;
}
return 0;
}
First of all I am counting the numbers of zeros present in right and left ( rightZ , leftZ) and then total number of ones (ones) and zeros (zeros).
At the time of counting zeros in right and left side I have also stored their index.
Then checked some base condition.
Then stored the length of all continious zeros excluding which are in the first and last because I have kept their count seperately.
And the length of zeros in descending order.
And then if K is odd it is always good to cut one of wires which is in last or first. Because only even
cuts are required to required to remove bulb from middle.
If K is even then I m checking whether the sum of rigthZero and leftZero is greater than largest continious length, if yes then cut both rightSide bulbs and leftSide bulbs else cut the largest continious length of zeros, because in both the case we have to use 2 cuts only and we have to remove maximum zeros in minimum cut.
Then we are cutting first K /2 cuts to remove the K/2 largest continious zero and if count of continious zeros are less than that then we are checking if it is possible to cut right Side or leftSide zeros, if yes then also remove it.
All bulbs removed during this process , its count is stored in offed (total no of bulbs offed) and then our answer is total zeros - offed.
@kingvarun @sksama @rishup_nitdgp @manishtanwar @rahuldugar @admin Pls help 
suppose LeftZ =10, rightz=9; v[0]=5
k is odd;
it will enter if (k % 2) condition and leftz will become 0, and k becomes even;
Now inside
{
offed += v[i];
k -= 2;
i++;
}
only the v[] elements will be chosen and k will become 0
RightZ will be ignored
if(k!=0 && rightZ!=0) it wont enter this as k=0
Let me know if it made sense