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
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

10904 - Structural Equivalence

Post by Krzysztof Duleba »

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

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

Post by Martin Macko »

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.

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

Post by Krzysztof Duleba »

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

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

Post by Martin Macko »

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.

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

Post by Krzysztof Duleba »

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

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

Post by Martin Macko »

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.

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

Post by Krzysztof Duleba »

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 »

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

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

Post by Krzysztof Duleba »

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; 

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 »

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

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

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

Post by Krzysztof Duleba »

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

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 »

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