Score
Problem Statement Summary Given a decimal number as a string of N digits and a budget of K adjacent swaps, find the maximum and minimum numbers obtainable. Leading zeros are not permitted (except for the number 0 itse...
Problem Statement
No standalone statement file is available for this entry.
A separate statement file is not available for this entry, so the page focuses on the editorial and implementation.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Problem Statement Summary
Given a decimal number as a string of $N$ digits and a budget of $K$ adjacent swaps, find the maximum and minimum numbers obtainable. Leading zeros are not permitted (except for the number 0 itself).
Solution: Greedy Selection Sort
Maximizing
Process positions left to right. At position $i$, locate the largest digit in the range $[i, \min(i+K, N-1)]$ (breaking ties by choosing the leftmost occurrence to minimize swaps). Bubble it to position $i$ by swapping with its left neighbor repeatedly, deducting the number of swaps used from $K$.
Lemma.
The greedy strategy is optimal for maximization.
Proof.
At each step we place the largest reachable digit into the leftmost unfilled position. Any other choice yields a lexicographically smaller result, because the first position where the two results differ will have a smaller digit in the non-greedy solution.
Minimizing
The same strategy applies, but we select the smallest digit. For position 0, we skip digit `0' to avoid leading zeros---we select the smallest non-zero digit reachable within $K$ swaps.
Edge Case
If the string is all zeros (representing the number 0), no leading-zero avoidance is needed.
C++ Implementation
#include <bits/stdc++.h>
using namespace std;
string maximize(string s, int K) {
int n = s.size();
for (int i = 0; i < n - 1 && K > 0; i++) {
int bestPos = i;
for (int j = i + 1; j < n && j - i <= K; j++)
if (s[j] > s[bestPos])
bestPos = j;
for (int j = bestPos; j > i; j--) {
swap(s[j], s[j - 1]);
K--;
}
}
return s;
}
string minimize(string s, int K) {
int n = s.size();
for (int i = 0; i < n - 1 && K > 0; i++) {
int bestPos = i;
for (int j = i + 1; j < n && j - i <= K; j++) {
if (i == 0) {
// Avoid leading zero
if (s[j] == '0') continue;
if (s[bestPos] == '0' || s[j] < s[bestPos])
bestPos = j;
} else {
if (s[j] < s[bestPos])
bestPos = j;
}
}
// If all reachable digits for position 0 are '0', skip
if (i == 0 && s[bestPos] == '0') continue;
for (int j = bestPos; j > i; j--) {
swap(s[j], s[j - 1]);
K--;
}
}
return s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string S;
int K;
cin >> S >> K;
cout << minimize(S, K) << "\n";
cout << maximize(S, K) << "\n";
return 0;
}Complexity Analysis
Time: $O(N \cdot \min(N, K))$. For each of $N$ positions, we scan at most $\min(K, N)$ positions ahead. The total number of swaps across all iterations is at most $K$.
Space: $O(N)$.
Code
C++ solution used for this page.
// IOI 2001 - Score
// Given a decimal number string and K allowed adjacent swaps,
// find the maximum and minimum achievable numbers.
// Greedy: for each position, find best digit within swap range and bubble it in.
// Minimizing avoids leading zeros.
// Complexity: O(N * min(N, K)) time, O(N) space.
#include <bits/stdc++.h>
using namespace std;
string maximize(string s, int K) {
int n = (int)s.size();
for (int i = 0; i < n - 1 && K > 0; i++) {
// Find position of the maximum digit in s[i..min(i+K, n-1)]
int bestPos = i;
for (int j = i + 1; j < n && j - i <= K; j++) {
if (s[j] > s[bestPos]) {
bestPos = j;
}
}
// Bubble s[bestPos] to position i
for (int j = bestPos; j > i; j--) {
swap(s[j], s[j - 1]);
K--;
}
}
return s;
}
string minimize(string s, int K) {
int n = (int)s.size();
for (int i = 0; i < n - 1 && K > 0; i++) {
int bestPos = i;
for (int j = i + 1; j < n && j - i <= K; j++) {
if (i == 0) {
// Avoid leading zero: skip '0' candidates for first position
if (s[j] == '0') continue;
if (s[j] < s[bestPos] || s[bestPos] == '0') {
bestPos = j;
}
} else {
if (s[j] < s[bestPos]) {
bestPos = j;
}
}
}
// Bubble s[bestPos] to position i
for (int j = bestPos; j > i; j--) {
swap(s[j], s[j - 1]);
K--;
}
}
return s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string S;
int K;
cin >> S >> K;
// Edge case: single digit
if (S.size() <= 1) {
cout << S << "\n" << S << "\n";
return 0;
}
string maxResult = maximize(S, K);
string minResult = minimize(S, K);
cout << minResult << "\n";
cout << maxResult << "\n";
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.