# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

* Author:* Soumyadeep Pal

*Takuki Kurokawa*

**Tester:***Daanish Mahajan*

**Editorialist:**# 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;
}
```