Buongiorno a tutti.
Stavo risolvendo il problema “autogrill” (soste in autostrada) su AlgoBadge, e i test case dati nel testo mi risultano corretti, ma il punteggio dato è comunque 0/100.
Il mio codice è seguente:
#include <fstream>
#include <cassert>
#include <utility>
#include <vector>
#include<cmath>
#include<limits.h>
using namespace std;
vector<long long> autogrill;
void inizia(){
autogrill.push_back(-1);
autogrill.push_back(LONG_LONG_MAX);
}
long long scorri(long long p){
int i=0, s=autogrill.size();
while(p>autogrill[i]&&i<s){
i++;
}
return i;
}
void apri(long long p){
int temp=scorri(p);
autogrill.insert(autogrill.begin()+temp, p);
}
long long cerca(long long p, long long &c){
long long i=1, f=autogrill.size()-2;
c=(i+f)/2;
while(i<=f){
c=(i+f)/2;
if(p==autogrill[c]){
return c;
}else if(autogrill[c]<p){
i=c+1;
}else{
f=c-1;
}
}
return -1;
}
void chiudi(long long p){
autogrill.erase(autogrill.begin()+scorri(p));
}
long long chiedi(long long p){
long long c;
if(cerca(p, c)==-1){
if(autogrill[c]==-1){
if(autogrill[c+1]==LONG_LONG_MAX){
return -1;
}else{
return autogrill[c+1];
}
}else if(autogrill[c]==LONG_LONG_MAX){
if(autogrill[c-1]==-1){
return -1;
}else{
return autogrill[c-1];
}
}else if(autogrill[c-1]==-1&&autogrill[c+1]==LONG_LONG_MAX){
return autogrill[c];
}else if(autogrill[c-1]==-1){
if(llabs(autogrill[c]-p)<llabs(autogrill[c+1]-p)){
return autogrill[c];
}else{
return autogrill[c+1];
}
}else if(autogrill[c+1]==LONG_LONG_MAX){
if(llabs(autogrill[c-1]-p)<llabs(autogrill[c]-p)){
return autogrill[c-1];
}else{
return autogrill[c];
}
}else{
if(autogrill[c]<p){
if(llabs(autogrill[c]-p)<llabs(autogrill[c+1]-p)){
return autogrill[c];
}else{
return autogrill[c+1];
}
}else{
if(llabs(autogrill[c-1]-p)<llabs(autogrill[c]-p)){
return autogrill[c-1];
}else{
return autogrill[c];
}
}
}
}else{
return p;
}
}
int main() {
int Q;
ifstream cin("input.txt");
ofstream cout("output.txt");
cin >> Q;
inizia();
for (int i = 0; i < Q; i++){
long long p;
char t;
cin >> t >> p;
if (t == 'a') apri(p);
else if (t == 'c') chiudi(p);
else cout << chiedi(p) << endl;
}
cin.close();
cout.close();
return 0;
}
Non riesco a trovare alcun tipo di bug. Magari qualcuno nota dei casi non contemplati? Ringrazio dell’aiuto.
P.S.: sono nuovo alla piattaforma
Ciao Zaccaria, ho letto la traccia del codice e ti dice di implementare solo le funzioni richieste all’interno del codice. Di conseguenza dovresti togliere il main .
Ciao,
Ho messo il main solo per praticità a chi vuole leggere e testare il contenuto… Le funzioni le metto da sole nelle sottoposizioni… Altrimenti non compilerebbe nemmeno
Si scusami non avevo letto attentamente. Come vedi a qualche test il codice risponde anche correttamente ma impiega molto tempo nell’esecuzione quindi oltre quello dovuto. La soluzione è giusta, altrimenti darebbe per errato tutti i case. Ti consiglio di rimuovere qualche condizione all’interno della funzione “chiedi” trovando una soluzione che impieghi meno tempo. Potresti spiegarmi il tuo ragionamento??
Ciao, scusami per il ritardo.
Il mio ragionamento si basa sul fatto che una ricerca binaria/dicotomica (funzione cerca()) termina con il “centro” c della ricerca sull’elemento da cercare, se trovato, oppure sull’elemento direttamente maggiore o direttamente minore. Quello che la funzione chiedi() fa è controllare che il valore trovato non sia -1 o LONG_LONG_MAX; se è -1, controlla che l’elemento successivo sia LONG_LONG_MAX, in tal caso non c’è alcuna stazione aperta, quindi ritorna -1; se è LONG_LONG_MAX, controlla se il precedente è -1 (quindi no stazioni); se non è uno dei due, ritorna il valore a destra. Se ci sono 3 elementi (-1, int, long_long_max) allora il valore della stazione è int; altrimenti, controlla che i valori a fianco nel vettore non siano i limiti; se lo sono, ritorna il numero; altrimenti, ritorna quello con differenza minore dal numero p.
(posso capire che questo ragionamento sia complesso da capire, proverò a reimplementare usando i set)
La funzione scorri() scorre il vettore autogrill finchè non trova un elemento maggiore di p o finchè il vettore finisce; quando termina, si ottiene l’indice per inserire il nuovo elemento con la funzione autogrill.insert(), così da non dover inserire e poi effettuare un ordinamento (particolarmente pesante).
Una curiosità: cosa intendi per “lento”? Ho provato a eseguire il programma con i casi di test e rientra con grande margine all’interno del secondo dato dal problema. Hai per caso usato un file più pesante (che non ho avuto modo di reperire)? Se sì, potrei ottenerne una copia?
Allego uno screenshot con la misura della durata di esecuzione del programma:
Il limite di ogni test come penso tu sappia già è di 1 secondo e il tuo codice nei task 3 e 12 supera leggermente questo limite. Ti do un consiglio: esistono vari “trucchi” per velocizzare il codice a volte cambiando anche una semplice funzione. Vedi quale dei tanti fa più al tuo caso.
Ciao,
volevo chiederti, com’è che ottieni questi test case e quali singoli casi sono errati? Ho guardato su algobadge e non trovo nulla. E’ qualcosa a cui non ho accesso o non ho guardato nel posto giusto?
Ciao a entrambi! Cerco di chiarire un paio di cose.
Algobadge è solo una selezione di problemi di training.olinfo.it. Dalla pagina in cui fai le sottoposizioni dovresti trovare in basso l’elenco delle sottoposizioni precedenti. Se clicchi sul numero identificativo di una sottoposizione dovresti visualizzare i dettagli che compaiono nell’immagine.
Poi, @Fearingtable, ovviamente la piattaforma non lascia terminare le soluzioni quando il tempo limite viene superato. Quindi quando viene dato come verdetto “Execution timed out” il tempo visualizzato è sempre poco più del TL, indipendentemente da quanto tempo avrebbe effettivamente impiegato la soluzione.
In merito ai test sul tempo impiegato in locale: i testcase segreti su cui vengono testati i programmi sono ovviamente molto più grandi dei casi di esempio forniti a scopo esplicativo (e di debugging) ai concorrenti/risolutori. Chiaramente il tuo programma impiegherà molto più tempo a eseguire un testcase con 100’000 richieste rispetto a uno con 5. (Nulla ovviamente ti vieta di generare in locale casi più grandi su cui testare il tuo codice)
Ritorniamo al codice che @Zaccaria ha inviato. Il vero problema è che quando inserisci un valore in mezzo a un vector (come tu stai facendo ora) sei costretto a spostare avanti di uno tutti gli elementi che vengono dopo. Questo nel caso peggiore ha complessità \mathcal{O}(S) dove S è la lunghezza del vector, che in questo caso può essere fino a Q. Facendo questa operazione per ogni query si arriva a una complessità \mathcal{O}(Q^2) che ovviamente non può stare nel time limit visti i constraints.
L’idea di fare una binary search non è sbagliata, ma ti serve una struttura dati che generalizzi questa idea nel caso in cui il tuo insieme di dati sia dinamico (cioè vari nel tempo). Questa struttura dati è convenientemente implementata nella STL con gli std::set.
Per concludere, può essere istruttivo considerare il suggerimento di @Fearingtable di semplificare la logica della funzione chiedi. Per quanto sia vero che quella funzione è sicuramente molto più complicata di quanto debba essere in realtà, questo ha un’importanza relativa, poiché comunque esegue in tempo logaritmico rispetto alla lunghezza del vector. Quello che veramente rallenta un sacco il programma sono le funzioni apri e chiudi che, per quanto siano lunghe rispettivamente 2 e 1 linea, nascondono un deleterio fattore lineare.
Spero di aver chiarito un po’ di dubbi, se così non fosse chiedete pure.
Tutto corretto. L’inserzione e l’eliminazione da un set hanno complessità \mathcal{O}(\log S) rispetto a \mathcal{O}(S) da un vector (S è sempre il numero di elementi). La binary search sul set è implementata dai metodi upper_bound e lower_bound.
Non puoi accedere ai test ufficiali per ovvie ragioni (i.e. potresti barare in modi creativi); puoi generare casi a mano, ma di solito generare casi grossi non serve: solo analizzando la complessità della tua soluzione e i constraints dovresti sapere se la tua soluzione passa o meno.
Ciao, scusami se ti disturbo ancora, ma non riesco a trovare un modo per trasformare un std::vector::iterator in un std::set::iterator. Ho cercato dappertutto e purtroppo chatgpt è bloccato, quindi cerco aiuto qui.
Scusami, dovevo spiegarmi meglio.
Praticamente sono arrivato al ragionamento che l’elemento con la differenza minore (sotto valore assoluto) da ‘p’ è il valore “corretto”. Il mio scopo è di ritornare l’ultima differenza minore, quindi se ipoteticamente ce ne sono 2 uguali, ritorno quella che “viene dopo”, così da rispettare quello che dice il problema (con 2 stazioni a pari distanza, ritorna quella situata al chilometro maggiore). Quello che volevo fare io era trovare l’ultima differenza e poi puntare all’elemento allo stesso “indice” sul set corrispondente alla differenza minima. Ti allego il codice:
long long chiedi(long long p){
vector<long long> differenze(autogrill.size());
vector<long long>::iterator it;
if(autogrill.size()==0){
return -1;
}else{
differenzeSet(differenze, p);
//modo per trovare l'ultimo minimo elemento (es. memorizzarlo in un indice n)
//fare in modo che l'indice n ottenuto dal passo precedente punti all'n-esimo elemento del set
}
}
Mi rendo conto che potrei fare il casting di un set in un vector e poi accedere da lì l’indice, ma ho trovato che la complessità è O(S*log(S)), e non vorrei eccedere il TL del problema nuovamente. Mi scuso ancora per eventuali incomprensioni e ringrazio per l’aiuto.
P.S.: ho letto che esiste il metodo set.lower_bound() (e anche il upper_bound()), ma questi ritornano solamente il valore più vicino MAGGIORE.
No ma non devi castare il set a un vettore. Il metodo dei set lower_bound(x) fa già quello che ti serve per risolvere questo problema, restituendoti l’iteratore al primo elemento maggiore di x nel set. Poi da lì controlli anche l’iteratore precedente con prev() e dai la risposta. Se hai dei dubbi su C++ ti consiglio di consultare la documentazione su cppreference.
Grazie mille! Ho risolto finalmente il problema (mi domando onestamente come abbia fatto a non pensarci prima)
Ultima domanda: se prev() non esiste (intendo che non ci sono elementi prima dell’iteratore specificato come argomento) restituisce un set.begin() o un set.end()? Non lo ho trovato nella documentazione e mi sembra logico che debba puntare all’inizio, ma volevo solo un chiarimento.
Non ci scommetterei, però penso che fare prev() sul primo iteratore sia undefined behaviour.
In ogni caso se il tuo iteratore (chiamiamolo it) è il primo del set allora non ti serve neanche controllare il precedente. Un semplice if (it != set.begin()) {...} dovrebbe bastare per escludere il caso.
.
