MULDIG - Editorial

PROBLEM LINK:

Practice
Contest

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

1 Like