I can’t figure out the reason for getting WA
https://www.codechef.com/viewsolution/38080721
welcome
1
11 3
00010000100
in this test case your code gives output 0
but the answer is 2
2 Likes
A comment on the question says that all 3 operations can be used only once and in order. It was not clearly mentioned in the question. I think here is where most of us went wrong.
1 Like
It is evident by the number of wrong submissions even on top of leaderboard.
My intuition is the same as the editorials. What I did was I counted the contiguous all the subsequences of 0’s and stored them in the array arr and also added the sum of the length of first and last subsequence and sorted the array. Then I traversed the array for how many subsequences are there such that when I remove the connections they won’t turn on even when I start switching on the lamps.
But, I am getting a WA, I tried a lot of different things but am not able to find out the error. Please, help.
Here is the link to my solution
1
11 3
00010000100
wrong here , ans will be 2
bro, I corrected my code, but it still gives WA.
here is the link to my updated solution.
Please, help!
@admin @rishup_nitdgp
This is exactly what I did! Can you look at my code and tell me what’s wrong?
My Code
here is my python3 solution loaded with comments ,posting with the intension to help anyone who still trying to figure out a way to solve this.
do let me know if anything is unclear.
for _ in range(int(input())):
n,k=map(int,input().split())
s=input()
i=0
while i<n and s[i]!='1':
i+=1
left=i # to sotore left groups of zero requires one cut
# condition to check if s if contains all zeros
# elif k==0 ,then asnwer would be equal to the number of zeros
# else we will continue .
if left==n :
print(0)
elif k==0:
print(s.count('0'))
else:
cut_len=[]
j=n-1
# loop to calculate zeros group in right extrem part of s
while j>i and s[j]!='1':
j-=1
# right holds the leght of right most zero group ,require one cut
right=n-j-1
# below to check if there is only one '1' in s
if i==j:
# if k==1 ,we can either cut left or right part with max zero
# since we have handle k==0 ,at this point if k!=1 ,then k>=2
# in this condition we can cut both end and answer would be zero
if k==1:
print(min(left,right))
else:
print(0)
else:
prev=i
K=i+1
# loop below is to calulate the size of each group falls between '1'
# and to store it into cut_len
# start form one postition right from the first '1'(i+1) and end at last '1' (j)
while K<=j:
if s[K]=='1':
if K-prev-1:
cut_len.append(K-prev-1)
prev=K
K+=1
# require 2 cuts for groups bound between '1' in s and 1 cut for left and right each
# condition to handle differnt cases
# if k==1 ,we can cut either of max(left,right) ,since cutting zero group which
# falls between one would not make any changes ,they need atleast 2 cuts to be in off state
# elif k is greater then cuts requiured to ensure all bulb to be in off state as per s
if k==1:
print(s.count('0')-max(left,right))
elif k>=2*(len(cut_len))+bool(left)+bool(right):
print(0)
else:
if k%2==0:
# if k is even then we can add the sum of left and right into cut_len
# sort in non-increasing order
# then would pick k//2 elements of cut_len
# the sum of selected elements would give us total bulb that can
# be ensured to be in off start with off state with atmost k cuts
# answer = total zero - sum(zeros in selected elements)
#print('here')
cut_len.append(left+right)
cut_len.sort(reverse=True)
total=sum(cut_len)
dis=sum(cut_len[:k//2])
print(total-dis)
else:
# in case of odd value
# k>=3 since we have hadle k==1 already
# dual variable stores values ,which shows how many zero group
# requiring two cuts can be disconnected in the beginning
# then we are left with at max 3 cuts
# with these 3 cuts we have two possible ways to make cut
# option 1: to cut left and right ,and leave with 2 cuts
# option 2: to cut a zero group requres 2 cut and cut max(left,right)
dual=(k-3)//2
total=s.count('0')
cut_len.sort(reverse=True)
dis=sum(cut_len[:dual])
chop=cut_len[dual]
print(total-dis-max(left+right,max(right,left)+chop))
2 Likes
https://www.codechef.com/viewsolution/38061797
can someone let me know why im getting TLE in this solution
For those of you searching for a test case:
11 2
00010000100
the answer here is 4 but you might be getting 5.
1 Like
Please help finding the bug. Here’s the commented code
PS- Thanks in advance
#include<bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
//#pragma GCC optimize(“Ofast”)
#pragma GCC target(“avx,avx2,fma”)
#pragma GCC optimization (“unroll-loops”
#pragma GCC optimize “trapv”
#define _GLIBCXX_DEBUG
#define ll long long int
#define ld long double
#define ull unsigned long long int // ranges from (0 - twice of long long int)
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i–)
#define pb push_back
#define mp make_pair
#define vll vector
#define MOD 1000000007LL
#define llpair pair<ll,ll>
#define INF 1000000000000000000ll // this is 1e18 long long
#define np next_permutation
#define PI acos(-1)
#define DEB(x) cout<<#x<<" "<<x<<endl;
#define rotate_left(vec,amt) rotate(vec.begin(),vec.begin()+amt,vec.end());
#define rotate_right(vec,amt) rotate(vec.begin(),vec.begin()+vec.size()-amt,vec.end());
#define all(x) x.begin(),x.end()
#define sortall(x) sort(all(x))
#define clr(x) memset(x,0,sizeof(x))
using namespace std;
int main()
{
speed;
ll t=1;
cin>>t;
while(t–)
{
ll n,k;
cin>>n>>k;
string s;
cin>>s;
vectorone,two; // one stores the length of 0s block which reuire 1 cut
// similarly for two
ll start=-1,finish=n,cnt=0; // start - index for first occurence of 1
// finish - index for occurence of 1 from last
rep(i,0,n)
cnt+=(s[i]=='0'); // count no of 0
if(cnt==n)
{
cout<<0<<endl;
continue;
}
rep(i,0,n)
{
while(s[i]=='0')
{
i++; // finding the index and also the length of block of 0 from starting
start=i;
}
break;
}
per(i,0,n)
{
while(s[i]=='0') //// finding the index and also the length of block of 0 from starting
{
i--;
finish=i;
}
break;
}
if(start!=-1)
one.pb(start); // storing in one
if(finish!=n)
one.pb(n-finish-1); // storing in one
else
{
finish--;
}
sort(one.begin(),one.end(),greater<ll>()); // sort in descending
for(ll i=start;i<=finish;i++)
{
ll len=0;
while( i<=finish && s[i]=='0') // finding blocks of 0 which require 2 cuts
{
i++;
len++;
}
// DEB(len);
if(len!=0)
two.pb(len);
}
sort(two.begin(),two.end(),greater<ll>()); //sort in desc
if(k==0)
{
cout<<cnt<<endl; // if k==0
}
ll ans=0,size=two.size(); // ans stores the maximum zeroes that can be removed using cuts
if(one.size()>0 && k>0)
{
ll temp=one[0]; // in each if block finding max ans for it
ll also=k-1;
rep(i,0,min(size,also/2)) // also stores the updated value of k
{ // we can take atmost max(two.size(),also/2) elements
temp+=two[i];
}
ans=max(ans,temp);
}
if (one.size()>1 && k>1 )
{
ll temp=one[0]+one[1];
ll also=k-2;
rep(i,0,min(size,also/2)) // similar as above for scenario when k>1 and one.size()>1
{
temp+=two[i];
}
ans=max(ans,temp);
}
if(k>=2)
{ // finally checking if we can obtain the max value by removing only 2 cut requiring elements
ll t1=0;
rep(i,0,min(size,k/2))
{
t1+=two[i];
}
ans=max(ans,t1);
}
cnt-=min(cnt,ans);
cout<<cnt<<endl;
}
return 0;
}
weak testcases
many of the solutions got accepted on
1
12 2
000100001000
correct output : 4
those who got 6 as output, got accepted.
1 Like
Weak test cases ruined my efforts…very disappointed by the testers
3 Likes
I’m getting the output 3 but I’m still getting WA on submissionhttps://www.codechef.com/viewsolution/38085094. Please help in finding the problem.
I’m also getting answer 4 but still I’m getting WA on submission.CodeChef: Practical coding for everyone
Just make a vector of partial blocks and whole blocks. sort descending.
Then ans1 = we fix partial blocks first by using 1 moves (k–)
ans2 = we fix whole blocks first by using 2 moves(k-2)
Also if there are two partial blocks(there can be 2 at max), then,
ans3 = we fix only one of the partial blocks and then the whole blocks and then the second partial block.
ans is the minimum of the three.
My submission: CodeChef: Practical coding for everyone