Editorial for Yet Another Contest 5 P4 - Nils++
Submitting an official solution before solving the problem yourself is a bannable offence.
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
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
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
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.