L'auteur présente son bilan de la 87ème compétition bi-hebdomadaire, ayant réussi à résoudre trois des quatre problèmes proposés.

6184. Calculer le Nombre de Jours Passés Ensemble

Le premier problème consistait à dénombrer les jours communs où deux personnes étaient disponibles, étant donné leurs périodes de présence respectives.

L'auteur a rencontré des difficultés initiales avec la manipulation des chaînes de caractères représentant les dates. L'API sscanf n'était pas familière, entraînant une perte de temps. L'utilisation de substr et stoi (recherché en ligne) a finalement permis de traiter les dates. Un manque de refactorisation du code a également conduit à des répétitions inutiles.

Une approche alternative pour résoudre ce problème consiste à convertir chaque date en un nombre de jours depuis le début de l'année. Ensuite, il faut déterminer l'intervalle de jours communs aux deux périodes. Si l'intervalle de début de la période commune est postérieur à l'intervalle de fin, il n'y a pas de jours communs. Sinon, le nombre de jours est calculé comme la différence entre la fin de l'intervalle commun et le début de l'intervalle commun, plus un.

#include <string>
#include <algorithm>
#include <vector>

class Solution {
private:
    // Tableau pour stocker le nombre de jours dans chaque mois (non bissextile)
    std::vector<int> joursParMois = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    // Fonction pour convertir une date (MM-DD) en un nombre total de jours depuis le début de l'année
    int convertirEnJours(const std::string& date) {
        int mois = std::stoi(date.substr(0, 2));
        int jour = std::stoi(date.substr(3, 2));
        int joursTotaux = 0;
        for (int i = 1; i < mois; ++i) {
            joursTotaux += joursParMois[i];
        }
        return joursTotaux + jour;
    }

public:
    int countDaysTogether(std::string arriveeA, std::string departA, std::string arriveeB, std::string departB) {
        // Convertir les dates de début et de fin pour chaque personne en jours
        int debutA = convertirEnJours(arriveeA);
        int finA = convertirEnJours(departA);
        int debutB = convertirEnJours(arriveeB);
        int finB = convertirEnJours(departB);

        // Calculer le début et la fin de la période commune
        int debutCommun = std::max(debutA, debutB);
        int finCommun = std::min(finA, finB);

        // S'il n'y a pas de chevauchement, retourner 0
        if (debutCommun > finCommun) {
            return 0;
        }

        // Sinon, retourner la durée de la période commune
        return finCommun - debutCommun + 1;
    }
};

6185. Nombre Maximum de Correspondances Joueur-Entraîneur

Ce problème a été résolu rapidement, en 3 minutes, car il s'agit d'un problème de greedy classique. La preuve de la correction de l'approche greedy est fournie : après avoir trié les joueurs et les entraîneurs par niveau, il est toujours optimal de faire correspondre le joueur le moins qualifié avec l'entraîneur disponible le moins qualifié qui puisse l'entraîner. Si une correspondance non optimale est supposée, on peut toujours la réorganiser pour obtenir une correspondance optimale sans diminuer le nombre total de correspondances.

L'implémentation trie les deux vecteurs puis utilise deux pointeurs pour trouver le nombre maximum de paires possibles.

#include <vector>
#include <algorithm>

class Solution {
public:
    int matchPlayersAndTrainers(std::vector<int>& joueurs, std::vector<int>& entraineurs) {
        // Trier les joueurs et les entraîneurs par niveau croissant
        std::sort(joueurs.begin(), joueurs.end());
        std::sort(entraineurs.begin(), entraineurs.end());

        int pointeurJoueur = 0;
        int pointeurEntraineur = 0;
        int correspondancesTrouvees = 0;

        // Parcourir les deux listes avec les pointeurs
        while (pointeurJoueur < joueurs.size() && pointeurEntraineur < entraineurs.size()) {
            // Si le joueur actuel peut être entraîné par l'entraîneur actuel
            if (joueurs[pointeurJoueur] <= entraineurs[pointeurEntraineur]) {
                // Former une paire et avancer les deux pointeurs
                correspondancesTrouvees++;
                pointeurJoueur++;
                pointeurEntraineur++;
            } else {
                // Sinon, l'entraîneur actuel ne convient pas à ce joueur, essayer le prochain entraîneur
                pointeurEntraineur++;
            }
        }
        return correspondancesTrouvees;
    }
};

6186. Longueur Minimale du Plus Petit Sous-tableau pour Obtenir un OR Maximum

