#include <stdio.h> #include <string.h> #include
using namespace std;
int N,K,M; #define NMAX 1000
int coda[2][NMAX];
vector < vector<pair<int,int>>> nodi;
int miaDKS(int);
int main()
{
int da,a,i,v;
FILE *fin=freopen(“input.txt”,“r”,stdin);
FILE fout=freopen(“output.txt”,“w”,stdout);
scanf(“%d %d %d”,&K,&N,&M);
nodi.resize(N);
for( i=0;i<M;i++){
scanf(“%d”,&da);
scanf(“%d”,&a);
scanf(“%d”,&v);
nodi[da].push_back(make_pair(a,v));
}
printf(“%d\n”,miaDKS(K));
return 0;
}
int miaDKS(int voli){
int a=0,b=1;
int lung;
int succ,costo,costovolo;
unsigned int j,k;
for(k=0;k<nodi[0].size();k++){
succ=nodi[0][k].first;
costovolo=nodi[0][k].second;
if(coda[0][succ]<costovolo)
coda[0][succ]=costovolo;
}
lung=1;
while( lung <voli){
for(j=0;j<N;j++){
if(coda[a][j]){
costo=coda[a][j];
for(k=0;k<nodi[j].size();k++){
succ=nodi[j][k].first;
costovolo=nodi[j][k].second;
if(coda[b][succ]<costo+costovolo)
coda[b][succ]=costo+costovolo;
}
}
}
lung++;
if(!a){
a=1;
b=0;
}
else{
a=0;
b=1;
}
if(lung<voli)
memset(coda[b],0,Nsizeof(int));
}
return coda[a][0];
}
ma con il test case banale riportato sotto:
2 2 2
0 1 0
1 0 1
trova 0 come risultato invece di 1 (anche se basta poco per effettuare la correzione).
Ennesima dimostrazione del fatto che ci può essere differenza fra il fare 100 e trovare una soluzione corretta??
Buongiorno, ci tengo a precisare che quello che lei afferma è correttissimo e nessuno direbbe mai il contrario, fare 100 non significa avere trovato la soluzione corretta, dato che il numero dei test cases possibili è troppo grande da far valutare ad un computer. Perciò, quando si vanno a generare i test cases di un problema si cerca di tagliare fuori famiglie di soluzioni incorrette più grandi e più aspecifiche possibili (tipo soluzioni in O(N^2) o soluzioni greedy).
Se ad esempio avessi sottoposto una soluzione a questo problema che si rifiuti di passare per un arco che ha peso 13797 se questo arco parte dal nodo 0, la soluzione potrebbe essere definita corretta al 100%? No ovviamente. Ha però senso includere in un test case un nodo di peso 13797 che parte da 0? Assolutamente no!
Eppure la stessa cosa fa il suo programma, solo che il nodo è di peso 0.
Con questo non sto accusando nessuno di nulla, cerco solo di spiegare che non c’è persona al mondo che possa scovare ogni singolo corner case di un problema e metterlo nella valutazione.
Piccola aggiunta che non c’entra molto: nella mia breve ma intensa carriera olimpionica mi sono reso conto che errori del genere capitano tendenzialmente nei problemi più semplici (probabilmente perché nessuno si scervella le ore a cercare tc strong per un problemino da 20 minuti), in task come Pyramid Base, ad esempio, la questione dovrebbe essere più complicata
Buonasera, sono perfettamente d’accordo su tutta la sua trattazione generale.
Nel caso specifico qualcosa non mi convince del tutto:
Lo 0 in tanti problemi è un valore limite che va trattato come caso a parte, paragonarlo ad un generico valore non mi sembra del tutto appropriato. Inoltre chi ha ideato il problema ha voluto prevedere anche voli (estremamente improbabili nella realtà) di tale lunghezza e quindi ci si potrebbe aspettare che abbia voluto vedere se i solutori gestivano correttamente anche questi voli. Vedere che un programma che non lo fa la passa liscia lascia un po’ perplessi, tutto qui,
Solo per essere precisi, il mio programma materialmente non scarta alcun arco, ma, a partire dal secondo volo, evita di prendere in considerazione tutti quegli aeroporti ai quali si giunge con percorso di lunghezza 0, considerandoli come aeroporti non raggiunti con il volo precedente.
Se sapevi che il tuo codice aveva un bug, allora perché non l’hai corretto?
Quello che intendo è che se io scrivessi una soluzione con un bug e questa soluzione facesse 100, non mi accorgerei di questo bug! È semplice scrivere soluzioni volutamente con un corner case in modo da rompere i test case, ma è difficile creare test case che coprano ogni corner case.
Il generatore di questo problema è piuttosto lungo (100 righe) e complesso per appunto evitare che le soluzioni sbagliate passino. L’autore del task si è concentrato più sull’evitare che passino soluzioni greedy piuttosto che soluzioni corrette ma che non considerano corner case. Infatti la tua soluzione è corretta in sé, solo che non copre un corner case. È giusto dire che una soluzione che non copre il caso in cui ci sia un arco con peso 13797 uscente dal nodo 0 sia sbagliata? Secondo me no.
La genesi del codice che ho postato è ben altra:
Prima avevo scritto un codice che non aveva quel bug ed ho fatto 100 con quello!
Poi ho provato a vedere cosa succedeva con quello con il bug aspettandomi che non facesse 100 invece l’ha fatto e mi è sembrato giusto farlo presente, di nuovo tutto qui.
Per completezza il codice che non ha quel bug!
#include <stdio.h> #include <string.h> #include
using namespace std;
int N,K,M; #define NMAX 1000
int coda[2][NMAX];
vector < vector<pair<int,int>>> nodi;
int miaDKS(int);
int main()
{
int da,a,i,v;
FILE *fin=freopen(“input.txt”,“r”,stdin);
FILE fout=freopen(“output.txt”,“w”,stdout);
scanf("%d %d %d",&K,&N,&M);
nodi.resize(N);
for( i=0;i<M;i++){
scanf("%d",&da);
scanf("%d",&a);
scanf("%d",&v);
nodi[da].push_back(make_pair(a,v+1));
}
printf("%d\n",miaDKS(K));
return 0;
}
int miaDKS(int voli){
int a=0,b=1;
int lung;
int succ,costo,costovolo;
unsigned int j,k;
for(k=0;k<nodi[0].size();k++){
succ=nodi[0][k].first;
costovolo=nodi[0][k].second;
if(coda[0][succ]<costovolo)
coda[0][succ]=costovolo;
}
lung=1;
while( lung <voli){
for(j=0;j<N;j++){
if(coda[a][j]){
costo=coda[a][j];
for(k=0;k<nodi[j].size();k++){
succ=nodi[j][k].first;
costovolo=nodi[j][k].second;
if(coda[b][succ]<costo+costovolo)
coda[b][succ]=costo+costovolo;
}
}
}
lung++;
if(!a){
a=1;
b=0;
}
else{
a=0;
b=1;
}
if(lung<voli)
memset(coda[b],0,N sizeof(int));
}
return coda[a][0]-voli;
}
