Script de test automatisé
Pour valider une solution, on peut utilisre un script qui génère des données, exécute une solution standard et la solution proposée, puis compare les sorties. Voici une version réécrite en C++ :
#include<iostream>
#include<cstdlib>
#include<string>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int compteur = 0;
while (true) {
std::cout << "test n°" << compteur++ << "\n";
system("./generateur > entree.txt");
system("./solution_officielle < entree.txt > officiel.txt");
system("./solution_proposee < entree.txt > propose.txt");
if (system("diff -q officiel.txt propose.txt > /dev/null") != 0) {
std::cout << "Mauvaise réponse\n";
break;
}
std::cout << "Correct\n";
}
return 0;
}
Problème 1 : Équilibrage de séquence
Étant donné une séquence d'entiers de longueur n, chaque élément peut transférer sa valeur à ses voisins gauche ou droit. On veut rendre tous les éléments égaux avec un minimum de transferts. On doit aussi construire une solution de dictionnaire minimale. La contrainte est n ≤ 3×10⁵.
Approche : On parcourt de gauche à droite. Pour chaque position, on privilégie les donneurs à gauche. On utilise un tas min pour gérer les positions des donneurs. Chaque donneur est inséré et extrait au plus une fois, d'où une complexité O(n log n).
Problème 2 : Maximum de la différence extrême
On cherche à maximiser la différence extrême sur des sous-intervalles de longueur donnée. On peut bin-searcher la valeur. Les propriétés clés : un intervalle plus long a une différence extrême au moins aussi grande. On peut utiliser une table de type ST pour calculer efficacement.
Problème 3 : Contributions individuelles
On considère la contribution de chaque élément. Le problème revient à placer chaque nombre à sa position correcte en comptant le nombre d'éléments plus petits à sa gauche.
Problème 4 : Plus court chemin avec conditions
Implémentation de Dijkstra pour un graphe pondéré. Voici une version réécrite avec des noms de variables et une structure différents :
#include<vector>
#include<queue>
#include<iostream>
#include<limits>
struct Arete {
int destination, poids;
};
class Graphe {
public:
int nbSommets;
std::vector<std::vector<Arete>> adjacences;
Graphe(int n) : nbSommets(n), adjacences(n + 1) {}
void ajouterArete(int u, int v, int w) {
adjacences[u].push_back({v, w});
adjacences[v].push_back({u, w});
}
std::vector<long long> dijkstra(int depart, const std::vector<long long>& poidsInitiaux) {
std::vector<long long> distances(nbSommets + 1, std::numeric_limits<long long>::max());
std::vector<bool> visite(nbSommets + 1, false);
using P = std::pair<long long, int>;
std::priority_queue<P, std::vector<P>, std::greater<P>> file;
for (int i = 1; i <= nbSommets; ++i) {
distances[i] = poidsInitiaux[i];
file.push({distances[i], i});
}
while (!file.empty()) {
auto [dist, u] = file.top();
file.pop();
if (visite[u]) continue;
visite[u] = true;
for (const auto& arete : adjacences[u]) {
int v = arete.destination;
int w = arete.poids;
if (distances[u] + w < distances[v]) {
distances[v] = distances[u] + w;
file.push({distances[v], v});
}
}
}
return distances;
}
};
int main() {
int n, m;
std::cin >> n >> m;
Graphe g(n);
std::vector<long long> poidsInitiaux(n + 1);
for (int i = 1; i <= n; ++i) {
std::cin >> poidsInitiaux[i];
}
for (int i = 0; i < m; ++i) {
int a, b, c;
std::cin >> a >> b >> c;
g.ajouterArete(a, b, c);
}
auto resultats = g.dijkstra(1, poidsInitiaux);
for (int i = 1; i <= n; ++i) {
std::cout << resultats[i] << " ";
}
std::cout << "\n";
return 0;
}
Problème 5 : Arbres couvrants et cycles
Pour n ≤ 6×10⁵, on considère l'arbre final. Si une arête de l'arbre n'est pas optimale, on peut la remplacer par une arête non-arbre pour réduire le poids du MST.
Problème 6 : Chemins avec obstacles
Pour n ≤ 10⁵, on modélise le problème en construisant un graphe à partir des points critiques. Voici une implémentation de BFS 0-1 réécrite :
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
struct Point {
int x, y;
};
int bfs01(const std::vector<Point>& points, int depart, int arrivee, int nombreObstacles) {
// Implémentation simplifiée de BFS 0-1 pour un graphe avec obstacles
// ... (logique détaillée omise pour la brièveté)
return -1; // distance minimale
}
Problème 7 : Connexité par retrait et ajout d'arêtes
Étant donné un graphe, on peut retirer une arête et en ajouter une autre. On veut minimiser le nombre d'opérations pour rendre le graphe connexe. On doit aussi fournir une solution de dictionnaire minimale.
Problème 8 : Distances entre couleurs différentes
On a un graphe avec des sommets colorés. À chaque modification de couleur, on demande la plus courte distance entre deux couleurs différentes. La solution repose sur le fait que la réponse doit être sur l'arbre couvrant minimal. On peut utiliser une structure de données dynamique pour maintenir les informations de couleur et de distance.
Problème 9 à 38 : Résumé de divers problèmes
Les problèmes restants couvrent des thèmes variés : optimisation, graphes, séquences, dynamique, etc. Voici quelques points saillants :
- Problème 11 : Sous-séquence croissante maximale avec une structure de type arbre BIT.
- Problème 12 : Calcul de la différence absolue entre deux séquences en utilisant le fait que la plage est limitée.
- Problème 13 : Maximisation du profit en choisissant des objets de deux groupes avec une approche gloutonne.
- Problème 14 : Plus grande aire d'un sous-rectangle sans obstacles, avec un balayage classique.
- Problème 15 : Couverture minimale de rectangles en utilisant une pile.
- Problème 16 : Partitionnement d'une séquence en segments de somme ≤ k avec prétraitement par doubleur.
- Problème 17 : Maximisation de la valeur minimale par découpe d'une grille avec bin-search.
- Problème 18 : Rendre tous les éléments égaux par opérations d'intervalle, conclusion classique.
- Problème 19 : Minimisation de la somme des carrés des différences par échanges, réduite à compter les inversions.
- Problème 20 : Problème de confiance pour résoudre des problèmes, avec analyse de séquence.
- Problème 21 : Comptage des éléments mal placés via une structure BIT.
- Problème 22 : Minimisation des menteurs en utilisant la programmation dynamique sur les intervalles de rang.
- Problème 23 : Plus court chemin entre villes intéressantes en utilisant une approche par coloration binaire et Dijkstra multi-sources.
- Problème 24 : Sous-séquence la plus longue formant une suite consecutive, avec hachage aléatoire.
- Problème 25 : Problème de piles avec score maximal, réduit à une plus longue sous-séquence croissante.
- Problème 26 : Maintenance dynamique d'une expression avec arbre de segments.
- Problème 27 : Reconstruction d'une matrice à partir de distances, avec solution constructive.
- Problème 28 : Comptage des permutations après XOR, avec analyse par bit et split-search.
- Problème 29 : Échange d'éléments pour éliminer les doublons, modélisé comme un problème de coloration de graphe.
- Problème 30 : Coloration d'intervalles avec compatge des configurations, dynamique sur les profondeurs.
- Problème 31 : Calcul de probabilités dans un jeu avec des formules combinatoires.
- Problème 32 : Problème d'arbre avec re-racine DP pour calculer les coûts maximaux.
- Problème 33 : Condition de réductibilité d'une permutation à un seul élément.
- Problème 34 : Longueur maximale d'un intervalle où tous les éléments sont multiples du minimum, avec approche par diviseurs.
Chaque problème requiert une analyse spécifique et l'adaptation d'algorithmes classiques. Les solutions détaillées sont souvent disponibles dans les ressources de programmation compétitive.