Minimizing a Number by Removing Digits

The goal is to take a high-precision positive integer n (up to 240 digits) and remove s digits such that the remaining digits, in their original order, form the smallest possible integer.

Problem Strategy

A common mistake is to sort the digits and remove largest ones. However, this violates the rule of maintaining the relative order of digits. To achieve the global minimum, we use a greedy approach: in each step, we look for the first occurrence where a digit is greater then the digit immediately following it (a "peak"). Removing this digit reduces the value of the number more effectively than removing any subsequent digit.

If the digits are in non-decreasing order (no peaks found), we simply remove the digit at the end of the string.

Implementation

The following C++ implementation uses string manipulation to handle high-precision integers and iteratively removes digits to find the optimal result.

#include <iostream>
#include <string>

using namespace std;

int main() {
    string sequence;
    int k;
    if (!(cin >> sequence >> k)) return 0;

    int remaining_len = sequence.size();

    for (int i = 0; i < k; ++i) {
        bool removed = false;
        for (int j = 0; j < remaining_len - 1; ++j) {
            // Find the first digit that is larger than the next one
            if (sequence[j] > sequence[j + 1]) {
                for (int m = j; m < remaining_len - 1; ++m) {
                    sequence[m] = sequence[m + 1];
                }
                removed = true;
                break;
            }
        }
        // If no peak was found, the sequence is non-decreasing; remove the last digit
        remaining_len--;
    }

    // Handle leading zeros and output the result
    bool is_leading_zero = true;
    for (int i = 0; i < remaining_len; ++i) {
        if (sequence[i] != '0') is_leading_zero = false;
        if (!is_leading_zero) cout << sequence[i];
    }

    if (is_leading_zero) cout << 0;
    cout << endl;

    return 0;
}

Minimum Swaps for Three-Value Sorting

This problem involves a sequence consisting only of the values 1, 2, and 3. We need to determine the minimum number of swaps required to sort the sequence in ascending order.

Analysis

To solve this efficiently, we first calculate the frequency of each number (1, 2, and 3). This tells us the boundaries of the "target zones" where each number should eventually reside. For example, if there are five '1's, the first five positions in the sorted array are the "1-zone."

The greedy strategy relies on the fact that a swap is most efficient when it fixes two numbers at once (e.g., swapping a 1 located in the 2-zone with a 2 located in the 1-zone). If direct exchanges are not possible, elements must be moved through a cycle of three, wich requires two swaps to fix three positions.

Calculation Logic

1. Count the total number of non-1 values currently sitting in the 1-zone. These must be moved out.
2. Count how many 3s are in the 2-zone.
3. Count how many 2s are in the 3-zone.
4. The minimum swaps required is the number of misplaced elements in the first zone plus the maximum of the misplaced counts in the other two zones.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> data(n);
    int c1 = 0, c2 = 0, c3 = 0;

    for (int i = 0; i < n; ++i) {
        cin >> data[i];
        if (data[i] == 1) c1++;
        else if (data[i] == 2) c2++;
        else if (data[i] == 3) c3++;
    }

    int misplaced_in_zone1 = 0;
    int threes_in_zone2 = 0;
    int twos_in_zone3 = 0;

    // Check Zone 1 (indices 0 to c1-1)
    for (int i = 0; i < c1; ++i) {
        if (data[i] != 1) misplaced_in_zone1++;
    }

    // Check Zone 2 (indices c1 to c1+c2-1)
    for (int i = c1; i < c1 + c2; ++i) {
        if (data[i] == 3) threes_in_zone2++;
    }

    // Check Zone 3 (indices c1+c2 to n-1)
    for (int i = c1 + c2; i < n; ++i) {
        if (data[i] == 2) twos_in_zone3++;
    }

    // The result is the sum of misplaced items in zone 1 
    // and the maximum of direct cross-displaced items in zones 2 and 3.
    cout << misplaced_in_zone1 + max(threes_in_zone2, twos_in_zone3) << endl;

    return 0;
}