Problème : Soit \\(n\\) bombes, la \\(i\\)-ème ayant une position \\(pos\_i\\) et un état \\(state\_i\\) (0 pour non activé, 1 pour activé). On dispose de \\(m\\) opérations ; la \\(i\\)-ème opération inverse l'état de toutes les bombes situées entre \\(l\_i\\) et \\(r\_i\\). Déterminer s'il est possible de rendre toutes les bombes non activées via une séquence d'opérations. Si impossible, afficher -1 ; sinon, afficher le nombre d'opérations utilisées, puis ces opérations triées par numéro croissant.

Solution : L'idée principale est de convertir les modifications d'intervalles en modifications ponctuelles. On trie d'abord les bombes par position, puis on définit une séquence de différences \\(d_i = state_i \oplus state_{i-1}\\) pour \\(i \ge 1\\), avec \\(state_0 = 0\\). Ainsi, inverser l'état des bombes dans un intervalle \\([l, r]\\) correspond à inverser uniquement \\(d_l\\) et \\(d_{r+1}\\). Le problème revient alors à rendre tous les éléments de \\(d\\) à zéro avec des opérations qui inversent deux éléments à la fois.

On construit un graphe où chaque nœud représente un élément de \\(d\\), et chaque opération correspond à une arête entre les deux indices affectés. Une solution existe si chaque composante connexe contient un nombre pair de \\(1\\). Pour trouver les arêtes nécessaires, on effectue un parcours en profondeur sur chaque composante : lorsqu'un nœud \\(v\\) a un nombre impair de \\(1\\) dans son sous-arbre, on inclut l'arête entre \\(u\\) et \\(v\\) dans la solution. Enfin, on trie les arêtes sélectionnées par identifiant.

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

const int LIMITE = 200005;

struct Element {
    int position, etat;
};

std::vector<int> resultat;
int difference[LIMITE];
bool visite[LIMITE];
std::vector<std::pair<int, int>> aretes[LIMITE];

