10904 - Structural Equivalence

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

Moderator: Board moderators

Post Reply
User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

10904 - Structural Equivalence

Post by Krzysztof Duleba » Thu Nov 03, 2005 10:48 pm

Any hints? I'm out of luck here. Are cases like the following allowed?

Code: Select all

type A = Z
type B = Z
--
What should I return for

Code: Select all

type A =   int
type B = A
type C = int
type X  = struct(A B)
type Y = struct(B   A)
type Z = struct(A Z)
type   S = struct(A S)
type W = struct(B R)
type R = struct(C W)
-
 type A = int
type B = char
type C = B
     type D = C
type E = D
type F = E
type G = F
type H = struct(B B C C D)
type J = struct(C G F A B)
-
type A = B
type B = A
type C = B
type D = int
type E = char
-
type A = struct(A A)
type B = struct(B B)
type C = struct(A A)
type D = struct(C A)
type E = struct(I A)
type F = struct(A I)
type G = struct(Z C)
type I = int
type Z = char
-
type A = Z
type B = Z
-
type A = C
type B = D
type D = C
type C = int
-
type A = B
type B = A
type C = D
type D = int
-
type A = Z
type B = Z
-
type A = A
type B = B
type C = D
type D = C
type E = F
type F = G
type G = int
type H = I
type I = char
type J = K
type K = L
type L = M
type M = N
type N = O
type O = L
type S = T
type U = V
type P = struct (P P)
type Q = struct (Q   Q)
type X = struct(Z Z)
type Y = struct (Z Z  )
--
My answers are

Code: Select all

A B C
R S W Z
X Y

A
B C D E F G
H
J

A B C
D
E

A B C D
E
F
G
I
Z

A B

A B C D

A B
C D

A B

A B C D J K L M N O
E F G
H I
P Q
S U
X Y

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 » Sat Dec 10, 2005 9:58 pm

Krzysztof Duleba wrote:Any hints? I'm out of luck here. Are cases like the following allowed?

Code: Select all

type A = Z
type B = Z
--
No, it's not allowed, because Z is not defined. My AC would abort() in such case.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sat Dec 10, 2005 11:57 pm

Thanks. Then what's the right answer for the following test?

Code: Select all

type A =   int

type B = A
type C = int
type X  = struct(A B)
type Y = struct(B   A)
type Z = struct(A Z)
type   S = struct(A S)
type W = struct(B R)
type R = struct(C W)
-
type A = int
type B = char
type C = B
type D = C
type E = D
type F = E
type G = F
type H = struct(B B C C D)
type J = struct(C G F A B)
-
type A = B
type B = A
type C = B
type D = int
type E = char
-
type A = struct(A A)
type B = struct(B B)
type C = struct(A A)
type D = struct(C A)
type E = struct(I A)
type F = struct(A I)
type G = struct(Z C)
type I = int
type Z = char
-
type A = C
type B = D
type D = C
type C = int
-
type A = B
type B = A
type C = D
type D = int
-
type A = B
type B = A
type C = D
type D = E
type E = C
I have

Code: Select all

A B C
R S W Z
X Y

A
B C D E F G
H
J

A B C
D
E

A B C D
E
F
G
I
Z

A B C D

A B
C D

A B C D E

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 » Sun Dec 11, 2005 12:23 am

Krzysztof Duleba wrote:Thanks. Then what's the right answer for the following test?
Hard to say. My AC's output for the 3rd case is

Code: Select all

A B C D E
and for the 6th

Code: Select all

A B C D
But your answers give me more sence. Thus, there are probably no such cyclical cases in the tests. My solution just greedily expands the variables into at most a certain depth and then compares the structure.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sun Dec 11, 2005 12:40 am

Are you sure about your output? In case 3, D = int, E = char. How come they are equivalent? You also missed E in case 6.

In my solution I treat types as trees (possibly infinite, but that's not a problem) with labelled leaves. I say that types are equivalent iff their trees are identical. I tested several modifications and different implementations of this approach and still WA :-(

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 » Sun Dec 11, 2005 12:58 am

Krzysztof Duleba wrote:Are you sure about your output? In case 3, D = int, E = char. How come they are equivalent? You also missed E in case 6.
Well, I'm not... actually I'm sure my answer is wrong, but that's what my AC outputs. D=E happend by comparing them to A. As A has not fully defined type my solution after a few iterations gave comparing A with D up and said it couldn't find a difference between them, thus A=D. The same happend for A=E. I don't know if there are such not fully defined types in the test cases. Probably not, because I wouldn't have got AC if there were such cases.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sun Dec 11, 2005 1:08 am

Thanks for help. Now I know what was wrong. There are commas in the input! My solution was ok (or, at least, acceptable ;-) ) all the time. This is very disappointing.

Anyway, the problem would be much nicer if the test cases were harder and included infinite cases.

t-s-n
New poster
Posts: 1
Joined: Sat May 20, 2006 2:21 pm
Location: Germany, Nuremberg

too crazy...

Post by t-s-n » Sat May 20, 2006 2:25 pm

Hi,
as this is the one and only post for problem #10904, I'll ask here:

do you have some more test-cases for this problem ?

What's the output for:
type A = int
type B = char
type C = A
-
type A = B
type B = A
-
type A = int
type B = char
type C = struct(A B)
type D = struct(A A)
type E = struct(B A)
type F = struct(B B)
-
type A = int
type B = int
type C = struct(A B)
type D = struct(A A)
type E = struct(B A)
type F = struct(B B)
--
My output says:
A C
B

A B

A
B
C
D
E
F

A B
C D E F

Thanx for your help,
Thomas

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sat May 20, 2006 2:36 pm

Same here.

Make sure to handle those damn commas correctly. I'm not sure, but there may be some tabs too (I have this line in my code, it could be important):

Code: Select all

while(str[n] == ' ' || str[n] == '\t' || str[n] == ',')++n; 

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

Re: too crazy...

Post by Martin Macko » Sat May 20, 2006 10:35 pm

t-s-n wrote:Hi,
as this is the one and only post for problem #10904, I'll ask here:

do you have some more test-cases for this problem ?
My AC's output is the same, too. Post your outputs to some more test cases so I can compare them to mine.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Sun Jun 04, 2006 6:27 pm

Infinite things make me sick..
A = struct (int A int)
B = struct (int B)
Are these two equivalent? A will only have even number of ints but it's not true for B.

Mmm.. Am I missing something?
JongMan @ Yonsei

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Mon Jun 05, 2006 8:05 am

They are not equivalent - just draw them and take a look.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Mon Jun 05, 2006 8:40 am

Thanks for the answer.

However, the problem statement is still confusing. The only definition of "equivalence" it gives is "if they are both structures containing equivalent types in the same order".

Then, are these two equivalent?
type A = struct(int A)
type B = struct(B int)
If we have to merely compare the parsed trees, these should not be equivalent.. however they fit in the above definition... So I don't know. Someone please clarify!
JongMan @ Yonsei

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Jun 05, 2006 9:03 am

The first types in structures: 'int' and 'B' are clearly not equivalent, so by definition, A and B are also not equivalent.

Post Reply

Return to “Volume 109 (10900-10999)”