Binary Operator Solution Google Kickstart 2021

by

Binary Operator Solution Google Kickstart 2021

Problem

You are given a list of valid arithmetic expressions using non-negative integers, parentheses (), plus +, multiply *, and an extra operator #. The expressions are fully parenthesized and in infix notation.

A fully parenthesized expression is an expression where every operator and its operands are wrapped in a single parenthesis.
For example, the expression x+yx+y becomes (x+y)(x+y) when fully parenthesized, and x+y+zx+y+z becomes ((x+y)+z)((x+y)+z). However, 00 is still 00 when fully parenthesized, because it consists of a single number and no operators. ((x+y))((x+y)) is not considered fully parenthesized because it has redundant parentheses.

The operators + and * denote addition and multiplication, and # can be any total function.

You want to group the expressions into equivalence classes, where expressions are in the same equivalence class if and only if they are guaranteed to result in the same numeric value, regardless of which function # represents.

You can assume that # represents the same function across all expressions in a given test case. That might mean that # represents some known function like addition or subtraction, but not both in different parts of the same test case.

For example, consider the following expressions:
F1F1=((1#(1+1))+((2#3)*2))
F2F2=(((2#3)+(1#2))+(2#3))
F3F3=((2*(2#3))+(1#2)).

Let A = 1#2, and let B = 2#3. Then we can say F1F1=F2F2=F3F3, regardless of the function # represents because the expressions can be rewritten as:
F1F1=((1#2)+((2#3)*2))=(A+(B*2))=(A+2B)
F2F2=(((2#3)+(2#3))+(1#2))=((B+B)+A)=(A+2B)
F3F3=((2*(2#3))+(1#2))=((2*B)+A)=(A+2B).

However, consider the expressions F4F4=((0#0)+(0#0)) and F5F5=(0#0). If # represents addition, then F4=F5F4=F5. However, if # is f(x,y)=Cf(x,y)=C, such that CC is a non-zero integer, then F4≠F5F4≠F5 since 2C≠C2C≠C. Therefore F4F4 and F5F5 are not in the same equivalence class.

Input

The first line of the input gives the number of test cases, TT. TT test cases follow. Each test case begins with a line containing the integer NN. NN lines follow. ii-th line contains one expression, EiEi.

Output

For each test case, output one line containing Case #xx: Y1,Y2,…,YNY1,Y2,…,YN, where xx is the test case number (starting from 1) and YiYi is the lexicographically smallest sequence satisfying the conditions below:

  1. 1≤Yi≤Z1≤Yi≤Z, where ZZ denotes the total number of equivalence classes in a given test case.
  2. Yi=YjYi=Yj if and only if EiEi and EjEj are in the same equivalence class.

Limits

Time limit: 20 seconds.
Memory limit: 1 GB.
1≤T≤1001≤T≤100
1≤N≤1001≤N≤100
The length of EiEi is at most 100100, for all ii.
EiEi will be valid, for all ii.

Test Set 1

No more than one # in each expression.

Test Set 2

No additional constraints.

Sample

Note: there are additional samples that are not run on submissions down below.

Sample Input

3
7
(1*(1#2))
(0*(1#2))
(1#2)
0
(3*0)
((1#2)*1)
(((1+(1#2))+3)*0)
5
(1*((1+(2#2))+3))
((0+(2#2))+4)
(100#2)
(((1+(2#2))+3)*1)
((50*2)#2)
2
(9999999999999999999999999999999999999999+1)
(100000000000000000000*100000000000000000000)

Sample Output

Case #1: 1 2 1 2 2 1 2
Case #2: 1 1 2 1 2
Case #3: 1 1

This sample test set contains 33 test cases.

Test case 1 has 77 expressions and a total of 22 equivalence classes, denoted G1G1 and G2G2.
E1E1=(1*(1#2)), E2E2=(0*(1#2)), ……, E7E7=(((1+(1#2))+3)*0).E1E1, E3E3, and E6E6 belong to G1G1, and E2E2, E4E4, E5E5, and E7E7 belong to G2G2.
There are 22 sequences of YiYi that satisfy the requirement about equivalence classes in test case 1: 2 1 2 1 1 2 1 and 1 2 1 2 2 1 2.
Since 1 2 1 2 2 1 2 is the lexicographically smaller one, the output for test case 1 is: Case #1: 1 2 1 2 2 1 2.

Test case 2 has 55 expressions and a total of 22 equivalence classes, denoted G1G1 and G2G2.
E1E1, E2E2, and E4E4 belong to G1G1, and E3E3 and E5E5 belong to G2G2.
Therefore, the output for test case 2 is: Case #2: 1 1 2 1 2.

Test case 3 has 22 expressions that do not contain any #.
These two expressions evaluate to the same value, and therefore belong to the same equivalence class.

Additional Sample – Test Set 2

The following additional sample fits the limits of Test Set 2. It will not be run against your submitted solutions.

Sample Input

1
9
((2*(2#3))+(1#2))
(0*(1#2))
0
((1#(1+1))+((2#3)*2))
(3*0)
(1#(2#3))
(((2#3)+(1#2))+(2#3))
(4#7)
(7#4)

Sample Output

Case #1: 1 2 2 1 2 3 1 4 5

In the provided sample, there are a total of 55 equivalence classes. The first expression in the input is ((2*(2#3))+(1#2)). All expressions from its equivalence class are denoted with 1 in the output. The equivalence class denoted with 2 consists of (0*(1#2)), 0, and (3*0). The equivalence class denoted with 3 consists of (1#(2#3)). Finally, the last two expressions, (4#7) and (7#4), are not equivalent to any of the prior expressions or to one another. Note that 2 1 1 2 1 3 2 5 4 is one of many other sequences that satisfy the requirement about equivalence classes the given input, but it is not a correct answer because this sequence is not the lexicographically smallest one.

Also Read:

Solution:

from random import randint as rnd
magic = 10 ** 10

d = dict()

def f(num1, num2):
    s = str(num1) + '#' + str(num2)
    if (s not in d):
        d[s] = rnd(1, magic)
    return d[s]

op = ['+', '-', '*', '#']

def calc(e):
    bal = 0
    j = -1
    j1 = -1
    for i in range(len(e)):
        if (e[i] == '('):
            bal += 1
        if (e[i] == ')'):
            bal -= 1
            if (bal == 0 and j1 == -1):
                j1 = i
        if (bal == 0 and e[i] in op):
            j = i
    if (e.isdigit()):
        return int(e)
    if (e[0] == '(' and j1 == len(e) - 1):
        return calc(e[1:-1])
    oper = e[j]
    if oper == '+':
        return calc(e[:j]) + calc(e[j+1:])
    elif (oper == '-'):
        return calc(e[:j]) - calc(e[j+1:])
    elif oper == '*':
        return calc(e[:j]) * calc(e[j+1:])
    else:
        return f(calc(e[:j]), calc(e[j+1:]))

def solve(t):
    d.clear()
    n = int(input())
    res = []
    ans = []
    rs = dict()
    cnt = 0
    for i in range(n):
        e = input()
        res.append(calc(e))
    for i in range(n):
        if (res[i] not in rs):
            rs[res[i]] = cnt + 1
            cnt += 1
        ans.append(rs[res[i]])
    print(f"Case #{t}:", end = ' ')
    print(*ans)

t = int(input())
for i in range(t):
    solve(i + 1)

Binary Operator Solution Google Kickstart 2021

Leave a Comment