Quando vado a sottoporre il codice mi da errore di fuori memoria in tutti i testcase, ma quando lo provo in locale con il grader scaricato funziona senza problemi, mi sapreste dire il perché?
Vi lasci qui di seguito il codice grazie in anticipo:
Probabilmente con il grader in locale ti è possibile accedere all’array C, quando sottoponi però non puoi, infatti il grader che viene lasciato per facilitare la lettura dell’input è solo una versione semplificata del grader usato durante la correzione. Quindi devi crearti tu un array globale sul quale mano a mano aggiungerai gli interi checksum. (Poi probabilmente non farai 100 lo stesso in quanto la complessità del tuo algoritmo è un tantino elevata)
oppure potrei non aver capito come risolverlo
No perchè io con i grader non sono molto pratico e vorrei capire se quando lui richiama le funzioni i vettori sono già riempiti oppure lo devo fare io
Cioè basta ma non basta , insomma devi anche modificarli nella funzione controlla o inizializza, sennò rimangono tutti a 0.
E comunque dopo ti andrà in TLE su alcuni, prima risolvi questo problema però.
Ti assicuro che non è affatto un problema semplice, ti consiglio di andarci comunque per gradi, piuttosto che spoilerarti direttamente la soluzione:
Risolvi prima di tutto il problema di adesso, aggiungi l’array globale C (non ho ben capito a cosa serva E) e anziché fare un find salvati direttamente quanti numeri hai controllato, all’inizio di controlla metti checksum nella prima casella libera di C e incrementi di 1 il numero di numeri che hai controllato, il resto dell’algoritmo lo fai uguale a prima.
Cerca di ottimizzare almeno la funzione coprimi, che per adesso ha complessità pari a O(M) in quanto deve controllare tutti i numeri fino ad a o b. Chiediti quale bellissima funzione può farti trovare un divisore comune con complessità logarimica. È il Massimo Comun Divisore, che in cpp si richiama con __gcd(a,b), che implementato correttamente con l’algoritmo di euclide ha complessità nel caso peggiore pari a log_{\varphi}(n)
Ovviamente quanto scritto sopra non basta, in quanto la complessità diventerebbe O(T^2log(M)), prova a risolvere accensione per vedere se ti viene in mente qualcosa, in caso ne riparliamo.
Per qualsiasi problema/incomprensione scrivi pure .
Piccolo edit:
sono riuscito a prendere 55/100 e vai in TLE in alcuni casi del penultimo task e in tutti quelli dell’ultimo, questo è il codice semplicemente ho controllato per quali numeri era divisibile l’attuale checksum e se nella ricerca non incontravo mai una casella già riempita significava che il checksum che stiamo attualmente controllando è valido, questo è il codice che forse potrebbe essere più chiaro, qualche idea per velocizzarlo?
#include <bits/stdc++.h>
#define MAXN 4000001
using namespace std;
static FILE *fr, *fw;
int P;
int M;
int last=0;
int E[MAXN];
void inizializza(int PP, int MM){
P=PP;
M=MM;
}
int controlla(int checksum){
vector<int>div;
bool a=false;
int numret=0;
for(int i=2;i<=checksum/2 && a==false;i++){
//cout<<checksum<<"%"<<i<<"\n";
if(checksum%i==0){
//cout<<"C: "<<E[i-1]<<"\n";
if(E[i-1]==0){
div.push_back(i-1);
}
else{
numret=E[i-1];
a=true;
}
}
}
if(E[checksum-1]==0){
div.push_back(checksum-1);
}
else{
a=true;
numret=E[checksum-1];
}
//cout<<checksum<<"\n";
if(a==false){
for(int i=0;i<div.size();i++){
E[div[i]]=checksum;
//cout<<div[i]<<" ";
}
}
return numret;
}
Un idea che mi era venuta in mente era di controllare se i divisori di un numero non fino a checksum/2 ma fino a sqrt(checksum) ma ho notato che con numeri come ad esempio 10 non funzionerebbe perchè si fermerebbe a controllare fino a 3 e non andrebbe a controllare 5 che è effettivamente un divisore di 10
Questo è effettivamente aggirabile, infatti se trovi che 2 divide 10, allora anche 10/2 divide 10, in questo modo puoi fermarti fino a radice di 10.
Comunque devo correggermi, il problema che ho linkato tra i punti non c’entra più di molto con questo
Bhe allora cosi su due passi penso che prendendo un pacchetto “pari” dopo tutti gli altri pari non li prenderò sicuramente e inoltre se prendo un pacchetto X tutti i multipli di X non gli dovrò prendere
.