# Checksum Problemi con il grader

**URL:** <https://forum.olinfo.it/t/checksum-problemi-con-il-grader/6205>\
**Category:** Aiuto\
**Created:** [25 Maggio 2020, 8:01pm UTC](https://forum.olinfo.it/t/checksum-problemi-con-il-grader/6205 "2020-05-25T20:01:37Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![Mat0k3](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/35a633/32.png) [@Mat0k3](https://forum.olinfo.it/u/Mat0k3)\
**Post date:** [25 Maggio 2020, 8:01pm UTC](https://forum.olinfo.it/t/checksum-problemi-con-il-grader/6205/1 "2020-05-25T20:01:37Z")

</div>

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:

```auto
#include <bits/stdc++.h>
using namespace std;
static FILE *fr, *fw;

// Declaring variables
static int P;
static int M;
static int* C;
static int* E;

// Declaring functions
bool coprimi(int a,int b){
	for(int i=2;i<=min(a,b);i++){
		if(a%i==0 && b%i==0){
			return false;
		}
	}
	return true;
}
void inizializza(int P, int M){
	::P=P;
	::M=M;
}
int controlla(int checksum){
	if(checksum==C[0]){
		return 0;
	}
	else{
		auto it=find(C,C+P,checksum);
		for(int i=0;i<it-C;i++){
			if(E[i]==0){
				if(checksum%2==0 && C[i]%2==0 || max(checksum,C[i])%min(checksum,C[i])==0){
					return C[i];
				}
				else{
					if(coprimi(checksum,C[i])==false){
						return C[i];
					}
				}
			}
		}
	}
	return 0;
}
```

---

<div class="post-metadata">

**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\
**Post date:** [26 Maggio 2020, 9:09am UTC](https://forum.olinfo.it/t/checksum-problemi-con-il-grader/6205/2 "2020-05-26T09:09:02Z")

</div>

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)

---

<div class="post-metadata">

**Author:** ![Mat0k3](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/35a633/32.png) [@Mat0k3](https://forum.olinfo.it/u/Mat0k3)\
**Post date:** [26 Maggio 2020, 9:45am UTC](https://forum.olinfo.it/t/checksum-problemi-con-il-grader/6205/3 "2020-05-26T09:45:19Z")

</div>

Quindi basta fare questa modifica:

```auto
int C[300000];
int E[300000];

```

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

---

<div class="post-metadata">

**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\
**Post date:** [26 Maggio 2020, 9:48am UTC](https://forum.olinfo.it/t/checksum-problemi-con-il-grader/6205/4 "2020-05-26T09:48:31Z")

</div>

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ò.

---

<div class="post-metadata">

**Author:** ![Mat0k3](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/35a633/32.png) [@Mat0k3](https://forum.olinfo.it/u/Mat0k3)\
**Post date:** [26 Maggio 2020, 9:53am UTC](https://forum.olinfo.it/t/checksum-problemi-con-il-grader/6205/5 "2020-05-26T09:53:14Z")

</div>

Guarda sarò io stupido( e su questo ce poco da dire 😅) ma non riesco a capire come risolverlo. Se me lo potresti dire tu mi faresti un gran favore 🤣

---

<div class="post-metadata">

**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\
**Post date:** [26 Maggio 2020, 10:33am UTC](https://forum.olinfo.it/t/checksum-problemi-con-il-grader/6205/6 "2020-05-26T10:33:25Z")

</div>

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](https://cp-algorithms.com/algebra/euclid-algorithm.html) 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](https://training.olinfo.it/#/task/accensione/statement) per vedere se ti viene in mente qualcosa, in caso ne riparliamo.

Per qualsiasi problema/incomprensione scrivi pure 😉.

---

<div class="post-metadata">

**Author:** ![Mat0k3](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/35a633/32.png) [@Mat0k3](https://forum.olinfo.it/u/Mat0k3)\
**Post date:** [26 Maggio 2020, 10:55am UTC](https://forum.olinfo.it/t/checksum-problemi-con-il-grader/6205/7 "2020-05-26T10:55:14Z")

</div>

Ok grazie mille vedo cosa riesco a fare

---

<div class="post-metadata">

**Author:** ![Mat0k3](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/35a633/32.png) [@Mat0k3](https://forum.olinfo.it/u/Mat0k3)\
**Post date:** [26 Maggio 2020, 2:51pm UTC](https://forum.olinfo.it/t/checksum-problemi-con-il-grader/6205/8 "2020-05-26T14:51:32Z")

</div>

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?

```auto
#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

---

<div class="post-metadata">

**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\
**Post date:** [26 Maggio 2020, 7:25pm UTC](https://forum.olinfo.it/t/checksum-problemi-con-il-grader/6205/9 "2020-05-26T19:25:07Z")

</div>

> [@Mat0k3](#):
>
> 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 😅

---

<div class="post-metadata">

**Author:** ![zJack1342](https://forum.olinfo.it/user_avatar/forum.olinfo.it/zjack1342/32/711_2.png) [@zJack1342](https://forum.olinfo.it/u/zJack1342)\
**Post date:** [26 Maggio 2020, 8:10pm UTC](https://forum.olinfo.it/t/checksum-problemi-con-il-grader/6205/10 "2020-05-26T20:10:27Z")

</div>

Prova a vederla secondo questo punto di vista: Se accetto il pacchetto X, quali pacchetti di sicuro scarterò d’ora in poi?

---

<div class="post-metadata">

**Author:** ![Mat0k3](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/35a633/32.png) [@Mat0k3](https://forum.olinfo.it/u/Mat0k3)\
**Post date:** [26 Maggio 2020, 9:31pm UTC](https://forum.olinfo.it/t/checksum-problemi-con-il-grader/6205/11 "2020-05-26T21:31:41Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![zJack1342](https://forum.olinfo.it/user_avatar/forum.olinfo.it/zjack1342/32/711_2.png) [@zJack1342](https://forum.olinfo.it/u/zJack1342)\
**Post date:** [26 Maggio 2020, 9:47pm UTC](https://forum.olinfo.it/t/checksum-problemi-con-il-grader/6205/12 "2020-05-26T21:47:51Z")

</div>

Non solo, se prendi 10 i pacchetti 5 e 2 sono scartati anche se non sono multipli. Prova a considerare il pacchetto 30030.