Can someone please help me understand how this is coming? I am not able to understand this
Exactly…I am getting 6 too…Throughout the whole contest, I was struggling with this…
Frequency array looks like this
25 → 18 (0 0 1 5 9 7 2 5)
18 → 9 (0 0 0 0 9 7 2 5)
9 → 8 (0 0 0 0 0 7 2 5)
8 → 5 (0 0 0 0 0 0 2 5)
Giving a total of 6 prefix zeroes
Finally an editorial in which i don’t have to scroll hundreds of lines in order to find the setter’s and the tester’s solution
#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);
void solve()
{
int n,k;
cin>>n>>k;
string s;
cin>>s;
int low=0,high=n+1;
while(low<=high)
{
int mid=(low+high)/2;
int ops=0;
for(int i=mid-1;i>=0;i--)
{
int rem=(ops+s[i]-'0')%10;
if(rem!=0)
ops+=10-rem;
}
if(ops<=k)
low=mid+1;
else
high=mid-1;
}
// dbg(low,high);
cout<<high<<"\n";
}
signed main()
{
FIO
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t;
cin>>t;
while(t--)
solve();
return 0;
}
Can anyone help why it is giving WA on 2nd 3rd and 5th TC
Probably undefined behaviour due high = n + 1
so you would be accessing s[n]…
But it works fine when you access s[-1] …
So not sure why but it gives ACs after initializing high = n
hi anyone can you explain O(n) solution in more detail please if you have time i am finding really hard to understand may be in more simple way please
Cout<<low
Will be final ans
Can someone tell me where i’m going wrong?
I am passing all sample test cases but getting wa
my soln: https://www.codechef.com/viewsolution/57415756
Awesome approach & explaination.
Can someone help me to add link my solution here.
I’m facing problems.
I’m pretty sure 5 is the correct answer. Do you have any other test cases to help me debug? My solution (CodeChef: Practical coding for everyone) is passing only one test case when I submit.