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(input())
    poids = list(map(int, input().split()))
    file_priorite = []
    
    for p in poids:
        heapq.heappush(file_priorite, p)
        
    cout_total = 0
    while len(file_priorite) > 1:
        premier = heapq.heappop(file_priorite)
        second = heapq.heappop(file_priorite)
        somme = premier + second
        cout_total += somme
        heapq.heappush(file_priorite, somme)
        
    print(cout_total)

Plus Courts Chemins Multi-Sources (Floyd-Warshall)

L'algorithme de Floyd-Warshall permet de calculer les distances minimales entre toutes les paires de sommets. Pour reconstruire le chemin, nous maintenons une matrice de successeurs mise à jour lors de chaque relaxation.

from collections import defaultdict
from math import inf

def resoudre_plus_court_chemin():
    nb_points = int(input())
    nom_vers_id = {}
    id_vers_nom = []
    
    for i in range(nb_points):
        nom = input()
        nom_vers_id[nom] = i
        id_vers_nom.append(nom)
        
    adj = [[inf] * nb_points for _ in range(nb_points)]
    nb_aretes = int(input())
    suivant = [[-1] * nb_points for _ in range(nb_points)]
    
    for _ in range(nb_aretes):
        u_nom, v_nom, poids = input().split()
        u, v = nom_vers_id[u_nom], nom_vers_id[v_nom]
        p = int(poids)
        if p < adj[u][v]:
            adj[u][v] = adj[v][u] = p
            suivant[u][v] = v
            suivant[v][u] = u

    for k in range(nb_points):
        for i in range(nb_points):
            for j in range(nb_points):
                if adj[i][k] + adj[k][j] < adj[i][j]:
                    adj[i][j] = adj[i][k] + adj[k][j]
                    suivant[i][j] = suivant[i][k]

    nb_requetes = int(input())
    for _ in range(nb_requetes):
        dep, dest = input().split()
        u, v = nom_vers_id[dep], nom_vers_id[dest]
        curr = u
        while curr != v:
            prochain = suivant[curr][v]
            print(f"{id_vers_nom[curr]}->({adj[curr][prochain]})->", end="")
            curr = prochain
        print(id_vers_nom[v])

Distance Minimale entre Composantes (DFS + BFS)

Ce problème consiste à identifier une première île via un parcours en profondeur (DFS), puis à utiliser un parcours en largeur (BFS) multi-sources pour trouver la distance la plus courte vers une seconde île.

from collections import deque

def distance_isolee():
    taille = int(input())
    grille = [list(input()) for _ in range(taille)]
    visite = [[False] * taille for _ in range(taille)]
    file_bfs = deque()
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    def marquer_ile(r, c):
        pile = [(r, c)]
        visite[r][c] = True
        while pile:
            curr_r, curr_c = pile.pop()
            file_bfs.append((curr_r, curr_c, 0))
            for dr, dc in directions:
                nr, nc = curr_r + dr, curr_c + dc
                if 0 <= nr < taille and 0 <= nc < taille:
                    if not visite[nr][nc] and grille[nr][nc] == '1':
                        visite[nr][nc] = True
                        pile.append((nr, nc))

    trouve = False
    for i in range(taille):
        if trouve: break
        for j in range(taille):
            if grille[i][j] == '1':
                marquer_ile(i, j)
                trouve = True
                break

    while file_bfs:
        r, c, d = file_bfs.popleft()
        if grille[r][c] == '1' and d > 0:
            print(d - 1)
            return
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < taille and 0 <= nc < taille and not visite[nr][nc]:
                visite[nr][nc] = True
                file_bfs.append((nr, nc, d + 1))

Programmation Dynamique sur Arbre Binaire

Pour un arbre binaire complet, nous utilisons la DP pour calculer le gain maximal. Pour chaque nœud, on stocke deux états : le gain maximum en incluant le nœud actuel ou en l'excluant.

