Cet article présente une analyse technique détaillée et les solutions algorithmiques pour les problèmes sélectionnés du deuxième entraînement d'été Nowcoder 2021. Nous explorerons des concepts allant de la parité simple à la géométrie tridimensionnelle et à la programmation dynamique avancée.

Problème C : Draw Grids

Ce problème de théorie des jeux se résout par une observation de parité. Dans un graphe de grille, le nombre total d'arêtes déterminera le gagnant si les joueurs agissent de manière à maintenir le graphe non connexe jusqu'au dernier mouvement possible.

Logique : Le résultat dépend de la parité du produit des dimensions de la grille. Si le nombre total de points est pair, le premier joueur dispose d'une stratégie gagnante.

#include <iostream>

int main() {
    int rows, cols;
    if (!(std::cin >> rows >> cols)) return 0;
    // Vérification de la parité du produit des dimensions
    if ((rows * cols) % 2 == 0) {
        std::cout << "YES" << std::endl;
    } else {
        std::cout << "NO" << std::endl;
    }
    return 0;
}

Problème D : Er Ba Game

Il s'agit d'un problème de simulation pure basé sur des règles de comparaison de mains de cartes. La clé réside dans la gestion rigoureuse des priorités (cas spéciaux comme le "2-8", les paires, puis la somme modulo 10).

#include <iostream>
#include <algorithm>

using namespace std;

void resolve_match() {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    if (x1 > y1) swap(x1, y1);
    if (x2 > y2) swap(x2, y2);

    auto is_special = [](int a, int b) { return a == 2 && b == 8; };

    if (is_special(x1, y1) && is_special(x2, y2)) {
        cout << "tie" << endl;
    } else if (is_special(x1, y1)) {
        cout << "first" << endl;
    } else if (is_special(x2, y2)) {
        cout << "second" << endl;
    } else if (x1 == y1 && x2 == y2) {
        if (x1 > x2) cout << "first" << endl;
        else if (x1 < x2) cout << "second" << endl;
        else cout << "tie" << endl;
    } else if (x1 == y1) {
        cout << "first" << endl;
    } else if (x2 == y2) {
        cout << "second" << endl;
    } else {
        int val1 = (x1 + y1) % 10;
        int val2 = (x2 + y2) % 10;
        if (val1 > val2) cout << "first" << endl;
        else if (val1 < val2) cout << "second" << endl;
        else {
            if (y1 > y2) cout << "first" << endl;
            else if (y2 > y1) cout << "second" << endl;
            else cout << "tie" << endl;
        }
    }
}

int main() {
    int cases;
    cin >> cases;
    while (cases--) resolve_match();
    return 0;
}

Problème F : Girlfriend

Ce problème demande de calculer le volume de l'intersection de deux ensembles de points définis par des contraintes de distance. La condition $AP \le k \cdot BP$ définit une sphère (sphère d'Apollonius en 3D).

Approche : 1. Extraire l'équation de la sphère de la forme $(x-x_0)^2 + (y-y_0)^2 + (z-z_0)^2 = R^2$ à partir de la relation de distance donnée. 2. Calculer les rayons $R, r$ et la distance entre les centres $d$. 3. Utiliser la formule du volume d'une calotte sphérique pour l'intersection : $V = \pi h^2 (r - \frac{h}{3})$.

#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

struct Point3D { double x, y, z; };

double get_dist(Point3D a, Point3D b) {
    return sqrt(pow(a.x-b.x, 2) + pow(a.y-b.y, 2) + pow(a.z-b.z, 2));
}

void solve_geometry() {
    Point3D p[5];
    for(int i=1; i<=4; ++i) cin >> p[i].x >> p[i].y >> p[i].z;
    double k1, k2;
    cin >> k1 >> k2;

    auto get_sphere = [](Point3D A, Point3D B, double k) {
        double k2 = k * k;
        double factor = 1.0 - k2;
        double cx = (A.x - k2 * B.x) / factor;
        double cy = (A.y - k2 * B.y) / factor;
        double cz = (A.z - k2 * B.z) / factor;
        double radius = sqrt(pow(cx, 2) + pow(cy, 2) + pow(cz, 2) - 
                        (pow(A.x, 2) + pow(A.y, 2) + pow(A.z, 2) - k2 * (pow(B.x, 2) + pow(B.y, 2) + pow(B.z, 2))) / factor);
        return make_pair(Point3D{cx, cy, cz}, radius);
    };

    auto s1 = get_sphere(p[1], p[2], k1);
    auto s2 = get_sphere(p[3], p[4], k2);

    double d = get_dist(s1.first, s2.first);
    double R = s1.second, r = s2.second;

    if (d >= R + r) cout << fixed << setprecision(3) << 0.000 << endl;
    else if (d <= abs(R - r)) {
        double min_r = min(R, r);
        cout << fixed << setprecision(3) << (4.0/3.0) * M_PI * pow(min_r, 3) << endl;
    } else {
        double h1 = R - (R*R + d*d - r*r) / (2.0 * d);
        double h2 = r - (r*r + d*d - R*R) / (2.0 * d);
        double volume = (M_PI/3.0) * (h1*h1*(3*R - h1) + h2*h2*(3*r - h2));
        cout << fixed << setprecision(3) << volume << endl;
    }
}

Problème G : League of Legends

Le but est de maximiser la somme des intersections de $K$ groupes d'intervalles. Ce problème se résout par programmation dynamique optimisée par une file monotone (monotonic queue).

Stratégie : Après avoir trié les intervalles et éliminé ceux qui sont inclus dans d'autres (car ils peuvent former des groupes individuels), on utilise la DP : $dp[i][j]$ est la valeur maximale en divisant les $j$ premiers interavlles en $i$ groupes.

Problème I : Penguins

Ce problème demande de trouver le chemin le plus court pour deux manchots se déplaçant simultanément sur deux grilles distinctes, l'un effectuant des mouvements miroirs par rapport à l'autre.

Technique : Recherche en largeur (BFS) sur un état quadridimensionnel $(x1, y1, x2, y2)$. Chaque état représente la position des deux manchots.

Problème J : Product of GCDs

On demande de calculer $\prod_{S \subseteq A, |S|=k} \gcd(S) \pmod P$.

Analyse : Au lieu de calculer directement le GCD, on compte combien de sous-ensembles ont un GCD divisible par un certainfacteur premier $p$. Si $m$ éléments sont divisibles par $p^v$, alors il y a $\binom{m}{k}$ sous-ensembles dont le GCD est divisible par $p^v$. L'utilisation du théorème d'Euler (ou petit théorème de Fermat si $P$ est premier) est nécessaire pour gérer les exposants élevés.

#include <iostream>
#include <vector>

using namespace std;

typedef __int128_t int128;

long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (long long)((int128)res * base % mod);
        base = (long long)((int128)base * base % mod);
        exp /= 2;
    }
    return res;
}

// Note: La fonction phi et le calcul des combinaisons sont requis pour l'exposant

Problème K : Stack

À partir d'informations partielles sur la taille d'une pile monotone à certains indices, il faut reconstruire une permutation possible des nombres de $1$ à $n$.

Solution : On construit d'abord un tableau complet des tailles de pile cohérent avec les contraintes. Ensuite, on peut utiliser une approche de type tri topologique ou une structure de données pour assigner les valeurs de manière à respecter la propriété de pile monotone (si size\[i\] > size\[i-1\], l'élément est poussé ; sinon, des éléments sont retirés).