Nemico Mortale (18/100)

Aiuto
1

Sono giorni che non riesco fare 100 manco ad un problema, sto impazzendo, mi sembrava di aver avuto una buona idea su questo problema ma mi da output parzialmente corretto su qualche testcase dalla subtask 3 in poi. Il problema più grosso di tutti è che non ho idea del perchè non vada anche perchè non riesco a generare nessun testcase dove fallisce…

bool colora(int k, vector<int> &v, int node, int colore = 0){

    v[node] = colore; // coloro il nodo 

    for(auto x : adj[node]){
        if(v[x] == -1) { // se il nodo non è colorato, lo coloro.
            if(!colora(k, v, x, (colore + 1) % k)) { 
                v[x] = -1; 
                return false; /* se colora() returna false allora non posso 
            }                    non posso usare k colori e devo returnare
                                 false */
        }
        if(v[x] == colore) {
            v[x] = -1;
            return false; // se un vicino è dello stesso colore -> false
        }
    }
    
    return true; // returno true solamente se non ho mai returnato false

}

void smista(int n, int nemico[]){
    adj.resize(n, vector<int>());

    for(int i = 0; i < n; ++i){
        adj[i].push_back(nemico[i]);
        adj[nemico[i]].push_back(i);
    }

    int l = 1, r = n+1; 

    vector<int> sol;

    while(l < r){ // binary search per il primo k per cui colora() = true
        int mid = (l + r) / 2;

        vector<int> visited(n, -1); 

        bool f = true;

        for(int i = 0; i < n; ++i){ // il grafo potrebbe avere più componenti
            if(visited[i] != -1) continue;
            if(!colora(mid, visited, i)) {
                f = false;
                break;
            }
        }

        if(f){
            r = mid;
            sol = visited;
        }else{
            l = mid + 1;
        }

    }


    for(int i = 0; i < l; ++i){
        nuovo_gruppo();
        for(int j = 0; j < n; ++j){
            if(sol[j] == i) aggiungi(j);
        }
    }


}

Vi chiedo aiuto, a me sembra corretto, non so più a cosa pensare, grazie in anticipo.

2

Controesempio su cui il tuo programma crea più gruppi di quanti ne servano.

7
1 2 3 4 5 6 0

Sidenote: mi sembra di capire che stai facendo ricerca binaria sul più piccolo intero k per cui esiste una k-colorazione. Il problema è che per k > 2 non è possibile stabilire se esiste una k-colorazione con un semplice algoritmo greedy come per il caso k=2. Non solo, stabilire se esiste una k-colorazione con k > 2, è un problema np-completo, risolverlo in tempo polinomiale vorrebbe dire risolvere il più grande problema aperto in informatica.

Allo stesso modo anche il problema generale di trovare il numero cromatico di un grafo generico (cioè il minimo numero di colori che servono per colorarlo) è np-completo.

Devi sfruttare meglio la struttura del grafo, che in questo caso è abbastanza regolare da permettere una soluzione lineare.

1 Mi Piace
3

guarda ho aspettato a darti la soluzione (anche perchè all’inizio non capivo). Non ho ancora risolto il problema ma dopo il 1 stage ho imparato un po’ di cose e ho capito cosa intendi, solo che non ho molto tempo per metterlo in pratica e non mi va di lasciare in sospeso sto argomento, grazie mille comunque per la risposta, modificherò questo messaggio appena finisco il problema (potrebbe essere tra 1 ora come mai).