def resoudre_dp_arbre():
    n = int(input())
    valeurs = [0] + list(map(int, input().split()))
    dp_inclure = [0] * (n + 1)
    dp_exclure = [0] * (n + 1)

    for i in range(n, 0, -1):
        gauche = i * 2
        droite = i * 2 + 1
        dp_inclure[i] = valeurs[i]
        
        if gauche <= n:
            dp_inclure[i] += dp_exclure[gauche]
            dp_exclure[i] += max(dp_inclure[gauche], dp_exclure[gauche])
        if droite <= n:
            dp_inclure[i] += dp_exclure[droite]
            dp_exclure[i] += max(dp_inclure[droite], dp_exclure[droite])
            
    print(max(dp_inclure[1], dp_exclure[1]))

Chemin Eulérien et Algorithme de Hierholzer

La recherche d'une séquence de mots enchaînés revient à trouver un chemin eulérien dans un graphe dirigé où les sommets sont des lettres. Nous utilisons les degrés entrants et sortants pour valider l'existence du chemin.

import sys
sys.setrecursionlimit(2000)

def trouver_catenymes():
    nb_mots = int(input())
    mots = sorted([input() for _ in range(nb_mots)])
    adj = defaultdict(list)
    d_in, d_out = defaultdict(int), defaultdict(int)
    lettres = set()

    for idx, w in enumerate(mots):
        u, v = w[0], w[-1]
        adj[u].append((v, w, idx))
        d_out[u] += 1
        d_in[v] += 1
        lettres.update([u, v])

    depart, arrivee, possible = None, None, True
    for c in lettres:
        diff = d_out[c] - d_in[c]
        if diff == 1:
            if depart is not None: possible = False
            depart = c
        elif diff == -1:
            if arrivee is not None: possible = False
            arrivee = c
        elif diff != 0:
            possible = False

    if not possible:
        print("***")
        return

    depart = depart if depart else min(lettres)
    resultat, utilise = [], [False] * nb_mots

    def hierholzer(u):
        for v, mot, i in adj[u]:
            if not utilise[i]:
                utilise[i] = True
                hierholzer(v)
                resultat.append(mot)

    hierholzer(depart)
    if len(resultat) != nb_mots:
        print("***")
    else:
        print(".".join(resultat[::-1]))

Arbre de Segment avec Propagation Paresseuse (Lazy Propagation)

L'arbre de segment permet des mises à jour et des requêtes sur des intervalles en O(log N). La teechnique "lazy" retarde les mises à jour pour optimiser les performances sur les modifications de plages.

class ArbreSegment:
    def __init__(self, n):
        self.n = n
        self.arbre = [0] * (4 * n)
        self.paresse = [0] * (4 * n)

    def _pousser(self, node):
        if self.paresse[node] != 0:
            val = self.paresse[node]
            self.arbre[2 * node] += val
            self.paresse[2 * node] += val
            self.arbre[2 * node + 1] += val
            self.paresse[2 * node + 1] += val
            self.paresse[node] = 0

    def mettre_a_jour(self, node, debut, fin, l, r, v):
        if l <= debut and fin <= r:
            self.arbre[node] += v
            self.paresse[node] += v
            return
        self._pousser(node)
        milieu = (debut + fin) // 2
        if l <= milieu:
            self.mettre_a_jour(2 * node, debut, milieu, l, r, v)
        if r > milieu:
            self.mettre_a_jour(2 * node + 1, milieu + 1, fin, l, r, v)
        self.arbre[node] = max(self.arbre[2 * node], self.arbre[2 * node + 1])

    def requete(self, node, debut, fin, l, r):
        if l <= debut and fin <= r:
            return self.arbre[node]
        self._pousser(node)
        milieu = (debut + fin) // 2
        res = -float('inf')
        if l <= milieu:
            res = max(res, self.requete(2 * node, debut, milieu, l, r))
        if r > milieu:
            res = max(res, self.requete(2 * node + 1, milieu + 1, fin, l, r))
        return res