ois_calculator
Di recente è stata fatta una segnalazione circa il task suddetto.
Ho riguardato la cartella dell problema (che risale a prima ancora che io fossi un partecipante alle OII) e ho effettivamente riscontrato alcuni problemi.
Bug nella soluzione ottimale
La soluzione usata per generare gli output ufficiali non provava entrambi gli ordini per le operazioni,
generando output subottimali su quasi il 60% dei casi possibili. Stiamo rivalutando le sottoposizioni contro gli output corretti, alcune sottoposizioni potrebbero perdere punti.
Comunque al momento battendo la soluzione ufficiale si ottenevano 100 punti.
Bug nel correttore
Il correttore era rotto nel caso in cui dei risultati intermedi dell’espressione fossero negativi. Ho ritenuto che la soluzioni migliore in questo caso fosse semplicemente impedire risultati intermedi non positivi, che generano anche numerose ambiguità semantiche.
Problemi concettuali
Il problema, così come era presentato, è in realtà al limite di ciò che è matematicamente risolvibile con strumenti odierni. La difficoltà sorge dal fatto che è possibile che l’espressione minima per numeri piccoli abbia risultati intermedi enormi. Il correttore ovvia(va) a questo rifiutando risultati intermedi più grandi di un miliardo in valore assoluto, senza alcuna menzione nel testo.
La limitazione è stata mantenuta, perché altrimenti il problema esula dall’interesse della programmazione competitiva, ma è ora esplicitata nel testo.
Problema originale
Secondo me il problema originale, cioè senza la limitazione che i risultati intermedi siano al più 10^9 è risolvibile, dato abbastanza impegno.
Ho iniziato un progetto di formalizzazione per trovare gli output dimostrabilmente ottimali, senza limiti sui valori intermedi e vi terrò aggiornati in merito.