Problème A : Validation de sous-chaîne de mot de passe

L'énoncé demande s'il est possible de modifier un mot de passe de longueur $m$ pour qu'il devienne une sous-chaîne d'une chaîne cible de longueur $n$. Puisque nous pouvons modifier n'importe quel caractère du mot de passe (sans changer sa longueur), la seule contrainte réelle est la dimension. Si $m \le n$, nous pouvons simplement extraire n'importe quel segment de longueur $m$ de la chaîne cible. Dans le cas contraire, c'est impossible.

void resolve_problem_a() {
    int target_len, pwd_len;
    std::cin >> target_len >> pwd_len;
    std::string source;
    std::cin >> source;

    if (pwd_len > target_len) {
        std::cout << -1 << std::endl;
    } else {
        // On retourne simplement le premier préfixe valide
        std::cout << source.substr(0, pwd_len) << std::endl;
    }
}

Problème B : Optimisation du trajet entre les îles

L'objectif est d'atteindre l'île $s$ à partir de l'île $1$ avec un minimum d'opérations sur $n$ îles au total. Nous devons comparer le coût d'un déplacement linéaire direct avec des stratégies impliquant l'opération de saut (opération 3).

La stratégie optimale consiste à évaluer le coût d'aller directement à $s$ ($s-1$ étapes) par rapport à l'utilisation du saut vers les multiples les plus proches. En calculant $t = n/s$, on peut tester les positions $n/t$ et $n/(t+1)$ pour minimiser la distance totale.

void resolve_problem_b() {
    long long total_islands, target;
    std::cin >> total_islands >> target;
    
    long long min_ops = target - 1;
    long long factor = total_islands / target;

    if (factor * target == total_islands) {
        min_ops = std::min(min_ops, factor);
    } else {
        long long lower_bound = total_islands / (factor + 1);
        long long upper_bound = total_islands / factor;
        
        min_ops = std::min(min_ops, factor + 1 + (target - lower_bound));
        min_ops = std::min(min_ops, factor + (upper_bound - target));
    }
    std::cout << min_ops << std::endl;
}

Problème C : Reconstruction de séquence par MEX

Ce problème de construction demande d'atteindre une séquence cible en remplaçant des éléments par le MEX (Minimum Excluded value) de l'ensemble actuel. Une observation clé est que si la cible contient des doublons (autres que 0), la construction est impossible car chaque opération MEX génère une valeur unique non présente auparavant.

La méthode de résolution consiste à travailler à l'envers. On identifie la valeur maximale et on vérifie combien d'éléments manquent entre 0 et cette valeur. Si plus d'un élément manque, la transition est impossible. On simule le processus en réduisant progressivement les valeurs vers zéro et on affiche les opérations en ordre inverse.

int find_missing_val(int n, int current_max, const std::vector<int>& vec) {
    std::vector<bool> present(current_max + 1, false);
    for (int i = 0; i < n; ++i) {
        if (vec[i] <= current_max) present[vec[i]] = true;
    }
    for (int i = 0; i <= current_max; ++i) {
        if (!present[i]) return i;
    }
    return -1;
}

void resolve_problem_c() {
    int n;
    std::cin >> n;
    std::vector<int> target(n);
    for (int i = 0; i < n; ++i) std::cin >> target[i];

    // Vérification des doublons non-nuls
    std::vector<int> sorted_t = target;
    std::sort(sorted_t.begin(), sorted_t.end());
    for (int i = 0; i < n - 1; ++i) {
        if (sorted_t[i] != 0 && sorted_t[i] == sorted_t[i+1]) {
            std::cout << -1 << std::endl;
            return;
        }
    }

    std::vector<int> sequence;
    while (true) {
        bool all_zero = true;
        int max_val = -1, pos = -1;
        for (int i = 0; i < n; ++i) {
            if (target[i] > 0) all_zero = false;
            if (target[i] > max_val) {
                max_val = target[i];
                pos = i;
            }
        }
        if (all_zero) break;

        int missing = find_missing_val(n, max_val, target);
        if (missing == -1) {
            target[pos] = 0;
        } else {
            target[pos] = missing;
        }
        sequence.push_back(pos + 1);
    }

    std::cout << sequence.size() << std::endl;
    for (int i = sequence.size() - 1; i >= 0; --i) {
        std::cout << sequence[i] << (i == 0 ? "" : " ");
    }
    std::cout << std::endl;
}

