Array partition 90/100

Aiuto
1

Sto provando a fare array partition (in gara ho fatto 90), intuendo che non è sicuramente la soluzione migliore(infatti da 90) fare i due for con complessità (n^2), allora ho pensato di farlo in questo modo:
http://pastebin.com/w9r6s252

io di fatto per i valori prima dalla prima meta calcolo quanti ce ne sono piu grandi prima di lui con un for, per calcore quanti ce ne sono piu piccoli dopo di lui invece di fare un for calcolo la differenza fra i valori che ho analizzato con il primo for e quanti ne ho contati con il cont(quindi i piu grandi di lui) cosi io di fatto trovo quanti ce ne erano piu piccoli prima, per trovare quanti ce ne sono piu piccoli dopo mi basta fare quanti ce ne sono piu piccoli in totale(quindi il numero che sto anallizando meno 1) meno quanti piu piccoli ne ho prima. cosi di fatto il secondo for non lo faccio da 0 a n ma da 0 a i

per esempio se ho un array di 100 000 elementi e devo calcolare gli elementi sbagliati per l elemento in posizione 1 mi basta scorrere solo la prima casella.

a quanto pare però non è la soluzione ottimale(fallisce 2 casi), come posso fare?

2

Devi trovare un modo più rapido di trovare tutti i numeri maggiori/minori del numero che stai considerando, solo tra quelli a sinistra/destra del numero. Un fenwick non sarebbe una cattiva idea

2 Mi Piace
3

Cioè? Controllare la somma tra 0 e i e tra i+2 e N-1 con il vettore originale e uno ordinato? In questo modo verifico subito se ho elementi disordinati, ok, ma non quanti.
Avevo cercato un po’ e ho trovato una soluzione che usa un albero AVL, ma ritengo che ciò non sia nelle intenzioni dell’autore quindi la escludo.

4

Se considerassi una versione semplificata del problema, saresti in grado di risolverlo?
Ad esempio, se il problema chiedesse di trovare, per un numero specifico, il numero di elementi maggiori o uguali di questo alla sua sinistra? E se lo chiedesse per tutti gli elementi?
Nota come risolvendo due volte quest’ultimo problema, una volta per trovare gli elementi a sinistra maggiori di ogni numero e una per trovare gli elementi a destra minori di ogni numero, puoi risolvere il problema originario.
Ora resta solo da capire come risolvere questo problema più semplice in un tempo decente. La soluzione ovvia esegue O(N^2) operazioni, iterando per ogni numero su tutti gli elementi a destra/sinistra di questo, puoi trovare un modo per eseguirne O(NlogN)?

1 Mi Piace
5

non sapevo dell esisitenza di questa “struttra”, ho cercato ma torvando solo siti in inglese non ho capito bene dove è il guadagno di tempo. se non ho capito male(cosa che non sarebbe cosi strana :smile: ) lui lavora con i numri in biniario e tiene contro del numero binario che si forma prendendo le ultime cifre (partendo da sinistra) inizia a contare dall’ultimo 0:
quindi per esempio il 12 che in binario è 1100 diventa 4 perche diventa 100 ma non capisco a cosa serve e come guadagni tempo

6

Quello a cui ti stai riferendo tu è l’indicizzazione che si usa nel fenwick (ovvero come ottenere gli elementi richiesti per determinate operazioni). Prima di questo dovresti farti un’idea di come funziona un fenwick e del guadagno in complessità che permette.
L’idea di fondo è quella di costruire, dato l’array in ingresso A, l’array delle somme prefisse B, nel quale in ogni posizione i è salvata la somma degli elementi A0, A1, …, Ai. Faccio un paio di esempi:

A: {1, 2, 3, 4, 5, 6}
B: {1, 3, 6, 10, 15, 21}

A: {1, 0, 0, 1, 2, 1}
B: {1, 1, 1, 2, 4, 5}

Se l’array A non cambia durante l’esecuzione del programma possiamo ottenere in tempo costante la somma di una qualsiasi sottosequenza contigua di A (ovvero la somma di tutti gli elementi compresi in un intervallo dato). Se prendiamo un intervallo [i, j] basterà infatti calcolare B[j] - B[i - 1] per ottenere la somma A[i] + A[i + 1] + ... + A[j - 1] + A[j]. L’unico problema di questo approccio è che per aggiornare l’array A bisogna anche ricalcolare tutte le somme prefisse, e questa operazione prende tempo lineare - O(N).

Il fenwick parte dall’idea delle somme prefisse ma aggiunge la possibilità di modificare A durante l’esecuzione del programma mantenendo comunque un tempo di esecuzione rapido. Per fare questo salva una versione compressa di un albero binario (e questa potrebbe essere l’idea dell’AVL trovata da @erixstep) in modo che sia per ottenere la somma prefissa [0, i] sia per modificare un valore in A, siano necessarie ~logN operazioni.

Ti segno un paio di link interessanti:
https://notes.tweakblogs.net/blog/9835/fenwick-trees-demystified.html - in Inglese, ma visualizzato meglio
https://digit.cms.di.unipi.it/resources/fenwick.pdf

Dario

p.s. Nell’esempio che hai fatto tu dovresti togliere il bit meno significativo settato a uno, quindi da 12 (1100) passi prima a 8 (1000) e poi a 0 (0000)

3 Mi Piace
7

Ho capito la tua risposta. Praticamente la soluzione è così banale, mi chiedo come io abbia fatto a non pensarci prima!

Praticamente la risposta è data da questo ragionamento chiave, che non avevo fatto: che i numeri sono sequenziali.

8

Scusate ma non ho capito come utilizzare la struttura di somme prefisse in questo problema: che vantaggio dovrebbe portarmi? perché?

9

Ti consiglio di guardare questo post:

Comunque se hai poca dimestichezza con gli alberi binari, esiste una soluzione molto più intuitiva che fa uso di una struttura dati della STL.

2 Mi Piace
10

@bortoz di che struttura dati stavi parlando ?

11

Mi riferivo a policy based data struct, che è una struttura dati con le stesse funzionalita di un std::set e inoltre ha due funzioni molto carine, ovvero:

  • find_by_order che ritorna un iterator all’i-esimo elemento
  • order_of_key che ritorna il numero di elementi con chiave minore di k
2 Mi Piace