Panagramma time limit stretto


#1

Si potrebbe alzare il time limit di pangramma? Una soluzione lineare va fuori tempo massimo.


#2

Forse già lo hai fatto ed è veramente troppo stretto il tempo, ma, durante la spiegazione dei problemi delle olimpiadi (a Matera) dissero che per ottenere 100/100 in quel problema l’unico modo era calcolare con un altro programma esterno (e quindi offline) tutti gli inversi modulari e dare al codice sorgente direttamente il vettore (o qualsiasi altra struttura, in realtà) con gli inversi calcolati


#3

A me non rimane comunque nel TL, anche con quell’accorgimento.


#4

Io ho dovuto subire questa tortura in gara. :cry:
Dopo la fine della gara mi hanno spiegato che una soluzione \mathcal O(N+MOD\log MOD) dovrebbe prendere 98 punti mentre la soluzione modello ha complessità \mathcal O(N+MOD). Uno dei modi per ottenere quella complessità è precalcolarsi gli inversi modulari sul proprio pc ma esiste comunque un’altra soluzione che permette di calcolare tutti gli inversi modulari in tempo lineare.