void parcours(int noeud) {
    visite[noeud] = true;
    for (auto voisin : aretes[noeud]) {
        int dest = voisin.first;
        int id = voisin.second;
        if (visite[dest]) continue;
        parcours(dest);
        if (difference[dest] == 1) {
            difference[noeud] = (difference[noeud] + 1) % 2;
            resultat.push_back(id);
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;

    Element tableau[LIMITE];
    for (int i = 1; i <= n; ++i) {
        std::cin >> tableau[i].position >> tableau[i].etat;
    }

    std::sort(tableau + 1, tableau + n + 1, [](const Element& a, const Element& b) {
        return a.position < b.position;
    });

    for (int i = 1; i <= n + 1; ++i) {
        int etatActuel = (i <= n) ? tableau[i].etat : 0;
        int etatPrecedent = (i > 1) ? tableau[i-1].etat : 0;
        difference[i] = etatActuel ^ etatPrecedent;
    }

    int positions[LIMITE];
    for (int i = 1; i <= n; ++i) {
        positions[i] = tableau[i].position;
    }

    for (int op = 1; op <= m; ++op) {
        int gauche, droite;
        std::cin >> gauche >> droite;
        int debut = std::lower_bound(positions + 1, positions + n + 1, gauche) - positions;
        int fin = std::upper_bound(positions + 1, positions + n + 1, droite) - positions;
        if (debut < fin) {
            aretes[debut].push_back({fin, op});
            aretes[fin].push_back({debut, op});
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (!visite[i]) {
            parcours(i);
            if (difference[i] == 1) {
                std::cout << -1 << "\n";
                return 0;
            }
        }
    }

    std::sort(resultat.begin(), resultat.end());
    std::cout << resultat.size() << "\n";
    for (int id : resultat) {
        std::cout << id << " ";
    }
    std::cout << "\n";

    return 0;
}

Problème : Sur un plan cartésien, partant de l'origine \\((0, 0)\\), on peut se déplacer d'une unité vers la droite ou vers le haut à chaque pas. Soit \\(f(r, c)\\) le nombre de chemins vers \\((r, c)\\). Calculer la somme

\[\sum_{r=r_1}^{r_2} \sum_{c=c_1}^{c_2} f(r, c).\]

Solution : On observe que \\(f(r, c+1) = \sum_{i=0}^{r} f(i, c)\\). Par récurrence, on démontre que la somme cumulative

\[\sum_{i=0}^{r} \sum_{j=0}^{c} f(i, j) = f(r+1, c+1) - 1.\]

Le problème se réduit donc à calculer des valeurs de \\(f(r, c)\\), qui représentent des coefficients binomiaux : \\(f(r, c) = \binom{r+c}{r}\\). On utilise la formule combinatoire avec des factorielles modulo \\(10^9 + 7\\), et on applique l'inclusion-exclusion pour la somme sur le rectangle.

#include <iostream>
#include <vector>

const int MOD = 1000000007;
const int MAX_TAILLE = 2000005;

long long factoriel[MAX_TAILLE];

long long puissanceModulaire(long long base, long long exposant) {
    long long resultat = 1;
    while (exposant > 0) {
        if (exposant % 2 == 1) {
            resultat = resultat * base % MOD;
        }
        base = base * base % MOD;
        exposant /= 2;
    }
    return resultat;
}

long long inverseModulaire(long long x) {
    return puissanceModulaire(x, MOD - 2);
}

long long coefficientBinomial(int r, int c) {
    int numerateur = r + c + 2;
    int denominateur = r + 1;
    return factoriel[numerateur] * inverseModulaire(factoriel[denominateur]) % MOD
           * inverseModulaire(factoriel[c + 1]) % MOD;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int r1, c1, r2, c2;
    std::cin >> r1 >> c1 >> r2 >> c2;

    factoriel[0] = 1;
    for (int i = 1; i <= r2 + c2 + 2; ++i) {
        factoriel[i] = factoriel[i-1] * i % MOD;
    }

    long long sol = (coefficientBinomial(r2, c2)
                     - coefficientBinomial(r1-1, c2)
                     - coefficientBinomial(r2, c1-1)
                     + coefficientBinomial(r1-1, c1-1)) % MOD;
    if (sol < 0) sol += MOD;

    std::cout << sol << "\n";
    return 0;
}

Problème : Sur une grille de \\(h+1\\) lignes et \\(w\\) colonnes, on commence à la ligne 1 (n'importe quelle colonne) et on se déplace vers le bas ou vers la droite d'une case. Pour la \\(i\\)-ème ligne, il est interdit de descendre dans les colonnes de \\(l_i\\) à \\(r_i\\). Pour chaque \\(k \\in [2, h+1]\\), afficher le nombre minimal de pas pour atteindre la \\(k\\)-ème ligne, ou -1 si impossible.

Solution : On traite la grille ligne par ligne. Soit \\(a_j\\) le nombre minimal de pas pour atteindre la colonne \\(j\\) de la ligne courante. Lors de la transition vers la ligne suivante, pour les colonnes où la descente est permise, \\(a_j\\) reste inchangé. Pour les colonnes où la descente est interdite (intervalle \\([l_i, r_i]\\)), on doit reporter la valeur à la colonne \\(r_i+1\\) par un mouvement vers la droite.

Formellement, on met à jour : \\(a_{r_i+1} = \min_{j=l_i}^{r_i+1} (a_j + r_i+1 - j)\\), puis on invalide \\(a_j\\) pour \\(j \\in [l_i, r_i]\\) en les mettant à une valeur infinie. On utilise deux arbres de segments : l'un pour les valeurs \\(a_j\\), l'autre pour \\(a_j - j\\) afin de calculer efficacement le minimum sur un intervalle.

#include <iostream>
#include <algorithm>
#include <climits>

const int MAX = 200005;
const long long INFINI = 1e18;

long long arbreValeurs[4 * MAX];
long long arbreDecales[4 * MAX];
long long etiquettes[4 * MAX];

void propagation(int noeud, int gauche, int droite) {
    if (etiquettes[noeud] != INFINI) {
        int milieu = (gauche + droite) / 2;
        arbreValeurs[2 * noeud] = etiquettes[noeud];
        arbreDecales[2 * noeud] = etiquettes[noeud] - milieu;
        etiquettes[2 * noeud] = etiquettes[noeud];
        arbreValeurs[2 * noeud + 1] = etiquettes[noeud];
        arbreDecales[2 * noeud + 1] = etiquettes[noeud] - droite;
        etiquettes[2 * noeud + 1] = etiquettes[noeud];
        etiquettes[noeud] = INFINI;
    }
}

void mettreAJour(int noeud, int gauche, int droite, int debut, int fin, long long valeur) {
    if (debut > droite || fin < gauche) return;
    if (debut <= gauche && droite <= fin) {
        arbreValeurs[noeud] = valeur;
        arbreDecales[noeud] = valeur - droite;
        etiquettes[noeud] = valeur;
        return;
    }
    propagation(noeud, gauche, droite);
    int milieu = (gauche + droite) / 2;
    mettreAJour(2 * noeud, gauche, milieu, debut, fin, valeur);
    mettreAJour(2 * noeud + 1, milieu + 1, droite, debut, fin, valeur);
    arbreValeurs[noeud] = std::min(arbreValeurs[2 * noeud], arbreValeurs[2 * noeud + 1]);
    arbreDecales[noeud] = std::min(arbreDecales[2 * noeud], arbreDecales[2 * noeud + 1]);
}

long long interroger(int noeud, int gauche, int droite, int debut, int fin, bool decalage) {
    if (debut > droite || fin < gauche) return INFINI;
    if (debut <= gauche && droite <= fin) {
        return decalage ? arbreDecales[noeud] : arbreValeurs[noeud];
    }
    propagation(noeud, gauche, droite);
    int milieu = (gauche + droite) / 2;
    long long gaucheMin = interroger(2 * noeud, gauche, milieu, debut, fin, decalage);
    long long droiteMin = interroger(2 * noeud + 1, milieu + 1, droite, debut, fin, decalage);
    return std::min(gaucheMin, droiteMin);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int h, w;
    std::cin >> h >> w;

    for (int i = 1; i <= 4 * w; ++i) {
        etiquettes[i] = INFINI;
    }

    for (int ligne = 1; ligne <= h; ++ligne) {
        int l, r;
        std::cin >> l >> r;

        if (r < w) {
            long long minDecale = interroger(1, 1, w, l, r + 1, true);
            mettreAJour(1, 1, w, r + 1, r + 1, minDecale + r + 1);
        }
        mettreAJour(1, 1, w, l, r, INFINI);

        long long reponse = arbreValeurs[1];
        if (reponse > 1e9) {
            std::cout << -1 << "\n";
        } else {
            std::cout << reponse + ligne << "\n";
        }
    }

    return 0;
}

Problème : Problème interactif. On a un tableau inconnu \\(a\\) de taille \\(n\\). À chaque requête, on envoie \\(k\\) indices distincts, et l'interacteur renvoie le xor des éléments correspondants. Déterminer le xor de tous les éléments du tableau avec un minimum de requêtes.

Solution : On modélise le problème comme un processus d'obtention d'informations sur les éléments. Soit \\(d_i\\) le nombre minimal de requêtes pour connaître le xor de \\(i\\) éléments. On effectue un BFS sur les états \\(i\\) de 0 à \\(n\\), où une transition de \\(u\\) à \\(v = u + k - 2i\\) (avec \\(i\\) éléments inconnus choisis) correspond à une requête. Ensuite, on retrace le chemin depuis \\(n\\) jusqu'à 0 pour planifier les requêtes : à chaque étape, on sélectionne \\(i\\) éléments inconnus et \\(k-i\\) éléments connus.

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

const int MAX_N = 505;

int distance[MAX_N];
int parent[MAX_N];

int demander(const std::vector<int>& indices) {
    std::cout << "?";
    for (int idx : indices) {
        std::cout << " " << idx;
    }
    std::cout << std::endl;
    int reponse;
    std::cin >> reponse;
    return reponse;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, k;
    std::cin >> n >> k;

    for (int i = 0; i <= n; ++i) {
        distance[i] = -1;
    }

    std::queue<int> file;
    distance[0] = 0;
    file.push(0);

    while (!file.empty()) {
        int u = file.front();
        file.pop();
        for (int i = std::max(0, k + u - n); i <= std::min(k, u); ++i) {
            int v = u + k - 2 * i;
            if (distance[v] == -1) {
                distance[v] = distance[u] + 1;
                parent[v] = u;
                file.push(v);
            }
        }
    }

    if (distance[n] == -1) {
        std::cout << -1 << std::endl;
        return 0;
    }

    std::vector<int> chemin;
    int courant = n;
    while (courant != 0) {
        chemin.push_back(courant);
        courant = parent[courant];
    }
    chemin.push_back(0);
    std::reverse(chemin.begin(), chemin.end());

    std::vector<int> connus, inconnus;
    for (int i = 1; i <= n; ++i) {
        inconnus.push_back(i);
    }

    int xorTotal = 0;
    for (size_t i = 1; i < chemin.size(); ++i) {
        int delta = chemin[i] - chemin[i-1];
        int nbInconnus = (k + delta) / 2;
        int nbConnus = k - nbInconnus;

        std::vector<int> requete;
        for (int j = 0; j < nbInconnus; ++j) {
            requete.push_back(inconnus.back());
            connus.push_back(inconnus.back());
            inconnus.pop_back();
        }
        for (int j = 0; j < nbConnus; ++j) {
            requete.push_back(connus.back());
            inconnus.push_back(connus.back());
            connus.pop_back();
        }

        xorTotal ^= demander(requete);
    }

    std::cout << "! " << xorTotal << std::endl;
    return 0;
}

Problème : Soit \\(n\\) articles avec des prix \\(a_i\\) et une séquence \\(c_1, c_2, \ldots, c_n\\). On doit acheter \\(m\\) articles spécifiés. Lors de l'achat d'un article \\(i\\), s'il est le \\(j\\)-ème article non encore acheté, le coût est \\(a_i + c_j\\). On peut acheter des articles supplémentaires. Trouver le coût minimal total pour acquérir les \\(m\\) articles.

Solution : On utilise la programmation dynamique. Soit \\(dp_{i,j}\\) le coût minimal pour acheter \\(j\\) articles parmi les \\(i\\) premiers. Pour l'article \\(i\\), si on l'achète, son coût dépend de combien d'articles précédents ont été achetés. On maintient une table de minimums pour \\(c_k\\) sur des intervalles. La transition est :

\[ dp_{i,j} = \min \left( dp_{i-1,j},\ dp_{i-1,j-1} + a_i + \min_{k=i-(j-1)}^{i} c_k \right). \]

On initialise \\(dp_{0,0} = 0\\) et les autres à l'infini. La réponse est le minimum sur \\(dp_{n,j}\\) pour \\(j \\ge m\\).

#include <iostream>
#include <algorithm>
#include <climits>

const int MAX = 5005;
const long long INFINI = 1e18;

long long a[MAX], c[MAX];
long long minimums[MAX][MAX];
long long dp[MAX][MAX];
bool obligatoire[MAX];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
    }
    for (int i = 1; i <= n; ++i) {
        std::cin >> c[i];
    }

    for (int i = 1; i <= n; ++i) {
        int idx;
        std::cin >> idx;
        obligatoire[idx] = true;
    }

    for (int i = 1; i <= n; ++i) {
        minimums[i][i] = c[i];
        for (int j = i + 1; j <= n; ++j) {
            minimums[i][j] = std::min(minimums[i][j-1], c[j]);
        }
    }

    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            dp[i][j] = INFINI;
        }
    }
    dp[0][0] = 0;

    for (int i = 1; i <= n; ++i) {
        if (!obligatoire[i]) {
            for (int j = 0; j <= i; ++j) {
                dp[i][j] = std::min(dp[i][j], dp[i-1][j]);
            }
        }
        for (int j = 1; j <= i; ++j) {
            if (dp[i-1][j-1] != INFINI) {
                long long cout = dp[i-1][j-1] + a[i] + minimums[i-(j-1)][i];
                dp[i][j] = std::min(dp[i][j], cout);
            }
        }
    }

    long long reponse = INFINI;
    for (int j = m; j <= n; ++j) {
        reponse = std::min(reponse, dp[n][j]);
    }

    std::cout << reponse << "\n";
    return 0;
}