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