Salve, vi chiedo gentilmente di darmi qualche indizio per risolvere ois_workout. Quale parte di teoria dovrei studiare per affrontare problemi di questo genere? Tra i tag del problema c’è binary search, ma dove andrebbe applicata? Ho visto che è un problema che non proprio tutti hanno risolto. Perdonatemi il disturbo.
Il problema proposto è NP e quindi non esiste una soluzione corretta che risolve il problema con le assunzioni proposte in tempi sensati. Quindi quello che devi trovare è un’euristica, ossia una soluzione non necessariamente corretta che però ha tempi di esecuzione che rimangono nel tempo limite. In gara (finale ois 2019) non fu risolto completamente da nessuno e questi sono i relativi punteggi. Solitamente i problemi del genere vengono aggiunti proprio come tiebreakers.
La domanda che sorge spontanea è dunque come hanno fatto a creare gli output corretti per i vari testcases? La risposta è che gli output della piattaforma non garantiscono la loro correttezza (ossia potrebbero esserci output minori) e quando valutano la loro soluzione la confrontano con quella che hai trovato tu. [Piccolo easter egg: se non ricordo male se tu trovi una permutazione che produce un output minore del loro allora nella colonna “Dettagli” di quel testcase ti viene detto. Ma quando controllai qualche mese fa non c’erano soluzioni migliori delle loro] .
Per quanto riguarda la binary search è un tag che ho aggiunto io in quanto la mia euristica la usa (in realtà penso che la usino quasi tutte le euristiche che prendono punteggio pieno).
Per concludere quello che ti viene dunque richiesto e scrivere una soluzione che si avvicini il più possibile alla risposta corretta. Per questo genere di problemi non c’è un approccio fisso, in generale si è nella situazione in cui provare ogni possibile soluzione (in questo caso ogni possibile combinazione) è mooolto lento, e quindi devi cercare l’euristica migliore.
5 Mi Piace