Ce document présente des solutions détaillées pour trois problèmes d'algorithmique distincts, issus d'un exercice de compétition.

Problème 1 : Plus court chemin avec points marqués

Étant donné un graphe orienté avec n sommets et m arcs, contenant k points marqués, l'objectif est de trouver la plus courte distance parcourue depuis un pointt de départ s jusqu'à un point d'arrivée t, en visitant tous les points marqués dans un ordre arbitraire.

Approche : Calculer les plus courts chemins entre tous les points marqués (incluant s et t) via l'algorithme de Dijkstra. Par la suite, effectuer un parcours exhaustif (DFS) de tous les ordonnancements possibles des points marqués pour déterminer la séquence minimisant la distance totale.

Point d'attention : Gérer le cas où il n'existe aucun chemin entre certains points marqués et le cas où les distances deivennent infinies.

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

using namespace std;

typedef long long ll;
const ll INF = 1e18;

int main() {
    int n, m, k, start_node, end_node;
    cin >> n >> m >> k >> start_node >> end_node;

    vector<vector<pair<int, ll>>> graph(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        graph[u].emplace_back(v, w);
    }

    vector<int> mandatory_points = {start_node};
    for (int i = 0; i < k; ++i) {
        int pt;
        cin >> pt;
        mandatory_points.push_back(pt);
    }
    mandatory_points.push_back(end_node);
    int total_mandatory = mandatory_points.size();

    // Dijkstra pour calculer les distances entre points obligatoires
    auto dijkstra = [&](int source) -> vector<ll> {
        vector<ll> dist(n + 1, INF);
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
        dist[source] = 0;
        pq.push({0, source});

        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (d != dist[u]) continue;
            for (auto& [v, w] : graph[u]) {
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }
        return dist;
    };

    // Matrice des distances entre points obligatoires
    vector<vector<ll>> dist_between(total_mandatory, vector<ll>(total_mandatory, INF));
    for (int i = 0; i < total_mandatory; ++i) {
        vector<ll> all_dist = dijkstra(mandatory_points[i]);
        for (int j = 0; j < total_mandatory; ++j) {
            dist_between[i][j] = all_dist[mandatory_points[j]];
        }
    }

    // DFS pour essayer tous les ordres (points de 1 à k sont les indices des points marqués dans mandatory_points)
    vector<bool> visited(total_mandatory, false);
    ll best_total = INF;
    bool solution_found = false;

    // Lancer la DFS depuis l'indice 0 (start_node), avec 0 points marqués visités.
    function<void(int, int, ll)> dfs = [&](int current_index, int points_visited, ll current_dist) {
        if (points_visited == k) {
            if (dist_between[current_index][total_mandatory - 1] != INF) {
                ll total = current_dist + dist_between[current_index][total_mandatory - 1];
                if (total < best_total) {
                    best_total = total;
                }
                solution_found = true;
            }
            return;
        }

        for (int i = 1; i <= k; ++i) { // Indices 1 à k sont les points marqués (hors start/end)
            if (!visited[i] && dist_between[current_index][i] != INF) {
                visited[i] = true;
                dfs(i, points_visited + 1, current_dist + dist_between[current_index][i]);
                visited[i] = false;
            }
        }
    };

    dfs(0, 0, 0);

    if (!solution_found) {
        cout << -1 << endl;
    } else {
        cout << best_total << endl;
    }

    return 0;
}

Problème 2 : Maximiser le gain sous contraintes séquentielles

Un jeu consiste en une séquence d'événements de deux types : combat (rapportant un gain) et fin de partie (imposant un nombre minimum de combats effectués jusqu'à ce point). L'objectif est que seul le dernier événement de fin de partie se produise, tout en maximisant le gain total accumulé.

Approche : Parcourir les événements séquentiellement. Pour chaque événement de combat, on l'ajoute à une collection (par exemple, une file de priorité minimale). Lorsqu'un événement de fin de partie est rencontré avec un seuil x, on s'assure d'avoir effectué au moins x combats. Si ce n'est pas le cas, on est forcé de conserver les x combats les plus rentables parmi ceux disponibles, en éliminant les moins profitables si nécessaire. Enfin, pour le dernier événement, on vérifie que le nombre total de combats conservés est suffisant.

