Ciao a tutti,
Ieri, risolvendo il problema lotteria, mi sono accorto di quanto la mia soluzione fosse incredibilmente lenta in confronto ai primi tempi presenti in classifica, nonostante io sia piuttosto certo che la mia soluzione sia almeno asintoticamente ottimale
Dunque spero di raccogliere un pochino di trucchetti generici per limare qualche centesimo da ogni problema
Questo e’ il codice di partenza: ho tolto ogni linea di codice atta ad abbassare il fattore costante e ora si presenta cosi’
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
ll MOD = 1e9 + 7;
ll n, k;
bool b = false;
vector<vi> p;
int main() {
cin >> n >> k;
p.resize(2, vi(k+1));
iota(p[0].begin(), p[0].end(), 0);
for (int i = 1; i < n; i++) {
b = not b;
for (int j = 1; j <= k; j++)
p[b][j] = (p[not b][j/2] + p[b][j-1]) % MOD;
}
cout << p[b][k];
}
Questo codice esegue il l’ultimo testcase in 91ms, ma e’ possibile scendere fino anche a 4ms
Tra le tecniche che uso gia’, elenco:
#pragma GCC optimize("O3") (e perche’ spesso e’ piu’ veloce di Ofast?)
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); (non volevo concentrarmi sull’input/output perche’ ci sono gia’ altri post a riguardo
sostituire long long con int_fast64_t
aggiungere const dove possibile (nell’esempio, la costante MOD)
sostituire i vector con gli array (nell’esempio, la variabile p)
Si accettano molto volentieri nuovi suggerimenti e/o aggiustamenti sui sopracitati
Ottimizzare un programma è un procedimento molto complicato che richiedere molto conoscenze di come funziona il C++, di come funziona un sistema operativo e in praticolare di come funziona l’architettura x86. Se non hai tutte queste conoscenze, la cosa migliore che puoi fare è lasciare che il compilatore faccia le sue ottimizzazioni al posto tuo poiché spesso cercando di ottimizzare il codice ottieni l’esatto opposto.
Delle tecniche che hai citato le uniche davvero utili sono #pragma GCC optimize("O3") e ios::sync_with_stdio(false):
Ofast è indentico a O3 ma attiva alcune ottimizzazioni per i numeri in virgola mobile che nel tuo codice non usi, se uno dei due è più veloce dell’altro è solo una casualità.
Assumo che tu conosca già i rischi di cin.tie(0), invece cout.tie(0) è totalmente inutile in quanto cout non ha nessuna tied stream associata.
long long e int_fast64_t sono identici perciò usare int_fast64_t è inutile. Se non hai un motivo particolare di usarli, ti sconsiglio gli int_fast*_t poiché:
la differenza di performance è insignificante,
questi tipi possono occupare più memoria rispetto ai tipi primitivi, quindi più cache miss e quindi performance peggiori.
const non fornisce nessun vantaggio in quanto in C++ non è garantito che le variabili const non vengano modificate (ad esempio usando const_cast) se vuoi un tipo di dato effettivamente costante usa constexpr che però ha una semantica leggermente diversa.
L’unico vantaggio degli array rispetto ai vector è che gli array richiedono una allocazione di memoria in meno. In questo caso il numero di vector è così piccolo che non vi è nessuna differenza pratica.
Tieni infine presente che il tempo di esecuzione non è deterministico, mandando più volte la stessa soluzione puoi ottenere tempi anche molto diversi tra di loro.
Ottimizzare un programma e’ un procedimento molto semplice che non richiede alcuna conoscenza su come funziona il c++, compilatori, sistema operativo o l’architettura su cui lo fai girare, anche perche’ in genere basta fare cose a caso e vedere quale va piu veloce.
seguono alcuni consigli generali:
usa tipi unsigned quando puoi (non cambia sempre ma spesso puo migliorare)
sii scaramantico, metti const e __restricted dove puoi, usa != al posto di < nei for anche senza sapere se aiutano davvero (ma magari fallo dopo aver ottimizzato gia il resto)
non usare mai vector (in genere non servono davvero), usa std::array o array normali globali, l’heap e’ lento (esercizio per il lettore: tieni un grafo come adjlist senza usare heap, sapendo il numero di archi massimo a compile time)
fai ogni cosa nel modo piu veloce che conosci (eg: non sortare un array di interi con std::sort, scrivi un radix sort)
accedi bene alle matrici: se hai a[i][j] in due for annidati, i deve essere iterato dal for fuori e j da quello dentro (o piu in generale usa la cache bene)
bottom-up in genere e’ meglio di top-down
non dipendere dai pragma, aggiungili solo alla fine, e’ pretty random se migliorano o peggiorano da O2
manda le soluzioni quando il server e’ poco occupato, tipo alle 3 di mattina
non usare <bits/stdc++.h>: quando il server compila ci mettera’ di piu’, quindi si incazza e da tempi peggiori alla tua soluzione
inline puo actually fare differenze
usa i bitset (quelli scritti a mano tho, la roba della stl e’ sempre piu lenta di quello che scrivi tu)
ritorna sempre 0 dal main, altrimenti si confonde e spreca del tempo per capire cosa deve ritornare
elimina tutto il codice morto, nel caso il compiler non ci riesca e’ sempre memoria in meno
usa tutti i trick possibili specifici del problema (prob la prima ottimizzazione da fare)
Disclaimer: tutti questi consigli sono 100% accurati e da seguire alla lettera.
Non mi sono guardato ancora questo problema, adesso magari ci provo e ti dico cosa puoi migliorare della tua soluzione.
Per il poco che ci ho guardato: la tua complessita’ e’ O(n\cdot m), ma si puo risolvere in O(m) (nota che allo step i, usi solo i p_j \mid j \le jmax/2 se jmax e’ il j massimo che calcoli allo step i+1), non so se si possa risolvere in meno di O(m) tho
#include <iostream>
#include <array>
#include <cinttypes>
using namespace std;
constexpr uint32_t mod = 1000000007;
array<array<uint32_t,200002>,2> p;
signed main() {
uint32_t n,k,i,j,b=0;
cin >> n >> k;
for(j=0;j<=(k>>(n-1));++j)p[0][j]=j;
for (i = 1; i < n; ++i) {
b^=1;
for (j = 1; j <= (k>>(n-i-1)); ++j)
p[b][j] = (p[b^1][j/2] + p[b][j-1])%mod;
}
cout << p[b][k] << endl;
return 0;
}
ecco una versione somewhat ottimizzata (con la poca voglia che avevo) del tuo codice, le ottimizzazioni principali sono:
migliorata la complessita’ da O(m\cdot n) a O(m \cdot 2)
cambiati tutti gli interi da i64 a u32
cambiato il vector ad array
spostate le variabili in locale (tranne l’array)
usato signed main al posto di int main (probabilmente l’ottimizzazione che ha influito di piu)
con queste ottimizzazioni (senza pragma) va a ~11ms (submittato alle 21)
poi puoi provare a fare qualsiasi cosa ti venga in mente tipo usare if al posto di % e vedere come va
Con tecniche di programmazione che usano gli operatori bit a bit e che ricordano tanto la programmazione di basso livello (assembler, linguaggio macchina, ALU, registri a scorrimento, mascherature,…) per applicazioni a microprocessore.
Basta un array di uint64_t, poi tutti gli operatori sono abbastanza banali: & e’ l’& tra tutti gli elementi, same con | ^ ~, per accedere all’iesimo elemento puoi fare (a[i/64]>>(i%64)), gli shift sono un po piu uno schifo da implementare, ma comunque oltre a essere piu veloci puo essere utili implementarli a mano perche’ la stl non ha cose tipo: bitset resizable con tutti gli operatori, o iteratori sugli elementi a 1, che sono tutte cose ez da implementare.
In ogni caso anche quelli della stl qualcuno deve averli implementati a mano.
Se intendevi in modo letterale: usi le mani per scrivere il codice di un bitset con la tastiera.
