Problema Autogrill

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

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