Implémentation alternative sans file de priorité explicite : On peut maintenir un compteur de combats et la somme totale, et rétroactivement ajuster la sélection lorsque le seuil est dépassé.

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

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> profits; // Stocke les gains des combats disponibles
    long long total_sum = 0;
    bool possible = true;
    int last_threshold = 0;

    for (int i = 0; i < n; ++i) {
        char type;
        int value;
        cin >> type >> value;

        if (type == 'c') {
            profits.push_back(value);
            total_sum += value;
        } else { // type == 'e'
            if (i == n - 1) {
                // C'est le dernier événement
                last_threshold = value;
            } else {
                // Événement de fin de partie intermédiaire
                // On doit avoir au moins 'value' combats.
                // Si on en a trop, on garde les 'value' meilleurs.
                if (profits.size() > (size_t)value) {
                    sort(profits.begin(), profits.end(), greater<int>());
                    while (profits.size() > (size_t)value) {
                        total_sum -= profits.back();
                        profits.pop_back();
                    }
                }
                // Si profits.size() < value, c'est impossible à satisfaire à ce point
                // Dans ce cas, la solution finale devrait être -1.
                // On continue la simulation pour lire toutes les entrées, mais on marque.
            }
        }
    }

    // Vérification pour le dernier événement
    if (profits.size() < (size_t)last_threshold) {
        possible = false;
    }

    if (!possible) {
        cout << -1 << endl;
    } else {
        // On a les meilleurs combats dans 'profits', on calcule leur somme.
        // Note : la somme avait été mise à jour lors des suppressions.
        cout << total_sum << endl;
    }

    return 0;
}

Problème 3 : Dénombrement de triangles non dégénérés

Étant donné n points dans le plan, déterminer le nombre de triangles (non dégénérés, i.e., d'aire non nulle) pouvant être formés avec ces points comme sommets.

Approche : Le nombre total de triplets est C(n,3). On doit soustraire les triplets de points colinéaires. Pour cela, on peut énumérer chaque point comme référence, calculer les pentes vers tous les autres points et regrouper les points ayent la même pente par rapport au point de référence. Pour chaque groupe de m points colinéaires avec le point de référence, on retire C(m,2) triplets invalides. Il faut veiller à ne pas compter les mêmes lignes plusieurs fois.

Optimisation : Pour éviter de trier les pentes (et les erreurs de virgule flottante), on peut utiliser des fractions de deux entiers (dx, dy) réduites et stockées comme paires.

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>

using namespace std;

typedef long long ll;

struct Point {
    int x, y;
};

// Fonction utilitaire pour calculer le coefficient directeur normalisé sous forme de paire (dx, dy)
pair<int, int> get_slope_pair(const Point& a, const Point& b) {
    int dx = b.x - a.x;
    int dy = b.y - a.y;
    if (dx == 0) return {0, 1}; // Pente verticale
    if (dy == 0) return {1, 0}; // Pente horizontale
    int g = gcd(abs(dx), abs(dy));
    dx /= g;
    dy /= g;
    // Normaliser le signe
    if (dx < 0) {
        dx = -dx;
        dy = -dy;
    }
    return {dx, dy};
}

int main() {
    int n;
    cin >> n;
    vector<Point> points(n);
    for (int i = 0; i < n; ++i) {
        cin >> points[i].x >> points[i].y;
    }

    ll total_triplets = (ll)n * (n - 1) * (n - 2) / 6;
    ll collinear_count = 0;

    // Énumérer chaque point comme point de référence
    for (int i = 0; i < n; ++i) {
        map<pair<int, int>, int> slope_map;
        // Calculer la pente vers tous les points suivants (j > i)
        for (int j = i + 1; j < n; ++j) {
            pair<int, int> slope = get_slope_pair(points[i], points[j]);
            slope_map[slope]++;
        }

        // Pour chaque pente, si m points (hors i) sont alignés avec i,
        // ils forment C(m,2) triplets dégénérés avec i.
        for (auto& [slope, count] : slope_map) {
            if (count >= 2) {
                collinear_count += (ll)count * (count - 1) / 2;
            }
        }
    }

    ll result = total_triplets - collinear_count;
    cout << result << endl;

    return 0;
}