#P16988. [NWERC 2018] Equality Control

[NWERC 2018] Equality Control

Problem Description

In programming contest circles, one of the most important roles is that of the Chief Equality Officer (CEO). This person is responsible for making sure that every team has an equal chance of winning the contest. Since last year's NWERC the current CEO, Gregor, has thought at length about how to make the contest even more fair and equal.

His answer is to introduce a new programming language as the only one allowed for submissions. This language is called BALLOON, short for Building A Long List Of Ordinary Numbers. Its only data type is the list of integers. To keep the language fast, it contains only four instructions:

  • [x1,...,xn] is the constructor for lists. It returns the integers inside the brackets in their given order.
  • concat(<Expr1>,<Expr2>) returns a list of all the integers returned when evaluating <Expr1> followed by all of the integers returned when evaluating <Expr2>.
  • shuffle(<Expr>) returns a list of all the integers returned by <Expr>, rearranged according to a uniformly random permutation.
  • sorted(<Expr>) returns a list of all the integers returned by <Expr>, rearranged into non-decreasing order.

As an example, consider the first expression of Sample Input 1. The two shuffle expressions both take the list [1,2] as input and return one of [1,2] and [2,1], each with probability 0.50.5, independently. The outer concat returns their concatenation. Thus it returns one of [1,2,1,2], [1,2,2,1], [2,1,1,2], and [2,1,2,1], each with probability 0.250.25.

The judge server has to check whether a submitted program is equivalent to the sample solution created by the judges. Two programs are equivalent if for any list LL of integers, both programs have an equal probability of returning LL.

It is your task to determine whether two given BALLOON programs are equivalent.

Input Format

The input consists of:

  • One line containing a string AA, the first program.
  • One line containing a string BB, the second program.

Each program is a syntactically valid BALLOON program with between 33 and 10610^6 characters, and contains neither spacing nor empty lists. Each integer is greater than 00 and less than 10910^9.

Output Format

If the two programs are equivalent, output equal, otherwise output not equal.

concat(shuffle([1,2]),shuffle([1,2]))
shuffle([1,2,1,2])
not equal
sorted(concat([3,2,1],[4,5,6]))
[1,2,3,4,5,6]
equal
concat(sorted([4,3,2,1]),shuffle([1]))
concat(concat([1,2,3],shuffle([4])),sorted([1]))
equal