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 by calculating
. This will be used in many other tasks.
Then, we simply note that the answer is .
Task 2: MAX
Let . The main idea is that we will add
to
, creating
. However, if
, then we should clear
to
beforehand, such that our answer is
.
So, we simply calculate . This value will be nonzero if and only if
, so we can use this value in the
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 . If the result is
, we should negate our final answer. Thus, we can deal with only non-negative values of
and
.
We will store the result in a variable , initially equal to
. We will also create the number
, and a counter
, initially equal to
. Then, we will perform
steps.
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 . We can also create the numbers
. Then, we perform
steps, processing the powers of
in decreasing order.
In each step:
- Increment
by the power of
.
- If
is not positive, then increase
by the relevant multiple of
.
As a side note, if and
are both equal to
, we can't actually create any non-zero numbers (such as
). However, since we never create any non-zero numbers, we will still output the correct value of
. This holds true in many other tasks, and explains the condition in the
EQUALS
task where at least one of and
are non-zero.
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 ). We want to implement the modulo operation, but if the number we are modulo-ing by is
, we want to do nothing.
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 and
by
to get their corresponding bits, and then set the bit of answer if the corresponding bits are not equal. To check this, we can use our algorithm from the
EQUALS
task.
Task 6: PRIMES
Process each prime number under in increasing order. First, we will decrease
by the difference between the current prime and the previous prime, considering the prime preceding
as
. If
is non-negative, then we will add
to the answer.
In order to decrease by the difference efficiently, it suffices to precompute small integers. The largest prime gap under
is
, so we only need to precompute integers up to
.
Task 7: SORT
First, notice that we can sort two integers and
by replacing them with
and
. This allows us to reuse code from the
MAX
task.
Then, we can simply perform a bubble sort or selection sort using this trick. In order to fit under the statement limit, we need to be able to sort two numbers in at most
statements.
Comments