L'Atelier Monstre

Sous-matrice de somme maximale Énoncé. On représente la « taille » d’une matrice par la somme de tous ses éléments. Étant donné une matrice carrée N × N, trouver la plus grande sous-matrice non vide (au moins 1 × 1) au sens de cette somme. Par exemple, dans la matrice 4 × 4 suivante : 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 La sous-mat ...

On a un groupe de combattants organisés en un arbre, où chaque combattant a un maître (sauf le chef). Chaque combattant a une certaine puissance de combat. Le but est d'inviter certains combattants pour maximiser la somme de leur puissance, tout en respectant la contrainte que si un maître est invité, aucun de ses disciples ne peut l'être. Form ...

Codage de Huffman et Optimisation Greedy Pour minimiser le coût total d'un arbre de codage, l'approche gloutonne de Huffman est optimale. En utilisant une file de priorité (tas binaire), nous extrayons répétitivement les deux poids les plus faibles pour construire l'arbre de bas en haut. import heapq def calculer_cout_huffman(): n = int(in ...

Analyse du Problème de Parenthèses Valides Ce défi algorithmique consiste à analyser une chaîne de caractères composée exclusivement de parenthèses ouvrantes ( et fermantes ). L'objectif est d'identifier la longueur maximale d'une sous-chaîne continue qui respecte la syntaxe correcte des parenthèses. Visualisation de la Logique Pour comprendre ...

L'analyse d'un problème de type réseau de flux met en évidence une réduction à un problème d'optimisation. La solution consiste à construire un graphe auxiliaire avec une source et un puits fictifs pour gérer les déséquilibres de flux. Chaque arc original est modélisé par plusieurs arêtes possibles pour permettre la correction du flux et de la ...

Problème A : Somme de Produits Triangulaires Description : Étant donné trois entiers positifs \(A\), \(B\) et \(C\), calculer la valeur modulo \(998244353\) de la somme triple \(\sum_{a=1}^{A} \sum_{b=1}^{B} \sum_{c=1}^{C} a \times b \times c\). Solution : La somme se factorise en \(\left( \sum_{a=1}^{A} a \right) \times \left( \sum_{b=1}^{B} b ...

Problème G: Théorie des jeux avec Rikka Énoncé du problème: Étant donné un graphe non oreinté à n sommets (n ≤ 17), attribuer une valeur à chaque sommet telle que la valeur de chaque sommet soit le mex des valeurs des sommets adjacents. Calculer le nombre total d'attribution valide. Solution: La contrainte sur n suggère une approche par program ...

Maison Voleur Ce problème est analogue à une version non continue de la somme maximale d'une sous-séquence. En séparant le dernier élément, les parties précédentes forment un sous-problème. La solution utilise la programmation dynamique pour calculer le maximum sans voler deux maisons adjacentes. class Solution { public: int rob(vector&l ...

Coloriage de Parenthèses (DP par intervalles) Ce problème classique de programmation dynamique par intervalles nécessite d'abord d'identifier les paires de parenthèses correspondantes à l'aide d'une pile. Pour un intervalle $[l, r]$, le coloriage n'a de sens que si les parenthèses sont appariées. Nous définissons l'état $f(l, r, c_1, c_2)$ comm ...

A. [P12074] L'exercice arithmétique (3) Lien du problème : P12074 On détermine la validité d'une suite de signes pour les \(a_i\) en parcourant de droite à gauche. On regarde les indices avec le même \(j\) comme des chaînes. L'insertion d'un élément ne dépend que de la parité de la longueur de la chaîne actuelle. Il suffit donc de compter le no ...