Ieri sera ho letto troppo frettolosamente il problema “All Possible Incresing Subsequences” e ho considerato solo il caso in cui la sequenza è non-decrescente, tuttavia dopo quel 10/100 ho capito che non era così (ma dai? °L°).
Quindi volevo rimediare a quell’inguardabile punteggio ma l’unica soluzione che ho in mente ha complessità O(N^2).
Ho la mia sequenza A e un secondo array S dove S[i] rappresenta il numero di sottosequenze crescenti che terminano con A[i]. Osservando poi che S[i] lo posso ottenere dalla somma degli S[j] per (0<=j<i && S[j]<S[i]) +1, allora mi basta costruire S partendo dal caso base S[0]=1.
La soluzione del problema sarà la somma di tutti i valori di S.
Il problema quindi è: come faccio a farlo in modo efficiente?
Il Fenwick Tree ho letto cos’è ma ci ho capito ben poco, ma questo non è il grosso problema (alla fine basta avere la pazienza di mettersi a fare due disegnini).
Quello che è più grave è che non ho la minima idea di dove applicarlo in questo problema (oltre a sommare i valori di S, a che mi dovrebbe servire?)
In realtà i valori possibili diversi che tu puoi avere sono al massimo N. Che la sequenza sia 1 2 3 o 10 20 30 non cambia la risposta. Quindi i tuoi N valori della sequenza li puoi rimappare in numeri da 1 a N.
Ho pure letto fino alla fine il “tutorial” sui Fenwick Tree su Topcoder e devo dire che non sono difficili (l’altra volta ho letto solo le prime righe e trovavo tutto molto contorto, ma devo ammettere che poi la strada è tutta in discesa).
Insomma mi basta creare un ulteriore array B=sort(A) e mano a mano che “percorro” A cerco in B (tramite un Fenwick) quanti valori minori di A[i] ho già “visitato”. (o meglio, la somma delle soluzioni che hanno prodotto)
E’ corretto così, no?
Devo solo fare attenzione a quando possiedo in B due o più valori uguali.
