Verso dicembre, grazie a @filippos, ero riuscito a risolvere Got. Da allora un po’ di gente mi aveva chiesto aiuto, ed è grazie a loro che ho avuto la buona volontà di riscrivere parte di quel problema perché usavo poco i globali, e la ricerca binaria era lacunosa e gestivo in modo poco elegante i corner case.
Ho notato che ottenevo tante sfilze di 43/100 di sottomissioni senza motivo, e gli errori erano semplicemente WA.
Facendo un po’ di troubleshooting ho scoperto che: qualsiasi variabile globale si chiami E, K, T, N, fa errare il programma in alcuni task.
Risultato? Se metto le variabili in un namespace prendo 100.
Alla fine di guadagno ne ho ottenuto poco (probabilmente il compilatore è stato abbastanza furbo da non pusharli nello stack e usare qualche puntatore? non ho spulciato nel disassemblato quindi non lo so).
Ciao,
non so bene come mai ciò succeda ma ieri ho scoperto che il compilatore di cms (per C++) in alcuni casi si comporta diversamente da quello che uso io (o quantomeno dalla versione che ho io).
Per esempio con una variabile globale chiamata index (mi sembra) mi dava compilazione fallita su “Trasporti pericolosi” perché il compilatore la associava a una funzione di cstring (o di un’altra libreria del C).
I globali sono buoni e giusti finché non cadono in tentazione.
Il file sottomesso nei problemi preoii, o almeno in questo, è semplicemente appeso. Reputo ciò poco probabile ma possibile
Il linker gioca brutti scherzi (ma lo static non serviva a questo?)
Name pollution nella STL? Strano, dato che nella STL i nomi sono rigorosamente prefissi con il namespace o al massimo con l’underscore. Possibile che ci sia un’inquinamento derivante da altro - ipotesi 1
Che il sorgente venga compilato con -D(qualcosa) e quindi i valori vengono sostituiti con macro?
PS: stavo facendo trasporti proprio ora, ho pensato di applicare LCA usando come radice il centro del grafo, tu hai proceduto così?
E’ possibile e probabilmente sarebbe anche il modo più semplice per realizzare il correttore per i problemi in cui si deve implementare una funzione, anche se mi sembra strano poiché in vari grader le variabili globali sono precedute dalla keyword static.
Innanzitutto chiediamoci se il linker funziona.
Con il mio compilatore non c’è questo problema benché usi using namespce std che ogni tanto ha qualche controindicazione.
Sinceramente non ho idea di cosa possa causare un tale problema.
Risposta al PS: Ho usato il LCA ma l’ho applicato in modo molto più ignorante dal nodo 0 tanto comunque non va in TLE e poi così si risparmia tempo sia per l’algoritmo che trova il centro del grafo sia per il debugging.
Va be’ il compilatore è g++. La versione non la so, invochiamo @wil93 e @veluca per scoprirlo. Lo so perché se guardi gli output di compilazione ottieni gli erorri “à la gcc”. Se non erro, la versione GCC è di major >= 5 per via dei “^” che denotano l’inizio di un warning o di un errore.
Mi pare tu usi msvc++ comunque non c’è di certo name pollution.
Rispondendo a mia volta:
Possibile, probabile, ma nasty. Conoscendo William e Luca, ne dubito un po’ (e spero di non rimanere mai deluso da loro)
Siamo su piattaforma linux. Il linker che abbiamo è sempre ld. Dubitare il funzionamento di ld in un caso del genere è forzato. Comunque, è lo static non rispettato che mi farebbe preoccupare.
La controindicazione avviene se, ad esempio, overrido swap() e poi faccio “using std::swap” oppure il classico “using namespace std”. Se lo swap è fatto per tipi elementari e POD, è plausibile che ci sia un’implementazione subdola che causa pasticci.
È l’ultima teoria sparata in aria.
PSS: Credo che da nodispeciali mi sia fissato a trovare trucchetti con i diametri ovunque
Non avevo mai trovato nulla su -DEVAL, a cosa serve?
PS4: ricorda sempre, per i problemi non servono soluzioni efficienti ma soluzioni che funzionino, anche se non si sa perché come per “Illuminazione di sala”, che è più semplice risolvere che capire.
Al giorno d’oggi non a molto, ma quando l’input era da file lo usavamo per leggere/scrivere da/su file solo quando la soluzione veniva compilata per la valutazione.
Più precisamente, nelle vecchie soluzioni c’era del codice per cui succedeva ciò - in particolare, l’unica cosa che -DEVAL fa è definire una macro (EVAL, appunto) e nel codice C(++) si può decidere di attivare o disattivare del codice a seconda delle macro che sono abilitate (con #ifdef).
PS5: o anche in sponsor, la mia soluzione brute force O(M^2 * N) ha battuto quella O(MlogM) (o qualcos’altro, mi secca calcolare la complessità per bene ora) basata sull’ordinamento della cardinalità, arrivando a fare solo 1,268s semplicemente usando dei bitset (e quindi ridurre di un fattore di \approx \frac{1}{64} grazie all’implementazione sottostante che fa uso dei uint64_t) più cosette sulla cardinalità di sponsor con 1 o 0 atleti
PS6: Ma mathjax è morto? LaTeX non va più da un pezzo, e William in privato non mi ha ancora risposto.
Insieme al problema della classifica non aggiornata da illo tempore, direi che il server è messo benone. Spero che dopo le OII la situazione si sistemi al meglio.
