Mat_boa e l'elusivo 100/100

In un vecchio thread riguardante questo problema (riassunto: trova un triangolo in un grafo diretto) ho letto che la soluzione ottimale ha complessità O(n^2). Non riesco a trovare però una soluzione con complessità minore di O(mn), dove m è il numero di archi, e chiaramente essendo nel caso peggiore m = n^2 la complessità della mia soluzione è O(n^3).
Il fatto è che anche cercando su internet, le soluzioni migliori che trovo hanno complessità O(mn), oppure O(n^{2.4}) ma richiedono di calcolare il quadrato della matrice (e l’algoritmo che permette di farlo con questa complessità è piuttosto oscuro e ha poche applicazioni pratiche). Ho provato anche con vari tipi di fast I/O ma non riesco proprio a superare quel 90/100. Qualche indizio per la soluzione ottimale?

La mia soluzione per ora è:

per ogni arco (i, j)
    per ogni figlio k di j
        se esiste l'arco (k, i)
            stampa i, j, k e fermati

C’è una soluzione O(n). Devi trovare un solo ciclo di lunghezza 3 in un grafo orientato…

se esiste un ciclo di lunghezza k >= 3, esistono per forza 3 dei suoi elementi che formano un ciclo

Non mi sembra corretta questa tua supposizione :joy:

Con le ipotesi del grafo del problema sì :stuck_out_tongue:

2 Mi Piace

Esatto, però dubito che la soluzione possa essere O(n) dato che in input abbiamo n^2 archi :slight_smile:

se per ogni coppia di nodi (u,v) esiste l’arco (u --> v) o (v -->u), allora sì

Una volta trovato un ciclo generico >= 3 come bisogna comportarsi?
Ho provato con una dfs da ogni nodo facente parte del ciclo generico per vedere quali possano comporre un ciclo di 3 però da 95/100, solo il penultimo task va in timeout.

Cosa mi sfugge?

Fai un disegno, sai che per ogni coppia esiste un arco in un verso oppure nell’altro. Prova a dimostrare una proprietà di quei cicli

1 Mi Piace

Devi credere alla fatina induttivina

1 Mi Piace

Ci sono riuscito :stuck_out_tongue: grazie

Direi che questo topic è aperto da un sacco di tempo; per evitare necroposting, vuoi l’onore -e l’onere- di scrivere la tua dimostrazione?

L’assunzione del problema è importantissima: tra due coppie di nodi qualsiasi c’è sempre un arco, in un verso o nell’altro.

Se troviamo un ciclo di qualsiasi lunghezza possiamo, in tempo lineare, riuscire a trovare un ciclo di lunghezza tre.

Se abbiamo un ciclo composto da 5 nodi per esempio:
1 -> 2 -> 3 -> 4 -> 5 (e poi di nuovo 1 etc.)

Prendiamo i primi tre:
1 -> 2 -> 3, se volessimo farlo diventare un ciclo, servirebbe un arco che va da 3 a 1.

quindi possiamo scorrere linearmente i nodi e vedere quali formano un arco (direzionato dall’ultimo al primo, quindi da 3 ad 1, da 4 a 2 e così via, almeno in questo caso d’esempio) e, appena trovato, stamparli.

Se non si trova, -1.

Non è molto teorica però spero vada bene :stuck_out_tongue:

(ah, ed io stavo per necropostare su abc_altavelocita :frowning:)

1 Mi Piace

funziona, ma la fatina induttivina è triste :cry: perchè non l’hai usata.
In maniera molto più elegante: dato un vettore V di indici tali che formano un ciclo, ossia (V_i,V_{i+1}) \in E \forall i: 1\leq i<|V| e (V_N,V_1)\in E

  1. se |V|=3 allora abbiamo trovato il ciclo V_1,V_2,V_3
  2. se c’è un arco da V_3 a V_1, esiste il ciclo V_1,V_2,V_3
  3. altrimenti c’è un ciclo lungo |V|-1 che è uguale a V \mathbin{\vcenter{\hbox{\scriptscriptstyle\setminus$}}} V_2$: rimuoviamo V_2 da V e torniamo al punto1
4 Mi Piace

Inoltre ci sono casi dove il tuo algoritmo sbaglia.
Puoi avere un ciclo di 6 nodi, ma gli archi che collegano V_i a V_{i+2} tutti nel senso sbagliato, e quindi camminando sul bordo non trovi la soluzione, che invece abbiamo dimostrato esiste

Riesci a darmi un input così da provarlo?