Salve a tutti,
Stavo risolvendo il problema “pin” delle ois2018 ma purtroppo ottengo un punteggio pari a 0/100 perchè ottengo due “Execution timed out” circa in ogni subtask. Qui c’è il mio codice (https://pastebin.com/rZ7W9P8b).
Qualcuno saprebbe aiutarmi ?
Grazie 
Il problema dice che la stringa è lunga N<=1.000.000, e la lunghezza del pin è K<=9. Esistono O(N-K) sottostringhe lunghe esattamente K di una stringa lunga N. K è piccolo, quindi trascuriamolo, il vettore pin conterrà O(N) stringhe, la count ha complessità O(N) e la esegui N volte, quindi la complessità dell’algoritmo è O(N^2).
Cerca una struttura dati che ti permetta di contare il numero di volte che hai inserito un certo elemento più velocemente che cercandolo in un array, oppure esegui qualche operazione sull’array in modo da trovare piu’ velocemente i pin ripetuti
1 Mi Piace
Ho usato una mappa …
Ora ottengo due " Execution killed with signal 9 " in ogni subtask.
Questo è il codice (https://pastebin.com/ERV7KLAp). Non so se è corretto ma dovrebbe funzionare…
Grazie.
Allochi troppa memoria, ho realizzato una soluzione simile alla tua usando sempre la map e occupo 51.6 MiB nel ultimo test case.
Salvandoti ogni combinazione nella mappa, hai il bisogno di salvarti tutto il testo in input ?
Il timeout è causato dal richiamo della della funzione substr, hai N <= 1 000 000 e richiamarla per N-K volte è un numero molto elevato.
Pensa bene a questo consiglio di marco che ha spiegato benissimo il problema.
Onestamente non riesco a trovare un algoritmo diverso da quello già fatto… potete aiutarmi ?
La soluzione è quasi completamente corretta, l’unica cosa che sbagli è come usi la map. Devi vederla come un contenitore che ad ogni stringa ti associa un valore intero (infatti map<string,int>). Tu continui ad inserire 1 come valore e contare quante volte è presente. C’è qualcosa di più furbo che puoi inserire dentro la map al posto di 1?
Nota: i valori numerici che inserisci possono anche essere cambiati dopo averli messi
Nota2: data una chiave (di tipo string) puoi accedere al valore (di tipo int) a cui è associata!
Ok, ora prendo 85 perchè nell’ ultimo subtask un testcase va in “Execution timed out.” per poco… Credo che il problema sia qui:
void caricamento() { string temp = ""; for(long int i = 0; i <= N-K; i++) { temp = s.substr(i, K); pin[temp] += 1; temp.clear(); } return ; }
Avevo lo stesso problema di time out sull’ultimo task dell’ultimo testcase.
Io ho risolto così:
Il problema sta nella check, dove cerchi il massimo.
#include algorithm
…
// find the best candidate c++11
auto x = max_element(candidates.begin(), candidates.end(),
[](const pair<string, int>& p1, const pair<string, int>& p2) {
return p1.second < p2.second; });
Si sì poi ho risolto. Ma già da mesi con una soluzione anche abbastanza ottimale ahah, comunque grazie 