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 * 231 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 232, then its 32-bit residue is 0.
We know that if n! is divisible by 232, then (n+k)! is also divisible by 232, for all positive k. So if we find the smallest n, for which n! is divisible by 232 then any (n+k)! will be equal to 0.
This is very interesting because 34! is the first value which is divisible by 232. 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 = -231. 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 a C such that B*C = A (in 32-bit residue) B*C + x*232 = A
Our best bet here is to see if we can find y and x in the equation
B*y + x*232 = 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*232 = 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 2k where B / 2k is odd. b*C + x*232-k = A/2k
Of course, now we can find a solution of
b*y + x*232-k = 1
by using the Extended Euclid’s Algorithm. The value of C will be
y * (A / 2k) modulo 232-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 232-k and deduct 231 from it to get the smallest within the 32-bit residue’s range.
Since 231 is divisible by 232-k (we know k ≥ 1) we are selecting a valid value of 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 -231.
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 = -231. 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
atotient(m) = 1 (mod m) totient(232) = 231
Meaning, we can find the residue of B, mod 231 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.
succesfully submitted 
Thanks