Visite d'une exposition artistique

Description du problème

Un musée expose des peintures réalisées par les m meilleurs artistes du monde.

Lors de l'achat d'un billet, les visiteurs doivent spécifier deux nombres, a et b, indiquant qu'ils souhaitent voir toutes les peintures de la a-ième à la b-ième (inclus) de l'exposition. Le prix du billet est d'un euro par peinture.

Alex souhaite voir toutes les œuvres des maîtres lors de sa visite. Bien sûr, il souhaite minimiser le coût de son billet.

On vous demande de déterminer les valeurs a et b qu'Alex devrait choisir pour son billet. Les données garantissent qu'une solution existe.

S'il existe plusieurs solutions possibles, choisissez celle avec la plus petite valeur a.

Format d'entrée

La première ligne contient deux entiers n et m, représentant respectivement le nombre total de peintures dans le musée et le nombre d'artistes distincts ayant réalisé ces œuvres.

La deuxième ligne contient n entiers a_i, indiquant l'identifiant de l'artiste pour la i-ième peinture.

Format de sortie

Une ligne contenant deux entiers a et b.

Exemple #1

Entrée d'exemple #1

12 5
2 5 3 1 3 2 4 1 1 5 4 3

Sortie d'exemple #1

2 7

Contraintes des données

• Pour 30% des données, n ≤ 200 et m ≤ 20.
• Pour 60% des données, n ≤ 10^5 et m ≤ 10^3.
• Pour 100% des données, 1 ≤ n ≤ 10^6, 1 ≤ a_i ≤ m ≤ 2×10^3.

// Solution utilisant deux pointeurs pour trouver la sous-séquence minimale contenant tous les artistes
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int nbPeintures, nbArtistes;
    cin >> nbPeintures >> nbArtistes;
    
    vector<int> peintures(nbPeintures + 1);
    for (int i = 1; i <= nbPeintures; i++) {
        cin >> peintures[i];
    }
    
    vector<int> compteur(nbArtistes + 1, 0);
    int artistesUniques = 0;
    longueurMinimale = INT_MAX;
    debut = 1, fin = 1;
    gauche = 1, droite = 1;
    
    while (gauche <= nbPeintures && droite <= nbPeintures) {
        if (artistesUniques == nbArtistes) {
            if (longueurMinimale > droite - gauche + 1) {
                longueurMinimale = droite - gauche + 1;
                debut = gauche;
                fin = droite;
            }
            
            // Réduire la fenêtre par la gauche
            compteur[peintures[gauche]]--;
            if (compteur[peintures[gauche]] == 0) {
                artistesUniques--;
            }
            gauche++;
        } else {
            // Étendre la fenêtre par la droite
            droite++;
            if (droite > nbPeintures) break;
            
            if (compteur[peintures[droite]] == 0) {
                artistesUniques++;
            }
            compteur[peintures[droite]]++;
        }
    }
    
    cout << debut << " " << fin;
    return 0;
}

// Alternative avec approche de fenêtre glissante optimisée
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int nbPeintures, nbArtistes;
    cin >> nbPeintures >> nbArtistes;
    
    vector<int> peintures(nbPeintures + 1);
    vector<int> dernierePosition(nbArtistes + 1, 0);
    int artistesTrouves = 0;
    longueurMinimale = INT_MAX;
    gauche = 1;
    
    for (int droite = 1; droite <= nbPeintures; droite++) {
        cin >> peintures[droite];
        
        // Mettre à jour la dernière position de l'artiste courant
        dernierePosition[peintures[droite]] = droite;
        
        // Si c'est la première occurrence de cet artiste
        if (dernierePosition[peintures[droite]] == droite) {
            artistesTrouves++;
        }
        
        // Avancer la gauche tant que possible
        while (gauche < dernierePosition[peintures[gauche]]) {
            gauche++;
        }
        
        // Vérifier si nous avons trouvé une solution valide
        if (artistesTrouves == nbArtistes) {
            if (longueurMinimale > droite - gauche + 1) {
                longueurMinimale = droite - gauche + 1;
                debut = gauche;
                fin = droite;
            }
        }
    }
    
    cout << debut << " " << fin;
    return 0;
}