Salve a tutti,
ultimamente ho provato a sviluppare l’algoritmo risolutivo del problema “Duplicato mancante (duplicato)”.
Durante lo sviluppo dell’algoritmo non ho riscontrato alcuna difficoltà, provando nel mio PC il programma con gli esempi di prova, gli output sono esatti… però nelle varie Sottoposizioni (comprese quelle di prova) prendo 0/100 per output non corretto…
Qui potete trovare il mio codice : https://pastebin.com/fiugCdXr
Cosi a prima vista prova a inizializzare pos e foglio potrebbe essere quello 
Il bug sta nella tua funzione trova, in cui chiami std::count(P, P + N, P[i]), mentre dovresti chiamare std::count(P, P + 2 * N, P[i]). Altra cosa che non tenevi in considerazione è il fatto che la count considera anche l’elemento corrente, quindi per l’elemento di cui manca la copia ritorna 1 e non 0.
Mi sono preso la briga di riscivere la tua funzione trova:
int trova(int N, int P[])
{
for(int i = 0; i < 2 * N; i++)
{
if(std::count(P, P + 2 * N, P[i]) == 1)
return P[i];
}
return -1;
}
Questo algoritmo comunque non permette di andare oltre i 70 punti, perchè ha complessità \mathcal O(N^2) e va quindi fuori tempo limite, mentre la complessità richiesta è al più \mathcal O(NlogN). Esiste anche un algoritmo in \mathcal O(N), ma in questo caso non era richiesto.
Dario
1 Mi Piace
Esattamente 70/100… mi è bastato cambiare “N” in “N*2-1” ed ho ottenuto 70/100.
Ma tu come facevi a sapere che avrei preso 70/100 ? 
Ti ho molto ignorantemente rubato il codice e lo ho sottomesso con le correzioni
1 Mi Piace
Algoritmo in O (n) ?Usi una map?
Con la map viene \mathcal O(NlogN), con una hashmap verrebbe \mathcal O(N) ma con fattori costanti bruttarelli. Esiste una soluzione in \mathcal O(N) elegantissima basata sullo ^
1 Mi Piace
Ah si avevo letto qualcosa del genere…
Ma dovrebbe essere lo XOR di quale valore ?
L’idea è quella di partire da a \oplus a = 0 e a \oplus 0 = a, dove \oplus indica lo xor tra due valori. Quindi se facciamo lo xor di tutti i valori in ingresso ogni valore che è presente due volte si annulla, mentre il risultato sarà proprio il valore dell’elemento presente una volta sola.
1 Mi Piace
Quindi all’interno del ciclo dovrei fare “P[i] ^ P[i]” ?
No, quello che devi fare è mantenere un unico valore che è lo xor di tutti i valori in ingresso, una cosa del tipo di V = P[0] \oplus P[1] \oplus \ldots \oplus P[N - 1]. V sarà il risultato.
1 Mi Piace
Grazie @dp_1 dell’aiuto… sono riuscito ad ottenere 100/100.
Pero’ mi piacerebbe sapere come è possibile trovare il risultato con lo XOR… se no non imparo niente e i 100 pt non hanno valore 
…
In ingresso hai una lista di interi a_0, a_1, b_0, b_1, c_0, c_1, \ldots, z_0, dove le coppie a_0, a_1 e simili indicano due valori identici, mentre z_0 è il valore che è presente una sola volta. La lista in ingresso non è necessariamente in quest’ordine, ma ce ne importa ben poco. Facendo lo xor di tutti i valori in questa lista le coppie del tipo di a_0, a_1 si annulleranno, perchè a \oplus a = 0, quindi alla fine otterremo V = 0 \oplus 0 \oplus 0 \ldots \oplus z_0 = z_0, che non è altro che il risultato richiesto.
1 Mi Piace