Problema torri

Aiuto
21
non colgo una valida struttura ricorsiva per poterlo fare.

Luke

Prova a risolvere prima il problema della dieta di poldo (usando la guida), dopo aver sottoposto correttamente una soluzione per poldo prova a risolvere anche torri.

L'equazione di ricorrenza che devi usare per torri è praticamente identica a quella di poldo (infatti, poldo è duale a torri quando i costi di demolizione sono tutti uguali).
22

Ottimo grazie a tutti, vi offrirei volentieri una birra!

23
Ottimo grazie a tutti, vi offrirei volentieri una birra!

Luke

perché non ti ho aiutato? D:
24

Ma ora pare che ci siano modi migliori no? un bel bis per aiutini pure su come migliorare le cose. Mi interessa soprattutto quello con cui si guarda solo la prima torre!

25
Ma ora pare che ci siano modi migliori no? un bel bis per aiutini pure su come migliorare le cose. Mi interessa soprattutto quello con cui si guarda solo la prima torre!

Luke

Sicuro che si possa fare?
26
Ma ora pare che ci siano modi migliori no? un bel bis per aiutini pure su come migliorare le cose. Mi interessa soprattutto quello con cui si guarda solo la prima torre!

Luke

Non credo si possa fare...
27

Si può abbassare la complessità a O(N log N) con l’utilizzo dei fenwick tree. Di meglio non credo si possa fare

28

Scusatemi potete spiegare a una povera anima innocente come posso usare il fenwick tree per arrivare a O(N log N)? Ci ho pensato un po’ ma non mi viene proprio in mente…

29

come hai fatto 0 secondi con n^2 ?

30
come hai fatto 0 secondi con n^2 ?

Luke

I limiti del task sono bassi, quindi non c’è molta differenza nella pratica tra la soluzione n^2 e n \log n.

Anzi, non mi sorprenderei se la quadratica fosse addirittura più veloce, prendi ad esempio il problema del prodotto tra matrici: la soluzione banale è O(n^3), mentre la soluzione O(n^k) più veloce conosciuta è O(n^{2.3728639}). Nonostante la cubica sia asintoticamente più lenta ha una “costante nascosta” molto bassa, contrariamente alla soluzione asintoticamente migliore che ha una costante nascosta talmente alta che, per apprezzare la sua velocità, dovresti prendere matrici troppo grandi per essere gestite con un computer :stuck_out_tongue:

31
Scusatemi potete spiegare a una povera anima innocente come posso usare il fenwick tree per arrivare a O(N log N)? Ci ho pensato un po' ma non mi viene proprio in mente...

cyanpencil

L'idea è sostanzialmente la stessa: alla i-esima iterazione puoi ricavare la soluzione ottima per la sottosequenza formata dalle prime i torri a partire dalle soluzioni precedenti (questa è almeno l'implementazione bottom-up, con la top-down non cambia molto).

Ora, il passaggio critico è proprio nella ricerca del massimo. Se questa operazione richiede un tempo lineare, l'algoritmo finale avrà complessità quadratica. Con il Fenwick Tree può invece essere svolta in tempo logaritmico, tuttavia l'implemantazione non è proprio intuitiva.

Prova a risolvere il problema seguente con complessità NlogN, usando Fenwick: dato un array di N interi, determinare la lunghezza della massima sottosequenza crescente (Longest increasing subsequence) in esso contenuta. La soluzione per Torri è praticamente identica... ;)

32

Usando l’agoritmo greedy più binary search al posto del Fenwick, la LIS può essere trovata sempre in nlogn ma più velocemente nel concreto(cotte con il fenwick non mi faceva 100 qui sul cms).

33
Usando l'agoritmo greedy più binary search al posto del Fenwick, la LIS può essere trovata sempre in nlogn ma più velocemente nel concreto(cotte con il fenwick non mi faceva 100 qui sul cms).

EmanueleRossi

Non sempre la LIS è la soluzione migliore ;)
34
Si può abbassare la complessità a O(N log N) con l'utilizzo dei fenwick tree. Di meglio non credo si possa fare

mark03

Una soluzione lineare non esiste, la soluzione migliore è usando un RangeTree ( soluzione piuttosto carina a mio parere!! ).
Sicuro che si possa fare con i fenwick tree?
35
come hai fatto 0 secondi con n^2 ?

Luke

I limiti del task sono bassi, quindi non c'è molta differenza nella pratica tra la soluzione n2 e nlogn. Anzi, non mi sorprenderei se la quadratica fosse addirittura più veloce, prendi ad esempio il problema del prodotto tra matrici: la soluzione banale è O(n3), mentre la soluzione O(nk) più veloce conosciuta è O(n2.3728639). Nonostante la cubica sia asintoticamente più lenta ha una "costante nascosta" molto bassa, contrariamente alla soluzione asintoticamente migliore che ha una costante nascosta talmente alta che, per apprezzare la sua velocità, dovresti prendere matrici troppo grandi per essere gestite con un computer :P

wil93

É possibile mettere un torri2, stesso problema ma con n dell'ordine dei 100k?
Giusto cosi testiamo le varie soluzione O(n log n) ;)

36
Usando l'agoritmo greedy più binary search al posto del Fenwick, la LIS può essere trovata sempre in nlogn ma più velocemente nel concreto(cotte con il fenwick non mi faceva 100 qui sul cms).

EmanueleRossi

Non sempre la LIS è la soluzione migliore ;)

mark03


Sì, in effetti è una LDS (il cui costo va poi sottratto a quello totale)...
37
Usando l'agoritmo greedy più binary search al posto del Fenwick, la LIS può essere trovata sempre in nlogn ma più velocemente nel concreto(cotte con il fenwick non mi faceva 100 qui sul cms).

EmanueleRossi

Non sempre la LIS è la soluzione migliore ;)

mark03

Mi sa che ema non si riferiva specificamente al problema "torri" ma alla LIS in generale
38
Mi sa che ema non si riferiva specificamente al problema "torri" ma alla LIS in generale

Degiac

Esiste una implementazione supercorta della LIS: 
set<int> S ; S.clear();
set<int>::iterator it ;
for( int i = 0 ; i < N ; i++ )
{
    it = S.lower_bound( V[i] );
    if( it != S.end() ) S.erase( it );
    S.insert( V[i] );
}
39

Io l’ho implementata praticamente uguale, ma con i vector (così quando devo sostituire lo fa in O(1) e non in O(logN))

40

Come fai con i vector ad inserire un elemento nel giusto ordine?
( ovvero quale è l’equivalente dell’ S.insert( V[i] ) ? )