PROBLEM LINK:
Author: Kamil Debowski
Primary Tester: Misha Chorniy
Editorialist: Hussain Kara Fallah
DIFFICULTY:
Medium-Hard
PREREQUISITES:
None
PROBLEM:
Problem is very long to describe here, kindly check contest/practice links.
Explanation
In this editorial I will describe the amazing library Kamil was able to build using a very simple function. Having this library coded would make solving the problem a matter of implementation and calling functions, because it allows various solutions to be applicable.
Our function is:
f(a , b) = (a + b)\%mod \ \ ;\ a \neq 0
f(a , b) = (mod-b)\%mod \ \ ;\ a = 0
Copy Function: Copies a value val to a cell in our array tar
f(val , 0 , tar)
Substraction function: Sub(a,b) :: a = (a-b)%mod
It’s equivalent to performing f(a,mod-1) exactly b times
Addition function: Add(a,b) :: a = (a+b)%mod
It’s equivalent to f(sub(a,b),f(b,b))
That’s because our function f doesn’t perform addition when a=0
Let’s define:
fhalf= \lfloor{\frac{mod}{2}} \rfloor
chalf=\lceil {\frac{mod}{2}} \rceil
Decrement function: Dec(a) :: a = max(a - 1 , 0)
It’s equivalent to Add( f(a,fhalf) , fhalf)
That’s correct because f(0,fhalf) = chalf
Sign Function returns 1 if the number is greater than zero, or zero otherwise
It’s equivalent to:
Sub( f(a,chalf) , sub(a,chalf) )
Case a = 0:
f(a,chalf) = fhalf , sub(a,chalf) = fhalf , that means sign(0) = 0
Case a > 0:
f(a,chalf) = a-fhalf , sub(a,chalf) = a - chalf
sign(a) = a - fhalf - a + chalf = 1
NOT Function :: Not(a) = (opposite of the sign)
sub(1,sign(a))
And Function :: And(a,b) returns 1 if both numbers are greater than 0
dec(add(sign(a),sign(b)))
OR Function :: OR(a,b) returns 1 if at least one number is greater than 0
Not(And(Not(a),Not(b)))
You can implement operators < , > using loops. decrementing both numbers by 1 and returning the corresponding boolean value according to the sign at the time one of them is equal to 0.
Now we can implement a program that multiplies two numbers in the same way we do it by our bare hands. We may copy the first digit of the second number along with the first number and multiply our digit with the first number using some extra cells of our memory. After that we may add the result to our answer cells. The same applies to the second digit. Of course we must perform multiplication by repeated addition.
Repeated addition can be easily done by running a loop that terminates when our second multiplied number reaches zero, adding the first number to the answer by each iteration.
Using these functions we are able to perform any arithmetic operation and of course binary operators. Also we can easily make our simulator run into loops and stop it whenever we would like to. Coding this library would make us able to solve the way we would like to.
You can check Kamil’s solution if we would like to
AUTHOR’s solution: Can be found here