ZENCALC - Editorial

ad-hoc
editorial
march13
medium
modulo

#1

PROBLEM LINKS

Practice
Contest

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 :wink: )

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.


#2

@anton_lunyov here in factorial i could not understand the part for -231 can you make it more clear


#3

I m not getting what is exactly 32 bit residue!!Can u make it more clear…


#4

Just try to input number -2^31 = -2147483648 from stdin and output its abs() or negation to stdout:

int x;
cin >> x;
cout << abs(x) << endl;
cout << -x << endl;

And you will see how evil it is.


#5

I think the way this works is :
x = -2^31 -> abs(x) = 2^31. But c++ automatically handles overflow (since int is from -2^31…2^31-1) the result is -2^31


#6

Great Editorial! Not easy for some one to understand from this but the way you guys presented is nice. Best you could do to explain those cases!


#7

got it :slight_smile: succesfully submitted :stuck_out_tongue: Thanks @anton_lunyov and @tungnk1993


#8

omg i’m so sad i missed the trick with power and B=-2**31… /cry


#9

Equivalent definition of 32-bit residue of X is
(X + 2^31) mod 2^32 - 2^31,
where A mod B is the remainder of division of A by B. For example:
2 mod 3 = 2
9 mod 4 = 1
12 mod 2 = 0
5 mod 5 = 0
0 mod 1 = 0
-3 mod 2 = 1
-4 mod 4 = 0


#10

Ohk Got it …Thanx!!


#11

moreover, although it’s not really necessary here, 2^32 is a great number for modulo operations on a computer, because it can simply be expressed as the bitwise operation &0xFFFFFFFF. :slight_smile: