PREZ-Editorial

[aa6245]

My greedy approach is also same. But still I am getting WA.
It will be much grateful if u could plzz point out where am I going wrong in it???!

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
int const N=1e5;

//PRE POST IN & LEVEL ORDER TRANSVERSAL IN BT

int main(){
#ifndef ONLINE_JUDGE
freopen(“INPUT.txt”,“r”,stdin);
freopen(“SHI HI HOGA YR.txt”,“w”,stdout);
#endif

int t;
cin>>t;
while(t–){
ll n, k,ans=0;
string s;
cin>>n>>k>>s;
for(auto &x:s){
if(x==‘0’)ans++;
else if((x-‘0’)+k>=10){
k-=10-(x-‘0’);
ans++;
}
else{
break;
}
}
int temp=ans;
for(int i=temp; i<n; i++){
if(s[i]==‘0’)ans++;
else break;
}
cout<<ans<<endl;
}}

[i_am_bad]

Deleted post since I found my mistake in the implementation : D

[blood_eagle123]

It can be solved using a prefix array.
We will iterate the array and store the number of moves required to convert the (i-1)th element to (i)th element. For the 0th element, it will be 0.
Example: 78712
For i = 0 : 0 steps(First element)
For i = 1 : 1 steps(7->8)
For i = 2 : 9 steps(8->7)
For i = 3 : 4 steps(7->1)
For i = 4 : 1 steps(1->2)
We can store this in a vector in the form {moves_required, i th element}.
{0, 7}, {0 + 1, 8},{0+1+9, 7},{0+1+9+4, 1},{0+1+9+4+1, 2}.
Then iterate over the vector and check if
moves_required + (10-ith element)%10 <=k

My Solution: CodeChef: Practical coding for everyone

[i_am_bad]

Thanks
I tried doing the same but ended up implementing it in the wrong way

[jjjjjj]

8 25
37159725

Our F array looks something look like
25 23 19 15 11 3
its answer will be 6 not 5

[arpit92_8]

@daanish_adm

Since we are only concerned with the final string, the order of operations doesn’t matter.

Here I cannot understand the term ‘order’. From where this ‘order’ is coming from?

[jjjjjj]

performing operation Si then Sj or Sj then Si results in same sequence

[me_v21]

right?? that’s a hell of a graph. my man came from 5*

[anon51588836]

could you please share some edge testcases it may help…

[anon51588836]

https://www.codechef.com/viewsolution/57392529

why WA??

[anon29522813]

var1 as the minimum number of operations required to convert s[i] =s[i]= '0',
var2 as the maximum multiple of 1010 \le (F_{i - 1} -≤(Fi−1​− var1).

var1 = (10 - (s[i] - '0')) % 10
var2 = ((F_{i - 1} - var1) / 10) * 10
So F_{i} = var1 + var2

Anyone please explain this , i m confused in this .

[ch_harsha1]

Can anyone tell me what is wrong with this solution?

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        string s;
        cin>>s;
        int cnt=0;
        for(int i=0;i<s.length();i++)
        {
            char ch =s[i];
            int x = ch-'0';
            if(x==0)
            {
                cnt++;
                continue;
            }
            else if(10-x>k)
            {
                break;
            }
            else
            {
                k = k-(10-x);
                cnt++;
            }
        }
        cout<<cnt<<"\n";
    }
    
}

[arpit92_8]

@daanish_adm

var1 as the minimum number of operations required to convert s[i]=s[i] =s[i]= '0',
var2 as the maximum multiple of 10 ≤(Fi−1−\le (F_{i - 1} -≤(Fi−1​− var1).

var1 = (10 - (s[i] - '0')) % 10
var2 = ((F_{i - 1} - var1) / 10) * 10
So F_{i} = var1 + var2

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

[rahat_mohammad]

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

[supernova69]

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

[rraj0511]

#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

[rahul_mallick]

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

[prnvkp]

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

[azadk]

Cout<<low
Will be final ans

[shark25361]

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