Nel problema Autogrill non mi è chiara la condizione “Nel caso in cui ci siano due o più autogrill equidistanti da p, si restituisca quello al km maggiore”. Un testcase con più di due autogrill aperti equidistanti da p potrebbe essere il seguente esempio
1 2 p 3 4
In tal caso l’output corretto è 3 (come penso) o 4? che è quello con km maggiore ma non il più vicino!
con equidistanti da p intende che se la differenza tra l’autogrill prima di p e l’autogrill dopo p è uguale, allora l’output dovrà essere l’autogrill con il kilometro più grande
secondo il testcase che hai fornito (un po’ ambiguo perchè il valore di p sarebbe 2,5 e non può essere)
dovresti fare differenza tra 2 e p e differenza tra 3 e p (ovvero |2 - p| e |3 - p|), le differenze danno come valore 0,5 quindi possiamo dire che gli autogrill sono equidistanti e quindi l’output corretto è 3
facciamo un altro esempio
1 5p 9 12 (p=5)
|1 - 5| = 4
|5 - 5| = 0
|9 - 5| = 4
l’output è 5
1 5 p 9 12 (p=6)
|5 - 6| = 1
|9 - 6| = 3
l’output è 5
1 5 p 9 12 (p=7)
|5 - 7| = 2
|9 - 7| = 2
l’output è 9
1 5 p 9 12 (p=8)
|5 - 8| = 3
|9 - 8| = 1
l’output è 9
Sorry. Errore di distrazione: volevo scrivere 1 2 p 4 5. In base agli esempi, avevo quindi inteso bene, difatti con questi esempi e con tanti altri funziona. Quando sottometto la soluzione (implementata con un SET) in un paio di testcase mi da output errato. Deduco che non è un problema di interpretazione. Grazie comunque.
Come sei riuscito a risolverlo con un set? Ci ho provato, ma il set non mi da operatori per accedere agli elementi, necessari per ottenere la funzione “chiedi” .
Ho pensato ad un lower_bound con una funzione di comparazione modificata, ma anche quella è stata un buco nell’acqua.
L’unico modo in cui ho ottenuto entrambi gli esempi con output corretto è stato grazie a una priority_queue.
Io ho usato due set, uno con numeri degli autogrill positivi e l’altro negativi, poi ho fatto un lower_bound di entrambi e ho confrontato la differenza assoluta.
Molto probabilmente esiste un modo migliore per farlo ma non sono intelligente abbastanza
1 Mi Piace
Per accedere al successivo e al precedente di un set, ad esempio nel caso di un lower_bound(), puoi utilizzare le seguenti funzioni:
auto it = myset.lower_bound(p),
int succ = *next(it); (per l’elemento successivo)
int prec = *prev(it); (per l’elemento precedente)
1 Mi Piace
Grazie mille caro, ho provato a risolvere adoperando il lower_bound ed il primo elemento precedente, ma il problema continua ad essere errato in alcuni testcase, e non comprendo il perché.
Dato che lower_bound restituisce il primo elemento NON MINORE, ottengo sicuramente una distanza dall’ultimo auogrill >= 0. Accedendo all’elemento precedente ottengo una distanza <0, queste due distanza sono comunque le due più vicine perché il set è ordinato per definizione.
Non comprendo dove possa dare errore…
Sono nella stessa condizione.
Controllo l’upper bound perché richiede la precedenza del maggiore rispetto al minore degli autogrill e successivamente controllo il precedente.
Rimane però il fatto che vari testcase risultano errati.
Come mai?
Senza vedere il codice è difficile dirlo, ma potrebbe essere che non stiate controllando alcuni edge case (esiste effettivamente un lower_bound? esiste il prev() del lower_bound?)
Prova a verificare il tuo programma con questo input:
7
q 5
a 8
q 6
a 10
q 8
a 11
q 12
long long chiedi(long long p, std::set<long long> &autogrill) {
long long min_val;
long long final_val;
if (autogrill.size()==0){
return -1;
}
set<long long>::iterator itup = autogrill.upper_bound(p);
min_val = abs(p-*itup);
final_val = *itup;
set<long long>::iterator prec = prev(itup);
long long val = abs(p-*prec);
if (val < min_val){
min_val = val;
final_val = *prec;
}
set<long long>::iterator itlow = autogrill.lower_bound(p);
val = abs(p-*itlow);
if (val < min_val){
min_val = val;
final_val = *itlow;
}
set<long long>::iterator succ = next(itlow);
val = abs(p-*succ);
if (val < min_val){
min_val = val;
final_val = *succ;
}
return final_val;
}
Credo di controllare tutti i casi. Cosa sto sbagliando?
Perché fai sia l’upper bound sia il lower bound? Comunque non stai controllando nessuno dei due casi di cui sopra: in particolare, cosa succede se non c’è nessun autogrill dopo la posizione di Giorgio? e se invece non ce ne sono prima?
Si, si può risolvere anche con un SET ‘giocando’ con il lowerbound e l’upperbound di p per ottenere il precedente ed il successivo elemento rispetto a p, a quel punto basta un calcoletto.
Guarda, ho provato con questo esempio molto sempliceche dovrebbe riportare il tuo edge case:
2
a 3
q 5
//restituisce 3
Il codice è il seguente, io non ho la più pallida idea di cosa non stia controllando.
long long chiedi(long long p) {
if(st.empty()) return -1; //Se il set è vuoto non ci sono autogrill aperti
auto succ = st.lower_bound(p); //iteratore alla prima distanza positiva da P
auto prec = prev(succ); //iteratore alla prima distanza negativa da P
long long primo = abs(*succ - p), secondo = abs(*prec - p);
if(primo > secondo) return *prec; //se è più vicino il secondo lo restituisco
return *succ; //se sono uguali o è meglio il primo restituisco il primo (perché più grande)
}
Quando utilizzi le funzioni prev() e next() devi controllare che l’iterator corrente non punti già all’inizio o alla fine del set.
auto it = myset.lower_bound(p);
if(it != myset.begin()) it = prev(it);
if(it != myset.end()) it = next(it);
Nel tuo programma ometti questo tipo di controllo e quindi restituisce un risultato errato come in questo input:
4
a 5
a 6
a 7
q 2
long long chiedi(long long p, std::set<long long> &autogrill) {
long long min_val;
long long final_val;
if (autogrill.size()==0){
return -1;
}
set<long long>::iterator it = autogrill.upper_bound(p);
min_val = abs(p-*it);
final_val = *it;
it = next(it);
long long val = abs(p-*it);;
if (val < min_val){
final_val = *it;
}
it = autogrill.upper_bound(p);
it = prev(it);
val = abs(p-*it);;
if (val < min_val){
final_val = *it;
}
return final_val;
}
Così controllo upper bound, precedente e successivo.
Mi pare di coprire tutti i casi.
Ho provato con i seguenti casi
4
a 5
a 6
a 7
q 10
e mi restituisce 7
con
4
a 5
a 6
a 7
q 1
mi restituisce 5.
Qual è il problema?
Mi sembra che questi due casi li faccia bene
1 Mi Piace
Mi dice sempre 0/100 perché nel subtask 2 in alcuni casi esce “Output not correct”.
Grazie infinite, sono finalmente riuscito a risolvere questo dannatissimo problema…
Senza il tuo aiuto e quello di @fve5 lo avrei risolto l’anno prossimo…
Grazie ancora!
Non stai controllando che iteratore ti ritorna upper_bound. Quando chiami autogrill.upper_bound(p) e non c’è un elemento abbastanza grande nel set, viene ritornato l’iteratore autogrill.end() che non è dereferenziabile in quanto non punta a nessun elemento del set.
Di conseguenza quando scrivi:
min_val = abs(p-*it);
il tuo programma mostra undefined behaviour e si comporta in modo imprevedibile.
Inoltre come ha detto @qwfwq quando fai prev(it) e next(it) devi controllare che it non sia rispettivamente il primo o l’ultimo elemento del set. Comunque controllare next(it) dovrebbe essere inutile visto che *it è già maggiore o uguale a p