L'auteur décrit sa solution initiale pour ce problème comme étant complexe. Elle implique le suivi du nombre d'occurrences de bits '1' pour chaque position (jusqu'à 32 bits) et l'utilisation de deux pointeurs pour trouver la longueur minimale du sous-tableau. Le code tente de maintenir dynamiquement l'OR bit à bit du sous-tableau courant et d'ajuster les pointeurs pour minimiser la longueur tout en atteignant l'OR global maximum.

Après avoir consulté une solution plus élégante, l'auteur partage une approche basée sur l'analyse bit à bit. L'idée est de considérer chaque bit indépendamment. Pour chaque bit, la longueur minimale du sous-tableau nécessaire pour que ce bit soit activé (soit '1') est déterminée par la position du bit '1' le plus à droite dans ce bit particulier, à partir de la position actuelle. En combinant ces informations pour tous les bits, on trouve la position du bit '1' le plus à droite parmi tous les bits significatifs. La longueur du sous-tableau est alors la distance entre la position actuelle et cette position la plus à droite.

La solution optimisée parcourt le tableau à l'envers. Pour chaque élément, elle met à jour la dernière position vue pour chaque bit. La longueur minimale pour cet élément est ensuite calculée en prenant le maximum de la position actuelle et de la dernière position de n'importe quel bit présent dans l'élément.

Complexité Temporelle : O(N log S), où N est la taille du tableau et S est la valeur maximale des éléments (pour considérer tous les bits). Complexité Spatiale : O(N + log S), pour stocker les résultats et les dernières positions des bits.

#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<int> smallestSubarrays(std::vector<int>& nums) {
        int n = nums.size();
        // p[j] stocke la dernière position (index) où le j-ème bit était à 1
        std::vector<int> dernierePositionBit(30, -1); 
        std::vector<int> resultats(n);

        // Parcourir le tableau à l'envers
        for (int i = n - 1; i >= 0; --i) {
            int valeurActuelle = nums[i];
            // Initialiser la longueur minimale potentielle avec la position actuelle
            int longueurMinPotentielle = i; 

            // Mettre à jour la dernière position pour chaque bit présent dans nums[i]
            for (int j = 0; j < 30; ++j) {
                if (((valeurActuelle >> j) & 1) == 1) {
                    dernierePositionBit[j] = i;
                }
                // La longueur minimale pour nums[i] est déterminée par la dernière apparition de n'importe quel bit qui le compose
                longueurMinPotentielle = std::max(longueurMinPotentielle, dernierePositionBit[j]);
            }
            // La longueur du sous-tableau est la distance entre la fin et le début (inclus)
            resultats[i] = longueurMinPotentielle - i + 1;
        }
        return resultats;
    }
};

6187. Nombre Minimum Initial d'Argent pour Compléter Toutes les Transactions

Le problème demande de trouver le montant d'argent initial minimum nécessaire pour effectuer une série de transactions, où chaque transaction a un coût et rapporte un certain montant. L'ordre des transactions peut être choisi.

L'auteur explique que l'ordre des transactions précédentes n'affecte pas le montant d'argent avant la transaction actuelle. Pour le pire scénario (nécessitant le plus d'argent initial), on peut envisager chaque transaction comme étant la dernière effectuée. Cela permet de déterminer le besoin maximal d'argent avant cette transaction.

L'exemple [[2,1],[5,0],[4,2]] est utilisé pour illustrer : si [4,2] est la dernière transaction, elle impose la plus forte contrainte sur l'argent initial, indépendamment de l'ordre des deux autres.

La solution consiste à calculer la perte nette totale (somme des dépense - revenu pour les transactions où dépense > revenu). Ensuite, pour chaque transaction, on calcule l'argent requis si c'était la dernière, en soustrayant la perte nette des transactions précédentes qui ont un coût supérieur au revenu, et en ajoutant le coût de la transaction actuelle. Le maximum de ces valeurs est le minimum d'argent initial requis.

#include <vector>
#include <numeric>
#include <algorithm>

class Solution {
public:
    long long minimumMoney(std::vector<std::vector<int>>& transactions) {
        long long perteNetteTotale = 0;
        // Calculer la perte nette totale cumulée pour les transactions où le coût est supérieur au revenu
        for (const auto& transaction : transactions) {
            if (transaction[0] > transaction[1]) {
                perteNetteTotale += (long long)transaction[0] - transaction[1];
            }
        }

        long long argentInitialMinimum = 0;
        // Pour chaque transaction, déterminer l'argent nécessaire si elle était la dernière
        for (const auto& transaction : transactions) {
            long long coutActuel = transaction[0];
            long long revenuActuel = transaction[1];
            long long perteTransaction = 0;

            // Si cette transaction entraîne une perte, ajuster la perte nette totale
            if (coutActuel > revenuActuel) {
                perteTransaction = coutActuel - revenuActuel;
            }
            
            // L'argent nécessaire avant cette transaction est la perte nette totale moins la perte de cette transaction (car elle est la dernière)
            // plus le coût de cette transaction elle-même.
            long long argentRequisSiDerniere = perteNetteTotale - perteTransaction + coutActuel;
            
            // Mettre à jour l'argent initial minimum global
            argentInitialMinimum = std::max(argentInitialMinimum, argentRequisSiDerniere);
        }
        
        return argentInitialMinimum;
    }
};