Skyline 72% (sparse table)

Sto provando a scrivere la funzione “valuta” del problema skyline con una Range Maximum Query con sparse table, ma supera i limiti di memoria (non di tempo).

https://pastebin.com/t0bTJKyW

Ho provato a usare sia array/matrici, sia vettori dinamici (nella parte commentata).
Per risolvere il problema pensavo a un modo per evitare di copiare il vettore di partenza in globale, ma in teoria non dovrei risparmiare così tanta memoria…
Forse devo provare con un altro metodo?

Ciao, purtroppo penso che non si possa usare un approccio con sparse table in quanto con N \le 10^6, devi memorizzare fino a Nlog(N) = 10^6 \times 20 = 2 \times 10^7 interi.
Siccome ti servono interi a 32 bit, l’utilizzo di memoria sarà circa 4 \times 2 \times 10^7 \approx 80 MiB, che i supera 64 MiB concessi per risolvere il problema.

PS: Cerca di ragionare sul tipo di RMQ a cui ti serve rispondere, è davvero necessaria una struttura dati per calcolare ogni possibile RMQ? :slight_smile:

3 Mi Piace

Comunque, puoi modificare la Sparse Table per costruirla (ad esempio) usando metà della memoria (controllando però il doppio di intervalli per ogni query).
Anche se tipicamente non è un’idea particolarmente utile :slight_smile:

1 Mi Piace

Se ho capito bene, l’idea migliore sarebbe usare un segment tree?

No, usare un segment tree dovrebbe prendere punteggio pieno ma non è l’idea migliore :slight_smile:
Le RMQ che devi calcolare sono tutte del tipo (0, i) o (i, N-1).

Il primo tipo sono prefissi e il secondo tipo suffissi, riesci a calcolarli in O(N) ?

2 Mi Piace

Ok, ho fatto 100% memorizzando tutti i prefissi e i suffissi in due array separati:
https://pastebin.com/7m0NrvDb

Intendevi una cosa del genere, vero?
Grazie mille

1 Mi Piace

Direi proprio di sì, ottimo :wink:

1 Mi Piace