### PROBLEM LINKS

### DIFFICULTY

MEDIUM

### PREREQUISITES

Modular Arithmetic, Modular Multiplicative Inverse, Extended Euclids Algorithm, Ad Hoc

### PROBLEM

You are given a **Zenfix** expression. It consists of a sequence of **operators** (from the set **{ !, ^, /, *, +, - }**, in order of priority) and integers that fit **32-bit signed integer** type. Evaluate it according to the following algorithm.

finished = false repeat if there is a '!' operator followed by an integer then solve the leftmost such occurance else if there is an operator followed by 3 integers among all options, first choose the operator with maximum priority then choose the leftmost such occurance and solve it else if there is an operator followed by 2 integers among all options, first choose the operator with maximum pririty then choose the leftmost such occurance and solve it else stop

Print the operations you performed in each iteration. Print **‘OK’** if the evaluation ends with only **one** integer remaining. Print **‘NOT OK’** otherwise, as well as in case there was an **undefined** evaluation.

### QUICK EXPLANATION

There is indeed much challenge in solving an involved **detail** oriented problem. There are a few modular arithmetic insights that are necessary to solve the problem. Let us look at them

## 32 bit residues

Each operation should end in converting the result to its **32-bit residue.** The **32-bit residue** is equivalent to how 32-bit integer **overflows** are handled by machines. So unless you are using a language in which the 32-bit integer data type is not present, you do not have to care about how to handle **overflows.** Let them happen. They will give you the value you were looking for!

Otherwise, you have to **carefully** fit the return value to its **32-bit residue,** yourself.

## 32-bit factorial

The **factorial** operation was deceptively easy. At first, it might seem that you have to do **1000 * 2 ^{31}** multiplications in the worst case. But, since you have to find the 32-bit residue of the result, you know that if the result is divisible by

**2**then its

^{32},**32-bit residue**is

**0.**

We know that if **n!** is divisible by **2 ^{32},** then

**(n+k)!**is also divisible by

**2**for all positive

^{32},**k.**So if we find the smallest

**n,**for which

**n!**is divisible by

**2**then any

^{32}**(n+k)!**will be equal to

**0.**

This is very interesting because **34!** is the first value which is divisible by **2 ^{32}.** That means, we never have to do more than

**34 multiplications**to calculate any factorial!

There is an important detail that a lot of codes missed. When checking

if ( abs(x) > 33 ) { return; }

The above piece of code will not work for x = -2^{31}. This is because abs(-2147483648) = -2147483648. The abs function does not work for this value! ( And how our tester loves making, sure this is a case on which all codes should pass )

## 32-bit division

Division in Modular Arithmetic is quite non trivial. It is possible **iff** there is a **modular multiplicative inverse** of the **denominator.**

For **A / B,** this takes care of all the cases where **B is odd.** But what if **B is even?** Let us look at one way of handling that case

We wish to find aCsuch that B*C = A (in 32-bit residue) B*C + x*2^{32}= A

Our best bet here is to see if we can find **y** and **x** in the equation

B*y + x*2^{32}= 1

And multiply it by **A.** This means **C = y*A.**

But we’re considering the case where **B** is **even.** We already know that the above equation does not have a solution in this case. The only other hope is to cancel powers of two from the equation

B*C + x*2^{32}= A

Until when **B** is **odd.** Now,

- if the power of 2 that divides A is smaller than the power of 2 that divides B, then there is no answer.
- Only otherwise, we get an alternate equation, such as following

after dividing by 2^{k}where B / 2^{k}is odd. b*C + x*2^{32-k}= A/2^{k}

Of course, now we can find a solution of

b*y + x*2^{32-k}= 1

by using the **Extended Euclid’s Algorithm.** The value of **C** will be

y * (A / 2^{k}) modulo 2^{32-k }

As you can see, being modular arithmetic in a field of smaller size, it is possible to have multiple correct values of **C.** We have to choose the smallest **C,** according to the problem statement. Hence, we choose the smallest positive **C** that we can in the field of 2^{32-k} and deduct 2^{31} from it to get the smallest within the 32-bit residue’s range.

Since **2 ^{31}** is divisible by

**2**(we know k ≥ 1) we are selecting a valid value of

^{32-k}**C.**

There are more **corner** cases to handle in the case of division. Such as **A = 0** or **B = 0**.

- For
**B = 0**, there is nothing we can do if**A**is**non-zero.**The answer is**undefined**in this case. - For
**A = 0**, even if**B**is**0**or not, the answer is simply**-2**^{31}.

## 32-bit exponentiation

The simplest way would be to implement it as described in the definition, using 32-bit division for negative **B**. But again doing something like

```
if B < 0
return 1 / fast_pow(A, -B)
```

will not work for **B = -2 ^{31}**. So you should be careful here.

We can use another method to not deal with this tricky case.

If **B** is **negative** and **A** is **even,** then we are asking to evaluate

1 / some-even-number

We already know this is **undefined.** So we can handle this as a **corner** case. In all other cases, the answer should be well defined.

It may be confusing what to do if B is negative. Well, we can use the Euler’s theorem

a^{totient(m)}= 1 (mod m) totient(2^{32}) = 2^{31}

Meaning, we can find the residue of **B,** mod **2 ^{31}** and find the answer by repeated squaring.

## Everything else

The other expressions are trivial.

There is much **detail** in applying the rules one by one in the **exact** order and rules as specified in the problem statement. Refer to the **Tester’s** solution for the details. The solution is well commented and hopefully the involved parts are easier to follow with the help of the editorial.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.