# Gara ABC 2018 (26/05/2018) **URL:** \ **Category:** Olimpiadi\ **Created:** [19 Maggio 2018, 8:01am UTC](https://forum.olinfo.it/t/gara-abc-2018-26-05-2018/5225 "2018-05-19T08:01:04Z")\ **Posts on this page:** 14\ **Page:** 1
**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\ **Post date:** [19 Maggio 2018, 8:01am UTC](https://forum.olinfo.it/t/gara-abc-2018-26-05-2018/5225/1 "2018-05-19T08:01:04Z")
Ciao a tutti! Nell’ambito del progetto “Olimpiadi di Informatica”, l’ITIS Paleocapa di Bergamo organizza per il sesto anno consecutivo la gara di informatica ABC. Il proposito è che la gara possa essere di allenamento nel periodo che intercorre tra la selezione territoriale di aprile e le successive gare autunnali (finale nazionale OII e inizio campionato OIS). Anche quest’anno la gara verrà svolta in due modalità: online, aperta a chiunque voglia partecipare, e onsite, presso l’ITIS Paleocapa di Bergamo. L’appuntamento è per **sabato 26 maggio 2018** alle ore 14:30 in rete o presso l’ITIS Paleocapa. I problemi saranno di difficoltà intermedia, con alcuni subtask particolarmente semplici e adatti anche a chi è alle prime armi. Verrà utilizzata la modalità con _grader_ per permettervi di prenderne confidenza, poiché sarà quella con cui si svolgerà anche la finale nazionale delle OII di settembre. La pagina di partenza per la **registrazione** e l’accesso alla **piattaforma di gara** è [abc.chiodini.org](http://abc.chiodini.org). In bocca al lupo sin d’ora! ---
**Author:** ![edomora97](https://forum.olinfo.it/user_avatar/forum.olinfo.it/edomora97/32/712_2.png) [@edomora97](https://forum.olinfo.it/u/edomora97)\ **Post date:** [19 Maggio 2018, 8:27am UTC](https://forum.olinfo.it/t/gara-abc-2018-26-05-2018/5225/2 "2018-05-19T08:27:47Z")
---
**Author:** ![Tredici](https://forum.olinfo.it/user_avatar/forum.olinfo.it/tredici/32/2637_2.png) [@Tredici](https://forum.olinfo.it/u/Tredici)\ **Post date:** [26 Maggio 2018, 3:39pm UTC](https://forum.olinfo.it/t/gara-abc-2018-26-05-2018/5225/3 "2018-05-26T15:39:01Z")
Ciao a tutti, bella gara! Grazie a tutti quelli che l’hanno organizzata! (Si potrebbe gentilmente sapere come si faceva il problema 2? 😅) ---
**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\ **Post date:** [27 Maggio 2018, 10:43am UTC](https://forum.olinfo.it/t/gara-abc-2018-26-05-2018/5225/4 "2018-05-27T10:43:54Z")
A partire dal solito link ([abc.chiodini.org](http://abc.chiodini.org)) sono ora disponibili la classifica finale e il booklet con i testi dei problemi. Tra non molto conto di caricarli anche sulla piattaforma (ma non garantisco avverrà nell’immediatezza…). ---
**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\ **Post date:** [27 Maggio 2018, 10:45am UTC](https://forum.olinfo.it/t/gara-abc-2018-26-05-2018/5225/5 "2018-05-27T10:45:47Z")
> [@Tredici](#): > > (Si potrebbe gentilmente sapere come si faceva il problema 2? 😅) Immagino ti riferisca a mining… Fissato il numero di GPU (eventualmente poi li puoi provare tutti), riesci a capire se è possibile terminare entro il minuto M usando esattamente _quel_ numero di schede video? ---
**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\ **Post date:** [27 Maggio 2018, 11:39am UTC](https://forum.olinfo.it/t/gara-abc-2018-26-05-2018/5225/6 "2018-05-27T11:39:39Z")
Facendo così (potrei sbagliarmi) si ottiene il k-partition problem che è NP-arduo. Qualche indizio in più? ---
**Author:** ![Tredici](https://forum.olinfo.it/user_avatar/forum.olinfo.it/tredici/32/2637_2.png) [@Tredici](https://forum.olinfo.it/u/Tredici)\ **Post date:** [27 Maggio 2018, 3:35pm UTC](https://forum.olinfo.it/t/gara-abc-2018-26-05-2018/5225/7 "2018-05-27T15:35:11Z")
Sì mi riferivo a mining, per trovare il minimo numero di GPU sufficienti a gestire tutto il carico è immediato che si possa usare una sorta di ricerca binaria se ogni volta ci si riduce a verificare se x schede siano sufficienti ma non ho idea di come ciò si possa fare in modo efficiente. P.S.: (non è strettamente legato a come si potrebbe risolverlo) io il problema l’ho reinterpretato in un contesto diverso: supponiamo di avere N carichi da trasportare ognuno di Q[i] quintali (i carichi non possono essere divisi in parti più piccole), vogliamo determinare il minimo numero di tir in grado di trasportare M quintali al massimo necessari per trasportare tutti i carichi che dobbiamo muovere. Rigirato così il problema mi sembra abbastanza importante dal punto di vista economico e dei trasporti e quindi vorrei chiedere se da quello che sapete è “famoso” e quindi ci sono degli articoli (o pagine di wikipedia) in proposito come per quello del commesso viaggiatore? ---
**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\ **Post date:** [27 Maggio 2018, 4:51pm UTC](https://forum.olinfo.it/t/gara-abc-2018-26-05-2018/5225/8 "2018-05-27T16:51:29Z")
Se ho interpretato bene il testo, questo problema è noto come [Bin Packing Problem](https://en.wikipedia.org/wiki/Bin_packing_problem) che è una generalizzazione del [k-partition problem](https://en.wikipedia.org/wiki/Partition_problem), inoltre questo task è una variante del [Job Shop Problem](https://en.wikipedia.org/wiki/Job_shop_scheduling). Tutti questi problemi sono NP-ardui, mentre il problema di determinare se è possibile terminare entro M minuti utilizzando k schede video è NP-completo. Quindi, a meno che non mi sfugga qualcosa, @lucach ha appena dimostrato che P = NP. 😅 ---
**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\ **Post date:** [27 Maggio 2018, 5:36pm UTC](https://forum.olinfo.it/t/gara-abc-2018-26-05-2018/5225/9 "2018-05-27T17:36:05Z")
No, in realtà hai approfondito ben più tu di me. Credo ci sia un fondamentale misunderstanding del testo, essenzialmente per una (grave) colpa del sottoscritto. In tutte le formulazioni iniziali “interne”, davo per scontato che fosse chiara la sequenzialità delle operazioni di mining - cosa che, mi accorgo ora leggendo i vostri commenti, non era affatto desumibile dal testo. Nello scegliere all’ultimissimo momento la metafora per il task, ho sottovalutato il fatto che quella scelta decisamente non si presta a questa interpretazione. Per lo stesso motivo, non ho aggiunto un’assunzione in merito. Inoltre, l’organizzare questa gara a fine maggio, momento culmine dell’anno per vari impegni, non ha certo giovato alla mia lucidità mentale. Durante la gara sono rimasto infatti molto sorpreso dai punteggi su questo task, ma stavo contemporaneamente sistemando alcuni bug della piattaforma (utilizzo questa gara anche per testare la versione “master” della piattaforma di correzione) e non ho avuto abbastanza energie per indagare a fondo anche su questo problema. Se vogliamo trarre una morale da questa breve e triste storia, questo caso dimostra ancora una volta come sia essenziale durante lo sviluppo di un problema farlo risolvere a più persone in modalità “blind” (ovvero, senza alcuna informazione pregressa sul task). Mi dispiace davvero tanto avere prodotto un testo senza questa informazione così essenziale e vi chiedo anche scusa per le eventuali arrabbiature che immagino vi possa aver provocato durante la gara. (Spero che, almeno per i più bravi tra voi, queste note dolenti siano almeno parzialmente compensate dall’avervi fatto involontariamente approfondire alcuni tra i più interessanti problemi di ottimizzazione / ricerca operativa 😇). **tldr** : Le criptovalute vanno minate in ordine; mea culpa per la mancata specifica nel testo; sorry, sorry and sorry. ---
**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\ **Post date:** [27 Maggio 2018, 5:45pm UTC](https://forum.olinfo.it/t/gara-abc-2018-26-05-2018/5225/10 "2018-05-27T17:45:25Z")
Sono curioso, è possibile risolvere il problema per come è presentato con le stesse assunzioni? (Onestamente non penso) ---
**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\ **Post date:** [27 Maggio 2018, 5:52pm UTC](https://forum.olinfo.it/t/gara-abc-2018-26-05-2018/5225/11 "2018-05-27T17:52:01Z")
> [@frakkiobello](#): > > è possibile risolvere il problema per come è presentato con le stesse assunzioni? Risolverlo in tempo polinomiale vuol dire dimostrare che P = NP. Esistono algoritmi euristici con una complessità lineare o linearitmica, ma non è certo che diano una soluzione ottimale. > [@lucach](#): > > Le criptovalute vanno minate in ordine Intendi che una scheda video può minare solo un sottoinsieme contiguo di criptovalute? ---
**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\ **Post date:** [27 Maggio 2018, 5:53pm UTC](https://forum.olinfo.it/t/gara-abc-2018-26-05-2018/5225/12 "2018-05-27T17:53:57Z")
> [@bortoz](#): > > Intendi che una scheda video può minare solo un sottoinsieme contiguo di criptovalute? È venuto anche a me lo steso dubbio, ma nel secondo esempio la prima scheda video mina la prima e la terza criptovaluta. 😲 ---
**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\ **Post date:** [27 Maggio 2018, 7:10pm UTC](https://forum.olinfo.it/t/gara-abc-2018-26-05-2018/5225/13 "2018-05-27T19:10:18Z")
> [@bortoz](#): > > Intendi che una scheda video può minare solo un sottoinsieme contiguo di criptovalute? No: intendo che non si può inziare a minare l’i-esima se ce n’è una j-esima, con j \< i, ancora non minata completamente o assegnata attualmente a una GPU. ---
**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\ **Post date:** [27 Maggio 2018, 7:38pm UTC](https://forum.olinfo.it/t/gara-abc-2018-26-05-2018/5225/14 "2018-05-27T19:38:31Z")
Ok grazie della spiegazione, appena saranno usciti i problemi sulla piattaforma proverò a risolvero.