PREZ-Editorial

editorial
, , , ,
24

Can someone please help me understand how this is coming? I am not able to understand this

25

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

26

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 :laughing:

1 Like
27 

#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

28

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

29

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 :pray::pray::pray::pray::pray::pray:

30

Cout<<low
Will be final ans

31

My solution using dp:
https://www.codechef.com/viewsolution/57357986

33

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

34

Awesome approach & explaination.

1 Like
35

Can someone help me to add link my solution here.
I’m facing problems.

37

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.