Equality Control
Time limit2sMemory limit512 MB
Given two BALLOON programs built from list literals, concat, shuffle, and sorted, decide whether they return every list with the same probability.
- Level
Medium7 of 10
- Topics
- String, Recursion, Implementation
- Solved
- No attempts yet
Problem
In programming contest circles, one of the most important roles is that of the Chief Equality Officer (CEO). This person makes sure that every team has an equal chance of winning the contest. After last year's NWERC, the current CEO, Gregor, spent a long time thinking about how to make the contest even fairer.
His answer is to make a new programming language the only one allowed for submissions. No team is disadvantaged by not having mastered one of the allowed languages. The 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 has 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 the integers from evaluating<Expr1>, followed by the integers from evaluating<Expr2>.shuffle(<Expr>)returns the integers from<Expr>rearranged by a uniformly random permutation. Each permutation is used with equal probability.sorted(<Expr>)returns the integers from<Expr>rearranged in non-decreasing order.
For example, take concat(shuffle([1,2]),shuffle([1,2])). Each shuffle takes [1,2] and returns either [1,2] or [2,1], each with probability , independently of the other. The outer concat joins the two results. So it returns [1,2,1,2], [1,2,2,1], [2,1,1,2], or [2,1,2,1], each with probability .
Output is probabilistic, so submissions cannot be checked by comparing bytes. The judge instead checks whether a submitted program is equivalent to the judges' sample solution. Two programs are equivalent if, for every list of integers, both programs return with the same probability.
Your task is 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 has between 3 and characters. Programs contain no spaces and no empty lists, so the strings (a space) and [] never occur in the input. Each integer in a program is greater than 0 and less than .
Output
Print equal if the two programs are equivalent, and not equal otherwise.