Salve, ho provato a risolvere il problema (CMSocial - a social coding app) ma mi da TLE sugli ultimi due test case. La mia idea è stata quella di scorrere indietro la gerarchia dei capi di ogni dipendente fino ad arrivare al direttore generale e ogni volta sommare 1 al numero di coppie finali.
Qui c’è il mio codice: int coppie(int N, int C[]){ int ans = 0; for(int i = 0; i < N; i++) - Pastebin.com.
Grazie
L’idea funziona ma risulta troppo lenta, ti do qualche spunto per velocizzare. Il testo sta descrivendo, anche abbastanza palesemente, una struttura ad albero, che potrebbe avere, per esempio, una forma di questo tipo:
Utilizzando il tuo codice, quando j varrà 3 farai: 3 \rightarrow 1 contando una coppia.
Quando j varrà 4 farai: 4 \rightarrow 3 \rightarrow 1 contando due coppie.
j varrà 5 farai: 5 \rightarrow 4 \rightarrow 3 \rightarrow 1 contando tre coppie.
Puoi notare come stai risalendo tutto l’albero da 5 fino alla radice quando in realtà, se tu sai che con 4 puoi fare due coppie puoi sapere immediatamente che essendo 5 un figlio di 4 potrai fare una coppia in più quindi tre.
Se l’input corrente è particolarmente sfortunato, ossia l’albero ha la forma di una catena: 1 \rightarrow 2 \rightarrow \dots \rightarrow N eseguirai 1 + 2 + ... + N - 1 = N(N -1)/2 operazioni, ottenendo una complessità temporale pari a O(N^2) che è decisamente troppo alta per l’assunzione N \leq 100000 con il time limit di un secondo.
Grazie mille, ha funzionato! 