Salve a tutti, ho provato a risolvere il problema annoluce, ma fallisco nel risolvere l’ultima task, nello specifico i testcase 22 e 24 (“Not correct”, no time out)
Per risolvere il problema calcolo la distanza delle stelle (con: rad(x^2+y^2+z^2)), le salvo in un vettore e poi lo ordino. Per ogni query eseguo una specie di ricerca binaria e restituisco la posizione trovata +1.
All’inizio ho pensato che il problema fosse la precisione della distanza calcolata sulle stelle (ho provato ad usare float, double e long double ma niente funziona), essendoci numeri molto grandi e calcolando, credo perdendo precisione, la radice di un numero.
Allora ho provato a calcolare la distanza delle stelle solo come la somma dei quadrati delle coordinate e a salvarle su un vettore di long long int, e a confrontare le nuove distanze con D^2 (sempre memorizzato su un long long int). Ma nemmeno questo sembra risolvere il problema (dà sempre lo stesso errore sui testcase 22 e 24).
Allora ho pensato che la ricerca binaria possa avere qualche problema, e ho provato a risolvere il problema nel modo più intuitivo, e lento, possibile :
for(ris = 0; ris<N && D>=mappa[ris]; ris++)
return ris; //mappa è il vettore ordinato dove sono salvate le distanza delle stelle
anche qui l’algoritmo è sostanzialmente corretto, e quando non va in time out mi dice che il risultato è giusto, tranne nel testcase 22(il 24 va in timeout quindi non so se è giusto il risultato).
Questo dimostra che il problema non sta nella ricerca binaria ma nel confronto dei numeri, che, per mancanza di precisione mi danno il risultato sbagliato.
Non credo ad essere l’unico ad aver avuto questo problema considerando il numero di soluzioni inviate (1106 di cui 46 corrette) e sarebbe bello avere un chiarimento su queste task.
Sarà una domanda stupida ma: consideri il fatto che ci potrebbero essere più stelle con la stessa distanza?
Magari con la tua ricerca binaria ti fermi proprio nel mezzo di un gruppo di stelle con la stessa distanza e ne perdi alcune.
Oppure non consideri il fatto che la distanza D data in input potrebbe essere insufficiente a raggiungere una qualunque stella, quindi con la tua ricerca ti fermeresti alla posizione 0, ritornando 0+1=1 quando in realtà la risposta è 0.
Grazie per la risposta, comunque il mio algoritmo di ricerca binaria dovrebbe funzionare anche nei casi limite che hai citato
Il problema principale non è tanto la ricerca binaria, bensì il calcolo della distanza delle stelle.
Infatti usando un altro algoritmo più inefficiente ma semplice e “sicuro” ovvero lo scorrere tutto il vettore e aumentare il risultato di 1 ogni volta che si trova una stella con lunghezza minore uguale a d, il testcase 22, che NON va in time out, mi segna che ho dato un risultato sbagliato, il testcase 24 va in timeout, i restanti sono giusti o vanno in timeout.
Questo, anche ammettendo che il mio algoritmo di ricerca binaria sia sbagliato, non spiega perchè il testcase 22 sia errato anche con l’utilizzo di un così semplice algoritmo. Per aumentare la precisione ho provato a memorizzare le distanze delle stelle solo come la somma di quadrati e a fare il confronto con D^2. Ho provato ad utilizzare casi di prova con i numeri più grandi possibili, e non ci sono overflow. Quindi non capisco proprio cosa possa essere…
long long int mappa[MAXN];
void mappatura(int N, int X[], int Y[], int Z[]) {
for(int i = 0; i<N; i++)mappa[i] = (pow(X[i],2)+pow(Y[i],2)+pow(Z[i],2));
sort(mappa, mappa+N);
}
int query(int D) {
long long int d = pow(D,2);
int ris = 0;
for(int i = 0; i<N ; i++)if(d>=mappa[i])ris++;
return ris;
}
So che non si dovrebbe scrivere codice risolutivo in questa sezione ma alla fine la query è sostanzialmente troppo lenta per essere una vera e propria soluzione, perdonatemi se violo qualche regolamento ma sto impazzendo e non capisco dove stia sbagliando…
Ho provato a risolvere la conversione tra double e int con ceil(sqrt(pow(X[i], 2) + pow(Y[i], 2) + pow(Z[i], 2))) + 0.1 (Così il +0.1 sicuramente fa approssimare per eccesso il double ceil(x)), ma non funziona. Sapete perche?
(Ho provato anche X[i] * X[i]... immagazzinando i valori al quadrato e poi elevando alla seconda D(in una variabile long long) ma faceva ancora meno punti, non so perchè…)
Hai riaperto un thread chiuso da 7 anni. Se questo già non ti sembrava poco sensato quando hai iniziato a scrivere il messaggio, ti è anche apparso un riquadro che ti avvertiva ulteriormente del fatto. Chiedere aiuto sul forum va bene, accodarsi a un thread recente sull’argomento anche, ma considera che dopo 7 anni è praticamente certo che gli autori originali neanche si ricordino di questo thread etc. etc.
Se ti serve davvero aiuto ti consiglio di aprire un nuovo argomento (magari con qualche dettaglio in più sul tuo problema)
questo non è necessariamente vero: i double tengono “solo” ~16 cifre significative (prova a confrontare 2^{53} e 2^{53} + 1): quando è possibile conviene usare variabili intere. (Se fossi interessato comunque esistono long double e __int128_t)
