Editorial for Yet Another Contest 5 P4 - Nils++
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Task 1: EQUALS
First, we can get a
Then, we simply note that the answer is
Task 2: MAX
Let
So, we simply calculate CLR
statement.
Note that variations of this trick allow us to affect the behaviour of the CLR
statement depending on whether a value is negative, positive, non-negative or non-positive. This will be used in many other tasks.
Task 3: PRODUCT
First, we will solve the subtask where
We can start by dealing with signs. Store the value of
We will store the result in a variable
In each step:
- Increment
by . - If
is not positive, then increase by .
Now, we will deal with the harder variant of the task. We can use a very similar procedure. First, using repeated doubling, we can create the numbers
In each step:
- Increment
by the power of . - If
is not positive, then increase by the relevant multiple of .
As a side note, if EQUALS
task where at least one of
Task 4: GCD
Basically, we want to implement the Euclidean algorithm. We don't know how many steps it will take, so we will just perform the maximum number of steps needed for any pair (which turns out to be
So, how do we do modulo? Well, modulo is basically just repeated subtraction whilst our current number is non-negative. We could do this naively, but we can borrow the same idea as for the harder variant of the PRODUCT
task; we simply subtract numbers which are powers of 2 multiplied by the number we are modulo-ing by, whilst the current value is non-negative.
Task 5: XOR
This task does not introduce any new ideas. We already know how to perform division and modulo from the GCD
task. So it suffices to repeatedly divide and modulo both EQUALS
task.
Task 6: PRIMES
Process each prime number under
In order to decrease
Task 7: SORT
First, notice that we can sort two integers MAX
task.
Then, we can simply perform a bubble sort or selection sort using this trick. In order to fit under the
Comments