11060 - Beverages

[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 ).

[Martin Macko]

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:

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.

[Martin Macko]

(my 3rd sample output is: apple-juice wine vodka beer martini rum whiskey cachaca gin ).

Wait... where have you lost tequila?

[little joey]

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:

Code: Select all

3
a
b
c
1
c a

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.

[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.

[Mg9H]

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:

Code: Select all

3
a
b
c
1
c a

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.

[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).

[little joey]

Please read 'drank' in stead of 'drunk' in my previous posts. My knowledge of english strong verbs is a bit weak...

[Mg9H]

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).

[Darko]

Please read 'drank' in stead of 'drunk' in my previous posts.

I think 'drunk' is correct there.

[joemmanuel]

(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)

[Martin Macko]

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.

[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.

[Martin Macko]

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.

[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?