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 )

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
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.
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
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.
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.
Hi,
as this is the one and only post for problem #10904, I'll ask here:
do you have some more testcases 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
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!