Come saprai la gara è stata estesa fino al 17 (per chi ha esigenze particolari e per chi non sapeva della gara). Tuttavia avevamo detto che oggi avremmo aggiunto i task per gli allenamenti (e pubblicato le soluzioni), quindi ecco:
booklet_pre_oii.pdf (1.1 MB)
Questo porta quindi alla pubblicazione di una classifica parziale (ovvero “come appariva” la classifica alla fine della gara “non estesa”). Eccola:
Tra poco i problemi saranno visibili qui sul correttore di allenamento.
15esimo… Credevo molto ma molto peggio 
Bravi tutti 
Come avete trovato i problemi?
Ci farebbe piacere qualche commento costruttivo per il futuro!
IMHO, trasporti è assurdo. Gli altri tre sono fattibili, forse i primi due un po’ troppo facili (anche se il secondo sembra che abbia dato problemi a più di una persona :p)
Come avete trovato i problemi?A parte che ho fatto schifo hahaha
Ci farebbe piacere qualche commento costruttivo per il futuro! :DGaspare
IMHO, trasporti è assurdo.Pienamente d'accordo! Ci ho speso quasi 3 ore e mezza sul 4 (senza tra l'altro prendere nemmeno un punto :P) !Degiac
I primi due sono molto semplici, il terzo non è complicato ma è molto difficile prendere il 100/100. Il quarto invece è molto difficile da implementare in gara, ma la soluzione è comunque abbastanza capibile (a seguito della gara, durante credo che sia improbabile prendere 100 (o quasi ahahaha))
Ci ho perso la stessa quantità di tempo lolIMHO, trasporti è assurdo.Pienamente d'accordo! Ci ho speso quasi 3 ore e mezza sul 4 (senza tra l'altro prendere nemmeno un punto :P) !Degiac
Delfad0r
Complimenti per i problemi, veramente carini l’ultimo era più difficile di quello che pensavo, dato che non ho avuto il tempo di mettermici seriamente.
Guardate che non sono stati aggiornati i testcase per trasporti, la mia soluzione per nulla ottimale prende ancora 100/100
Guardate che non sono stati aggiornati i testcase per trasporti, la mia soluzione per nulla ottimale prende ancora 100/100Ti stai facendo troppi nemici, occhio che a Fisciano ti buggano le soluzioni.mark03
Mi porto la scorta, non si sa mai :/Guardate che non sono stati aggiornati i testcase per trasporti, la mia soluzione per nulla ottimale prende ancora 100/100Ti stai facendo troppi nemici, occhio che a Fisciano ti buggano le soluzioni.mark03
VashTheStampede
Loro hanno un MiliziaMi porto la scorta :/Guardate che non sono stati aggiornati i testcase per trasporti, la mia soluzione per nulla ottimale prende ancora 100/100Ti stai facendo troppi nemici, occhio che a Fisciano ti buggano le soluzioni.mark03
VashTheStampede
mark03
Guardate che non sono stati aggiornati i testcase per trasporti, la mia soluzione per nulla ottimale prende ancora 100/100Sì ne siamo al corrente... appena Gaspare mi passa il nuovo generatore aggiorno i testcase :)mark03
Aggiornati i test case di trasporti! 
La tua soluzione adesso fa 55/100 
Comunque per i più curiosi questo problema l’ho pensato dopo aver scoperto
l’Heavy-Path decomposition ( che è la prima soluzione da 100 che abbiamo trovato, quella che vi abbiamo mostrato è di Milizia ed è più facile da capire ).
Visto la complessità della tecnica abbiamo deciso di dare solo 10 punti in più per la vera soluzione e abbiamo puntato di più sugli altri subtask.
Il subtask 2 si risolveva con due if per ogni query ( e infatti valeva 7punti )
Il subtask 3 era pensato per implementare un RMQ con un segment tree ( o similari )
Il subtask 4 una DFS dalla radice agli altri nodi memorizzandosi il valore massimo incontrato.
Il subtask 5 l’avevo pensato per far implementare una union-find, anche se ho visto che molti hanno trovato una soluzione alternativa con una colorazione dell’albero.
Il subtask 6 bastava una qualsiasi soluzione cubica ( es. una versione modifica del floyd-warshall ).
Il subtask 7 ( e 6 ) una soluzione quadratica, la stessa idea del ST4 applicata però ad ogni nodo.
A dire la verità il primo a proporre la soluzione che poi è diventata “ufficiale” è stato Mazzetto
Qui potete trovare una spiegazione dell’heavy-light-decomposition