Problème E : Arbre de segments et gestion de parité via Masques de bits

Pour gérer les rotations de caractères (a -> b -> c...) sur des plages et vérifier si une réorgenisation en palindrome est possible, on utilise un arbre de segments. Le critère pour qu'une chaîne soit une permutation de palindrome est qu'au plus un caractère apparaisse un nombre impair de fois.

On stocke l'état de parité des 26 lettres dans un entier de 32 bits (bitmask). L'opération de décalage circulaire est gérée par une fonction de transformation de bitmask et une propagation paresseuse (lazy propagation) dans l'arbre.

struct Node {
    int l, r, lazy;
    int bitmask;
} tree[400005];

int rotate_mask(int mask, int shift) {
    shift %= 26;
    if (shift == 0) return mask;
    int next_mask = 0;
    for (int i = 0; i < 26; ++i) {
        if ((mask >> i) & 1) {
            next_mask |= (1 << ((i + shift) % 26));
        }
    }
    return next_mask;
}

void push_up(int u) {
    tree[u].bitmask = tree[u << 1].bitmask ^ tree[u << 1 | 1].bitmask;
}

void push_down(int u) {
    if (tree[u].lazy % 26 != 0) {
        int s = tree[u].lazy;
        tree[u << 1].bitmask = rotate_mask(tree[u << 1].bitmask, s);
        tree[u << 1 | 1].bitmask = rotate_mask(tree[u << 1 | 1].bitmask, s);
        tree[u << 1].lazy += s;
        tree[u << 1 | 1].lazy += s;
        tree[u].lazy = 0;
    }
}

void build_tree(int u, int l, int r, const std::string& s) {
    tree[u] = {l, r, 0, 0};
    if (l == r) {
        tree[u].bitmask = (1 << (s[l-1] - 'a'));
        return;
    }
    int mid = (l + r) >> 1;
    build_tree(u << 1, l, mid, s);
    build_tree(u << 1 | 1, mid + 1, r, s);
    push_up(u);
}

void update_range(int u, int l, int r, int k) {
    if (tree[u].l >= l && tree[u].r <= r) {
        tree[u].bitmask = rotate_mask(tree[u].bitmask, k);
        tree[u].lazy += k;
        return;
    }
    push_down(u);
    int mid = (tree[u].l + tree[u].r) >> 1;
    if (l <= mid) update_range(u << 1, l, r, k);
    if (r > mid) update_range(u << 1 | 1, l, r, k);
    push_up(u);
}

int query_mask(int u, int l, int r) {
    if (tree[u].l >= l && tree[u].r <= r) return tree[u].bitmask;
    push_down(u);
    int mid = (tree[u].l + tree[u].r) >> 1;
    int res = 0;
    if (l <= mid) res ^= query_mask(u << 1, l, r);
    if (r > mid) res ^= query_mask(u << 1 | 1, l, r);
    return res;
}

void solve_segment_tree() {
    int n, q;
    std::cin >> n >> q;
    std::string s;
    std::cin >> s;
    build_tree(1, 1, n, s);
    while (q--) {
        int type, l, r;
        std::cin >> type >> l >> r;
        if (type == 1) {
            int k; std::cin >> k;
            update_range(1, l, r, k);
        } else {
            int final_mask = query_mask(1, l, r);
            if (__builtin_popcount(final_mask) <= 1) std::cout << "Yes" << std::endl;
            else std::cout << "No" << std::endl;
        }
    }
}