Stavo provando a risolvere scmax https://training.olinfo.it/#/task/ois_scmax/statement . La mia idea era di usare un approccio dp, partendo dalla prima nota e arrivando all’ultima. Per ogni nota, cerco tra tutte quelle prima quella che appartenga alla sequenza più lunga e che rispetti le condizioni(Si > Sj o Si=Csj). Questa versione usciva di tempo quindi quello che ho fatto è stato aggiungere un vettore v di pair, dove ogni elemento mi diceva la lunghezza fino a una certa nota e l’indice della nota, e ogni volta che ne aggiungevo uno sortavo il vettore, in questo modo percorrendolo dal maggiore al minore(sortando per la lunghezza della sequenza) il primo che trovavo era la soluzione e uscivo dal ciclo. Sfortunatamente anche questo usciva di tempo facendo solo 35. A questo punto ho implementato un inserimento binario nel vettore, con la stessa logica di tenere il vettore ordinato per la lunghezza, ma anche in questo caso seppur andasse un pochino più veloce esce di tempo e fa solo 35.
Qualche indizio da darmi…?
(allego qua il codice a cui sono arrivato)
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
// constraints
#define MAXN 100000
// input data
int N, i, j;
int S[MAXN], C[MAXN+1];
int R[MAXN];
vector<pair<int,int>> v;
void binaryInsertion(int el, int i, int n){
int s, e;
s = 0;
e = n;
while(s<e){
if(el>v[(e+s-1)/2].first){
s = (e+s-1)/2+1;
}else{
e = (e+s-1)/2;
}
}
if(s==n){
v.push_back(make_pair(el,i));
}else{
v.insert(v.begin()+s,make_pair(el,i));
}
}
int main() {
freopen("input.txt", "r", stdin);
(1 == scanf("%d", &N));
for(i=0; i<N; i++)
(1 == scanf("%d", &S[i]));
for(i=1; i<=N; i++)
(1 == scanf("%d", &C[i]));
// insert your code here
int maxindex;
R[0] = 1;
v.push_back(make_pair(1,0));
for(i=1;i<N;++i){
maxindex = i;
for(j=i-1;j>=0;--j){
if(S[i]>S[v[j].second] || S[i]==C[S[v[j].second]]){
maxindex = v[j].second;
break;
}
}
binaryInsertion(R[maxindex]+1,i,i);
R[i] = R[maxindex]+1;
}
printf("%d\n",v[N-1].first);
return 0;
}
Ottimizza il modo per trovare il massimo
Come da tag, puoi farlo usando una struttura dati
edit: sotto trovi una spiegazione dettagliata, lascio questo messaggio se vuoi solo degli indizi molto generici.
1 Mi Piace
La prima considerazione è che l’inserimento binario è sicuramente più veloce di inserire in coda e poi ordinare, ma rimane comunque lento in quanto il vector supportando random access (quindi poter usare le []) deve comunque riallocare tutti gli elementi successivi a quello inseriti. Quindi nel caso peggiore, quando inserisci un elemento in prima posizione (supponendo che il vettore contenesse prima N elementi) hai comunque un costo di O(NlogN).
La seconda considerazione è che l’approccio in sé non è sufficientemente veloce. Devi cercare di ricondurlo a una LIS.
Esistono vari modi per calcolare la LIS in O(NlogN), in questo caso non è nemmeno necessario calcolare la LIS ma basta la sua lunghezza.
Uno dei metodi, che è quello che si adatta poi meglio a questo problema sfrutta i fenwick-tree.
Definiamo il problema come: Dato un vettore V di N elementi, trovare la lunghezza della Longest-Increasing-Subsequence. Per comodità diciamo che i valori di V sono compresi tra 1 e N (In caso non fosse così, sarebbe necessario mappare i valori del vettore in modo tale che tale proprietà sia rispettata ed anche le relazioni di > >= < <= rimangano corrette).
Come detto in precedenza vogliamo usare un fenwick, che nella sua versione più semplice permette di effettuare tali operazioni:
Quindi vogliamo fare in modo che ft_i (i-esima cella dell’albero) contenga la lunghezza massima di una sotto-sequenza crescente che termina con il valore i.
Si può allora processare in ordine di indice ogni elemento di V e fare:
for x in V:
best = ft.query(x - 1)
ft.update(x, best + 1)
return ft.query(N)
Dove la query ritorna il massimo valore nel prefisso di lunghezza i mentre l’update setta il valore in posizione i ad x.
Quello che stiamo facendo è, per ogni elemento x in V:
- Trova la lunghezza l maggiore di una sotto-sequenza crescente che termina con un valore y con y < x, ciò appunto corrisponde a fare la query di massimo sul prefisso x - 1
- Settare la lunghezza della sotto-sequenza crescente più lunga che termina con il valore x ad l + 1, il +1 è dovuto all’inserimento in coda dell’elemeto x
Infine troveremo la lunghezza della LIS in query(N) che restituisce la lunghezza maggiore di una sotto-sequenza crescente che termina con un elemento minore o uguale a N. Questo è il codice che implementa tale soluzione.
Ora devi cercare di capire anche come tenere in considerazione il fatto che quando costruiscila sequenza richiesta x: x_{i-1} potrebbe essere maggiore di x_i nel caso in cui ne fosse il suo complementare.
Grazie mille, penso di aver capito come procedere ora