Page 2 of 7
Posted: Mon Aug 07, 2006 1:35 am
by joemmanuel
Hi all.
I did a Topollogical Sort as follows and got WA:
Code: Select all
#include <stdio.h>
#include <map>
#include <string.h>
using namespace std;
char list[101][60];
int n,m;
int mat[101][101];
int pos(char a[]){
int i;
for(i=0;i<n;i++){
if(strcmp(a,list[i])==0)
return i;
}
}
int num[101];
int ts(char a[]){
int i;
int p=pos(a);
if(num[p]!=-1)
return num[p];
int max=0;
for(i=0;i<n;i++){
int t=0;
char tt[100];
if(mat[i][p]==1){
strcpy(tt,list[i]);
t=ts(tt);
}
if(t>max)
max=t;
}
if(max+1>num[p])
num[p]=max+1;
return num[p];
}
int main(){
int c=0;
while(scanf("%d", &n)!=EOF){
c++;
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
mat[i][j]=0;
for(i=0;i<n;i++){
scanf("%s", list[i]);
num[i]=-1;
}
scanf("%d", &m);
for(i=0;i<m;i++){
char t1[102],t2[102];
scanf("%s%s", t1,t2);
mat[pos(t1)][pos(t2)]=1;
}
for(i=0;i<n;i++)
if(num[i]==-1){
char ini[60];
strcpy(ini,list[i]);
ts(ini);
}
printf("Case #%d: Dilbert should drink beverages in this order:",c);
while(1){
int min=20000000;
int ii;
for(i=0;i<n;i++){
if(num[i]<min){
min=num[i]; ii=i;
}
}
if(min==20000000)
break;
num[ii]=20000000;
printf(" %s",list[ii]);
}
printf(".\n\n");
}
return 0;
}
But i don't understand very good the third test case. Because Martini got Degree 2, so it must be printed in the same "level" that beer and vodka, isn't so?
Surelly, i'm understanding bad the problem. Can you help me?
(my 3rd sample output is: apple-juice wine vodka beer martini rum whiskey cachaca gin ).
Posted: Mon Aug 07, 2006 8:10 am
by Martin Macko
joemmanuel wrote: But i don't understand very good the third test case. Because Martini got Degree 2, so it must be printed in the same "level" that beer and vodka, isn't so?
Surelly, i'm understanding bad the problem. Can you help me?
(my 3rd sample output is: apple-juice wine vodka beer martini rum whiskey cachaca gin ).
As it has already been posted here:
problem statement wrote:In the case there is no relation between two beverages Dilbert should start drinking the one that appears first in the input.
Therefore, if you have some beverages on the same "level" print them in order they were written on the input.
Posted: Mon Aug 07, 2006 8:14 am
by Martin Macko
joemmanuel wrote:(my 3rd sample output is: apple-juice wine vodka beer martini rum whiskey cachaca gin ).
Wait... where have you lost tequila?
Posted: Mon Aug 07, 2006 12:38 pm
by little joey
Darko wrote:I assumed there were no cycles - because they didn't say what to do in the case of one.
I am still not sure what I did wrong with my solution, it was supposed to be a simple topological sort, right?
What is output for this:
mf wrote:I get:
Code:
Case #1: Dilbert should drink beverages in this order: b c a.
Well, that solution is obviously wrong: since there is no relationship between b and a and b is listed later than a, b should be drunk after a.
In fact none of the 6 permutations of a, b and c gives a valid drinking order, so this input is illegal.
IMO this signals a weakness in the problem description: the description doesn't exclude inputs like these, but doesn't describe what to do if they occur. The fact that such inputs don't actually occur in the judge's input (which may or may not be, I haven't checked), should have been explicitly mentioned, I think.
Posted: Mon Aug 07, 2006 12:43 pm
by Wei-Ming Chen
To arsalan_mousavian , mf , mute , and sluga:
Thanks for all your help
I didn't read the problem careful and also because my poor Engilsh, I misunderstood the problem.
Now I got AC, thanks all very much.
Posted: Mon Aug 07, 2006 12:59 pm
by Mg9H
little joey wrote:Darko wrote:I assumed there were no cycles - because they didn't say what to do in the case of one.
I am still not sure what I did wrong with my solution, it was supposed to be a simple topological sort, right?
What is output for this:
mf wrote:I get:
Code:
Case #1: Dilbert should drink beverages in this order: b c a.
Well, that solution is obviously wrong: since there is no relationship between b and a and b is listed later than a, b should be drunk after a.
In fact none of the 6 permutations of a, b and c gives a valid drinking order, so this input is illegal.
Why do you say it is illegal? Doesn't the problem state that:
In the case there is no relation between two beverages Dilbert should start drinking the one that appears first in the input.
Posted: Mon Aug 07, 2006 1:13 pm
by little joey
There is no relation between a and b, so a must be drunk before b, because it appears earlier in the list;
There is a relation between a and c that dictates that c should be drunk before a;
There is no relation between b and c, so b must be drunk before c, because it appears earlier in the list.
There is no ordering of a, b and c that fulfills all three constraints, so there is no answer to the input, so the input is illegal (can't be handeled without breaking the rules).
Posted: Mon Aug 07, 2006 1:18 pm
by little joey
Please read 'drank' in stead of 'drunk' in my previous posts. My knowledge of english strong verbs is a bit weak...
Posted: Mon Aug 07, 2006 2:43 pm
by Mg9H
little joey wrote:There is no relation between a and b, so a must be drunk before b, because it appears earlier in the list;
There is a relation between a and c that dictates that c should be drunk before a;
There is no relation between b and c, so b must be drunk before c, because it appears earlier in the list.
There is no ordering of a, b and c that fulfills all three constraints, so there is no answer to the input, so the input is illegal (can't be handeled without breaking the rules).
Aha, I get your point now. But I think almost everyone interpreted "no relation between two beverages" a & b as a & b has no relation and also there's nothing has less alcohol content than a & b (with the given M relations in the input).
Posted: Mon Aug 07, 2006 6:18 pm
by Darko
Please read 'drank' in stead of 'drunk' in my previous posts.
I think 'drunk' is correct there.
Posted: Tue Aug 08, 2006 4:23 pm
by joemmanuel
Martin Macko wrote:joemmanuel wrote:(my 3rd sample output is: apple-juice wine vodka beer martini rum whiskey cachaca gin ).
Wait... where have you lost tequila?
Sorry, ive pasted you a wrong ouput, my actually output says:
apple-juice wine vodka beer martini rum tequila whiskey cachaca gin.
Is that a correct answer? Can u help me with my algo? (pasted before)
Posted: Tue Aug 08, 2006 4:54 pm
by Martin Macko
little joey wrote:IMO this signals a weakness in the problem description: the description doesn't exclude inputs like these, but doesn't describe what to do if they occur. The fact that such inputs don't actually occur in the judge's input (which may or may not be, I haven't checked), should have been explicitly mentioned, I think.
Actually, there is such a case even in the third example of the problem statement. In this example there is no relation between
tequila and
whiskey and also no relation between
whiskey and
vodka. According to their order in the input
tequila must be drunk before
whiskey and
whiskey must be drunk before
vodka. However,
vodka is said to be less alcoholic then
tequila in the input, therefore it must be drunk before
tequila, which contradicts the order above.
IMHO, the problem statement should be rephrased somehow, so it would be consistent with judge's outputs.
Posted: Tue Aug 08, 2006 5:59 pm
by little joey
Yes, good analysis. I was so fed up with this problem, I didn't bother to look anymore after I got AC in my third attempt (although I knew my program wouldn't cover all possible cases). I guess the program should print "impossible" or "illegal" in such cases.
Posted: Wed Aug 09, 2006 9:49 am
by Martin Macko
little joey wrote:Yes, good analysis. I was so fed up with this problem, I didn't bother to look anymore after I got AC in my third attempt (although I knew my program wouldn't cover all possible cases). I guess the program should print "impossible" or "illegal" in such cases.
I guess the problemsetter meant to write that beverage
A should be brunk before beverage
B if
A has less alcohol content than
B or beverages
A and
B are
independent and beverage
A is earlier in the input, where two beverages
A and
B are
independent if and only if there is no (even indirect) alcoholic relation between them in the input
and there is no yet undrunk beverage C with less alcohol content than A or B.
I think the outputs for examples mentioned in the problem statement correspond to this definition. Also my AC assumed that.
Posted: Fri Aug 11, 2006 3:06 pm
by asif_rahman0
Please check my Input/Output:
Code: Select all
8
a
b
c
d
e
f
s
t
6
a e
a b
c d
e f
s t
a t
8
s
a
b
e
f
c
d
t
6
a e
a b
c d
e f
s t
a t
8
a
b
c
s
t
e
f
d
6
a b
a e
c d
e f
s t
a t
Code: Select all
Case #1: Dilbert should drink beverages in this order: a b c d e f s t.
Case #2: Dilbert should drink beverages in this order: s a b e f c d t.
Case #3: Dilbert should drink beverages in this order: a b c s t e f d.
Is it OK?