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.
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?
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?
Se ho interpretato bene il testo, questo problema è noto come Bin Packing Problem che è una generalizzazione del k-partition problem, inoltre questo task è una variante del Job Shop Problem. 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.
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.
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.
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.
)
).