2019 North American Practice Contest 5

#### Start

2019-02-02 18:00 UTC

## 2019 North American Practice Contest 5

#### End

2019-02-02 23:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -201 days 14:44:10

5:00:00

0:00:00

# Problem EEquality Control

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 way, no team will be disadvantaged by not having mastered any of the allowed languages. 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:

• [x$_1$,…,x$_ n$] is the constructor for lists. It returns the integers inside the brackets in their given order.

• concat(<Expr$_1$>,<Expr$_2$>) returns a list of all the integers returned when evaluating the expression <Expr$_1$> followed by all of the integers returned when evaluating <Expr$_2$>.

• shuffle(<Expr>) returns a list of all the integers returned by <Expr>, rearranged according to a uniformly random permutation, i.e., each permutation of the elements is used with equal probability.

• 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 exressions both take the list [1,2] as input and return one of the lists [1,2] and [2,1], each with probability $0.5$ (independently of each other). The outer concat operator takes the two returned lists as its input and returns their concatenation. I.e., it returns one of the lists [1,2,1,2], [1,2,2,1], [2,1,1,2], and [2,1,2,1], each with probability $0.25$.

Naturally, we cannot use byte-by-byte output comparison any more when teams submit their solutions in Balloon, as its output is probabilistic. The judge server instead 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 $L$ of integers, both programs have an equal probability of returning $L$.

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

## Input

The input consists of:

• One line containing a string A, the first program.

• One line containing a string B, the second program.

Each program is a syntactically valid Balloon program with between $3$ and $10^6$ characters, and contains neither spacing nor empty lists (i.e., the strings “ ” or “[]” do not occur in the input).

Each integer in each program is greater than $0$ and less than $10^{9}$.

## Output

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

Sample Input 1 Sample Output 1
concat(shuffle([1,2]),shuffle([1,2]))
shuffle([1,2,1,2])

not equal

Sample Input 2 Sample Output 2
sorted(concat([3,2,1],[4,5,6]))
[1,2,3,4,5,6]

equal

Sample Input 3 Sample Output 3
concat(sorted([4,3,2,1]),shuffle([1]))
concat(concat([1,2,3],shuffle([4])),sorted([1]))

equal