Problème

Étant donné n périodes mensuelles et m contraintes de la forme (début, fin, somme) indiquant le revenu total entre le mois début et le mois fin, déterminer si un ensemble de valeurs de revenus mensuels peut exister sans contradictions.

Approche par Système de Contraintes de Différences

Soit prefix[i] le revenu cumulé jusqu'au mois i (inclus). La contrainte (s, t, v) se traduit par :

prefix[t] - prefix[s-1] = v

Cette égalité peut être décomposée en deux inégalités pour un système de contraintes de différences :

prefix[t] ≤ prefix[s-1] + v
prefix[s-1] ≤ prefix[t] - v

Ce système correspond à un graphe orienté avec des arcs pondérés. Une contradiction est détectée par la présence d'un cycle de poids négatif, vérifiable via un algorithme de plus court chemin modifié.

Implémentation avec Détection de Cycle

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

struct Lien {
    int cible;
    int poids;
};

bool rechercherCycle(int noeud, vector<Lien> graphe[], int etat[], long long distances[]) {
    etat[noeud] = 1;
    for (Lien& arc : graphe[noeud]) {
        if (distances[arc.cible] > distances[noeud] + arc.poids) {
            distances[arc.cible] = distances[noeud] + arc.poids;
            if (etat[arc.cible] == 1 || rechercherCycle(arc.cible, graphe, etat, distances))
                return true;
        }
    }
    etat[noeud] = 2;
    return false;
}

int main() {
    int tests;
    cin >> tests;
    while (tests--) {
        int mois, contraintes;
        cin >> mois >> contraintes;
        vector<Lien> graphe[mois +组];
        int etat[mois +组] = {0};
        long long distances[mois +组];
        fill(distances, distances + mois +组, 0);

        for (int i = 0; i < contraintes; i++) {
            int debut, fin, total;
            cin >> debut >> fin >> total;
            graphe[debut - 1].push_back({fin, total});
            graphe[fin].push_back({debut - 1, -total});
        }

        bool contradiction = false;
        for (int i = 0; i <= mois; i++) {
            if (etat[i] == 0) {
                if (rechercherCycle(i, graphe, etat, distances)) {
                    contradiction = true;
                    break;
                }
            }
        }
        cout << (contradiction ? "false" : "true") << endl;
    }
    return 0;
}

Approche par Union-Find Pondéré

Maintenons un tableau ecart où ecart[x] représente la différence de revenu cumulé entre x et le représentant de son ensemble. Pour une contrainte (s, t, v), on unifie les ensembles de s-1 et t. Si déjà dans le même ensemble, on vérifie la cohérence.

Implémentation Union-Find

#include <iostream>
using namespace std;

int parent[210];
int ecart[210];

int trouver(int x) {
    if (parent[x] != x) {
        int racine = trouver(parent[x]);
        ecart[x] += ecart[parent[x]];
        parent[x] = racine;
    }
    return parent[x];
}

int main() {
    int tests;
    cin >> tests;
    while (tests--) {
        int mois, contraintes;
        cin >> mois >> contraintes;
        for (int i = 0; i <= mois; i++) {
            parent[i] = i;
            ecart[i] = 0;
        }
        bool valide = true;

        while (contraintes--) {
            int debut, fin, total;
            cin >> debut >> fin >> total;
            int repDebut = trouver(debut - 1);
            int repFin = trouver(fin);
            if (repDebut == repFin) {
                if (ecart[fin] - ecart[debut - 1] != total)
                    valide = false;
            } else {
                parent[repFin] = repDebut;
                ecart[repFin] = ecart[debut - 1] - ecart[fin] + total;
            }
        }
        cout << (valide ? "true" : "false") << endl;
    }
    return 0;
}

Approche par Programmation Dynamique Intervallaire

Définissons tableau[l][r] comme le revenu total sur l'intervalle [l, r]. Initialisé à une valeur sentinelle, il est rempli par les contriantes. Pour chaque intervalle, on tente une division en deux sous-intervales et on vérifie la cohérence des sommes.

Implémentation DP

#include <iostream>
#include <climits>
#include <cstring>
using namespace std;

const int SENTINELLE = INT_MAX / 2;

int main() {
    int tests;
    cin >> tests;
    while (tests--) {
        int mois, contraintes;
        cin >> mois >> contraintes;
        int revenu[210][210];
        for (int i = 1; i <= mois; i++)
            for (int j = 1; j <= mois; j++)
                revenu[i][j] = SENTINELLE;

        bool coherent = true;
        while (contraintes--) {
            int l, r, val;
            cin >> l >> r >> val;
            if (revenu[l][r] == SENTINELLE)
                revenu[l][r] = val;
            else if (revenu[l][r] != val)
                coherent = false;
        }

        if (!coherent) {
            cout << "false" << endl;
            continue;
        }

        for (int longueur = 2; longueur <= mois && coherent; longueur++) {
            for (int debut = 1; debut + longueur - 1 <= mois; debut++) {
                int fin = debut + longueur - 1;
                for (int separateur = debut; separateur < fin; separateur++) {
                    if (revenu[debut][separateur] != SENTINELLE && 
                        revenu[separateur + 1][fin] != SENTINELLE) {
                        int somme = revenu[debut][separateur] + revenu[separateur + 1][fin];
                        if (revenu[debut][fin] == SENTINELLE)
                            revenu[debut][fin] = somme;
                        else if (revenu[debut][fin] != somme)
                            coherent = false;
                    }
                }
            }
        }
        cout << (coherent ? "true" : "false") << endl;
    }
    return 0;
}