Modélisation et analyse mathématique

Le problème consiste à déplacer un élément unique (la valeur 1) dans un tableau de taille n, initialement situé à l'index p. À chaque étape, il est possible d'inverser un sous-tableau contigu de taille k. Certains indices sont interdits (tableau banned) et ne peuvent jamais contenir la valeur 1. L'objectif est de déterminer le nombre minimal d'opérations pour amener la valeur 1 à chaque index du tableau.

Supposons que la valeur 1 se trouve actuellement à l'index i. Si nous inversons un sous-tableau commençant à l'index j et se terminant à j + k - 1, la position relative de 1 par rapport au début du sous-tableau est i - j. Après l'inversion, sa nouvelle position par rapport à la fin du sous-tableau sera identique. La nouvelle position absolue i' peut être calculée ainsi :

i' = (j + k - 1) - (i - j) = k - 1 - i + 2j

Les contraintes sur j pour que le sous-tableau soit valide et contienne i sont :

• 0 <= j et j + k - 1 < n (limites du tableau)
• j <= i et i <= j + k - 1 (le sous-tableau doit couvrir i)

Ce qui se simplifie en : max(0, i - k + 1) <= j <= min(i, n - k).

En substituant les valeurs minimales et maximales de j, on obtient l'intervalle des positions atteignables. De plus, le terme 2j étant toujours pair, la parité de la nouvelle position i' dépend uniquement de k - 1 - i. Cela signifie qu'à chaque étape, la parité des indices visités alterne ou reste identique de manière prévisible, ce qui permet de séparer les indices pairs et impairs pour optimiser les recherches.

Stratégie 1 : Parcours en largeur (BFS) avec ensembles ordonnés

Une approche naïve de type BFS explorerait tous les j posisbles, entraînant une complexité de O(n·k). Pour optimiser, nous pouvons utiliser deux ensembles ordonnés (std::set en C++) pour stocker les indices non visités, séparés par parité. Lors de l'exploration d'un nœud, nous calculons l'intervalle des postiions cibles et utilisons lower_bound et upper_bound pour extraire et supprimer efficacement les indices valides. Cette approche réduit la complexité temporelle à O(n log n).

class Solution {
public:
    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
        vector<int> distances(n, -1);
        distances[p] = 0;
        
        set<int> unvisited[2];
        vector<bool> is_blocked(n, false);
        for (int b : banned) is_blocked[b] = true;
        
        for (int i = 0; i < n; ++i) {
            if (!is_blocked[i] && i != p) {
                unvisited[i % 2].insert(i);
            }
        }
        
        queue<int> q;
        q.push(p);
        
        while (!q.empty()) {
            int curr = q.front();
            q.pop();
            
            int min_j = max(0, curr - k + 1);
            int max_j = min(curr, n - k);
            
            int min_next = k - 1 - curr + 2 * min_j;
            int max_next = k - 1 - curr + 2 * max_j;
            
            int parity = min_next % 2;
            auto& targets = unvisited[parity];
            
            auto it_start = targets.lower_bound(min_next);
            auto it_end = targets.upper_bound(max_next);
            
            for (auto it = it_start; it != it_end; ++it) {
                distances[*it] = distances[curr] + 1;
                q.push(*it);
            }
            targets.erase(it_start, it_end);
        }
        
        return distances;
    }
};

Stratégie 2 : Optimisation par Union-Find (Disjoint Set)

Bien que l'utilisation de std::set soit efficace, les opérations d'insersion et de recherche introduisent un facteur logarithmique. Pour atteindre une complexité quasi linéaire, nous pouvons employer une structure de type Union-Find (ou un tableau de pointeurs avec compression de chemin) pour sauter les indices déjà visités ou interdits.

L'idée est de maintenir un tableau parent où chaque index pointe vers le prochain index valide de même parité. Lorsqu'un index est traité, il est "fusionné" avec l'index i + 2. Des nœuds sentinelles (comme n et n + 1) sont utilisés pour marquer la fin des chaînes paires et impaires, évitant ainsi les débordements de mémoire.

class Solution {
    vector<int> parent;
    
    int find(int i) {
        return parent[i] == i ? i : parent[i] = find(parent[i]);
    }
    
public:
    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
        vector<int> ans(n, -1);
        ans[p] = 0;
        
        parent.resize(n + 2);
        iota(parent.begin(), parent.end(), 0);
        
        auto mark_visited = [&](int i) {
            parent[i] = (i + 2 < n) ? i + 2 : (i % 2 == 0 ? n : n + 1);
        };
        
        vector<bool> blocked(n, false);
        for (int b : banned) blocked[b] = true;
        
        for (int i = 0; i < n; ++i) {
            if (blocked[i] || i == p) {
                mark_visited(i);
            }
        }
        
        queue<int> q;
        q.push(p);
        
        while (!q.empty()) {
            int u = q.front(); 
            q.pop();
            
            int j_min = max(0, u - k + 1);
            int j_max = min(u, n - k);
            
            int nxt_min = k - 1 - u + 2 * j_min;
            int nxt_max = k - 1 - u + 2 * j_max;
            
            int v = find(nxt_min);
            while (v <= nxt_max) {
                ans[v] = ans[u] + 1;
                q.push(v);
                mark_visited(v);
                v = find(v);
            }
        }
        return ans;
    }
};