11060 - Beverages

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

joemmanuel
New poster
Posts: 4
Joined: Tue Aug 01, 2006 9:01 pm

Post by joemmanuel » Mon Aug 07, 2006 1:35 am

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

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Mon Aug 07, 2006 8:10 am

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.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Mon Aug 07, 2006 8:14 am

joemmanuel wrote:(my 3rd sample output is: apple-juice wine vodka beer martini rum whiskey cachaca gin ).
Wait... where have you lost tequila? :P

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Aug 07, 2006 12:38 pm

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:

Code: Select all

3
a
b
c
1
c a
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.

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Mon Aug 07, 2006 12:43 pm

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.

User avatar
Mg9H
New poster
Posts: 18
Joined: Sun Oct 14, 2001 2:00 am
Location: Ohio University
Contact:

Post by Mg9H » Mon Aug 07, 2006 12:59 pm

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:

Code: Select all

3
a
b
c
1
c a
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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Aug 07, 2006 1:13 pm

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Aug 07, 2006 1:18 pm

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

User avatar
Mg9H
New poster
Posts: 18
Joined: Sun Oct 14, 2001 2:00 am
Location: Ohio University
Contact:

Post by Mg9H » Mon Aug 07, 2006 2:43 pm

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

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Mon Aug 07, 2006 6:18 pm

Please read 'drank' in stead of 'drunk' in my previous posts.
I think 'drunk' is correct there.

joemmanuel
New poster
Posts: 4
Joined: Tue Aug 01, 2006 9:01 pm

Post by joemmanuel » Tue Aug 08, 2006 4:23 pm

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? :P
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)

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Tue Aug 08, 2006 4:54 pm

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Aug 08, 2006 5:59 pm

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.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Wed Aug 09, 2006 9:49 am

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.

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Fri Aug 11, 2006 3:06 pm

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?

Post Reply

Return to “Volume 110 (11000-11099)”