booklet_cesena.pdf (473.4 KB)
Edoardo e la lotteria è stato una bella sfida riuscire a risolverlo ahah comunque bei problemi 
Io sto provando ora a risolverli senza leggere le soluzioni… Sto partendo da Lotteria e credo di aver trovato una soluzione O(n*m) che non mi funziona in locale (pazienza… ora vedo di debuggare).
Comunque da dove escono questi problemi? o.o
Gli altri sono più o meno difficili di questo? (ammetto che quel m=200k mi aveva spiazzato all’inizio >_<)
1 Mi Piace
ahaha ovvio che anchio li risolvo senza leggere le soluzioni 
Secondo me i più difficili sono lotteria e albero
Comunque da dove escono questi problemi? o.oGli altri sono più o meno difficili di questo? (ammetto che quel m=200k mi aveva spiazzato all'inizio >_<)VashTheStampede
Trovati in giro su internet... lotteria è degli allenamenti per le ACM ICPC della Sapienza.
Secondo me i più difficili sono lotteria e alberoConta che erano due gare (5 problemi per gara) e i problemi erano ordinati per difficoltà crescente (ma poi in gara l'ordine si è rivelato abbastanza errato), quindi la difficoltà in teoria sarebbe 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, rispetto all'indice che vedete nel booklet....Carlo
(lo so, dare difficoltà 5 a viaggio è imbarazzante :P, diciamo che tutto sommato la gara2 era più difficile della gara1).
Secondo me i più difficili sono lotteria e alberoBoh quello dell'albero l'ho letto e ho il vuoto hahaha, ne faccio un paio degli altri e al massimo quello lo faccio domani prima delle COCI come riscaldamento x__xCarlo
In realtà io lotteria ho fatto una soluzione assurda con formula matematica in NlogM, ecco perché mi era sembrato difficile ahah ora che leggo la soluzione ufficiale è molto più semplice. Albero sono 50 punti easy, il problema è il subtask 3 D::
UPD: Scherzavo in realtà non so che complessità sia perché è M/2 + M/4 + M/8 … e così via per N-1 volte…
UPD: Scherzavo in realtà non so che complessità sia perché è M/2 + M/4 + M/8 ... e così via per N-1 volte...Se n = log2(m) allora m/2+m/4+m/8+...+m/m = m(1/2 + 1/4 + 1/8 + ... + 1/m) --> m*1 = O(m).Carlo
Se n < log2(m) è comunque O(m).
EDIT: ah, ma forse dicevi per n-1 volte nel senso di ripetuto n-1 volte... in tal caso, per lo stesso motivo, O(mn).
Grazie del chiarimento, comunque intendevo la somma di M/(2^i) con i che va da 1 a N-1
In tal caso è proprio O(m), quindi è meglio della soluzione ufficiale… not bad :P, cioè, quando i supera il logaritmo in base 2 di M l’algoritmo si ferma, no?
In realtà non ho messo questo if… ma comunque non penso che cambi molto dal momento che N <= 20…
E in ogni caso m/2 + m/4 + m/8 + … + 1 + 1 + 1 + 1 (n addendi, con n > log2(m)) sarebbe O(m + n) che è comunque meglio di O(mn).
Perfetto 
Che poi a pensarci bene se n > log2(m) la risposta è sempre zero xD, quindi si potrebbe mettere direttamente un if all’inizio in tutte le soluzioni… in questo modo O(m²n) ed O(mn) sono in realtà rispettivamente O(m² log m) e O(m log m), mentre la tua è O(m)