PREZ-Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

Author: Soumyadeep Pal
Tester: Takuki Kurokawa
Editorialist: Daanish Mahajan

DIFFICULTY:

Easy

PREREQUISITES:

Greedy, Binary Search

PROBLEM:

You are given a string S of length N, which consists of digits from 0 to 9. You can apply the following operation O(L) to the string:

  • Choose an integer L with 1\le L \le N and apply S_i = (S_i + 1) \bmod 10 for each 1 \le i \le L.

Find the length of the longest good prefix that can be obtained in string S by applying the given operation maximum K times where a good prefix is defined as a prefix having all characters equal to '0'.

EXPLANATION:

Hint 1

The order of operations doesn’t matter.

Solution

Since we are only concerned with the final string, the order of operations doesn’t matter.
Suppose operations used are O(L_1), O(L_2), \ldots, O(L_K), it’s easy to visualize the operations being executed in increasing order of L_i.
Let F_i denote the number of times index s[i] is incremented under modulo 10. Assume the string is 1 indexed.
It’s easy to see that F is a decreasing array with F_0 = K.
Now we iterate over the string starting from index 0 and at each point (suppose index i) we try to use maximum (\le F_{i - 1}) operations to make s[i] = '0' and if its not possible to do so, we can simply break the loop.

Finding maximum operations that can be used at a particular index i

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

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

It’s true because after we convert s[i] = '0', we can use 10 \cdot r operations to reach the same spot.

ALTERNATE SOLUTION:

What's the technique that's maximum used in minimization/maximization problems?

The binary search solution is somewhat similar but in that case, we iterate in decreasing order of index and for a particular value of mid, we check whether the prefix of length mid can be made all '0' using at most K operations.
Check the tester’s code for reference.

COMPLEXITY ANALYSIS:

\mathcal {O}(N) or \mathcal {O}(N \log_2 N) depending on implementation.

SOLUTIONS:

Setter's Solution

#include<bits/stdc++.h>
using namespace std;

int main() {
ios_base :: sync_with_stdio(0);
cin.tie(0);
int t; cin >> t;
while (t–) {
int n, k; cin >> n >> k;
string s; cin >> s;
for (int i = 0; i < n; i++) {
int req = s[i] - ‘0’;
if (req + k < 10) break;
k = 10 - req + ((k - 10 + req) / 10) * 10;
s[i] = ‘0’;
}
int ans = 0;
for (int i = 0; i < n; i++) {
if (s[i] != ‘0’) break;
ans++;
}
cout << ans << ‘\n’;
}
return 0;
}

Tester's Solution
#include <bits/stdc++.h>
using namespace std;

int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        int low = 0;
        int high = n + 1;
        while (high - low > 1) {
            int mid = (high + low) >> 1;
            int cnt = 0;
            for (int i = mid - 1; i >= 0; i--) {
                int now = (cnt + s[i] - '0') % 10;
                if (now != 0) {
                    cnt += 10 - now;
                }
            }
            if (cnt <= k) {
                low = mid;
            } else {
                high = mid;
            }
        }
        cout << low << '\n';
    }
    return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define F first
#define S second
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); 
	int t; cin >> t;
	int n, k;
	string s;
	while(t--){
		cin >> n >> k;
		cin >> s;
		int id = 0, ans = 0;
		while(id < n){
			int required = (10 - (s[id] - '0')) % 10;
			if(required > k)break;
			ans++;
			id++;
			k = ((k - required) / 10) * 10 + required;
		}
		cout << ans << endl;
	}
	return 0;
}
8 Likes

Can prefix arrays be used to solve this?
I implemented it using the same and it worked for the samples, sadly didn’t get AC :confused:

2 Likes

Great and nice solution , this technique is generally called as "Binary Search on Answer / Answer on Binary Search "

Here are some few problems on this technique , can try (easy to hard), also if any other problems please share -

37 Likes

Thanks man

It’s easy to see that F is a decreasing array with F0=K

How??

3 Likes

the same approach but got the wrong answer .can any1 explain what wrong and which test cases is going wrong
Link: Solution: 57354930 | CodeChef

Damn Your rating graph is as sick as i was in cobid :cold_face:

1 Like

For any integer L with 1≤ L ≤ N we apply Si=(Si+1)%10 for each 1≤ i ≤ L.
The left-most element is incremented the most number of times as wherever the operation was performed, the index 1 is always affected. If L >= 2 then the 2nd value is always incremented. Basically, the lower indices are always incremented and the higher ones are not for any L. The order of operations is what causes this statement to be obvious.

5 Likes

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;
}}

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

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: Solution: 57317947 | CodeChef

7 Likes

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

1 Like

8 25
37159725

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

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

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

2 Likes

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

could you please share some edge testcases it may help…

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

why WA??

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 .

2 Likes

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";
    }
    
}