Task 1: EQUALS

First, we can get a ~1~ by calculating ~sgn(|X|+|Y|)~. This will be used in many other tasks.

Then, we simply note that the answer is ~1 - sgn(|X-Y|)~.

Task 2: MAX

Let ~A = Y-X~. The main idea is that we will add ~X~ to ~A~, creating ~X+(Y-X) = Y~. However, if ~X > Y~, then we should clear ~A~ to ~0~ beforehand, such that our answer is ~X+0 = X~.

So, we simply calculate ~(Y-X) - |Y-X|~. This value will be nonzero if and only if ~X > Y~, 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 ~|X|, |Y| \le 10^5~.

We can start by dealing with signs. Store the value of ~sgn(X) + sgn(Y)~. If the result is ~0~, we should negate our final answer. Thus, we can deal with only non-negative values of ~X~ and ~Y~.

We will store the result in a variable ~Z~, initially equal to ~0~. We will also create the number ~1~, and a counter ~C~, initially equal to ~0~. Then, we will perform ~10^5~ steps.

In each step:

1. Increment ~C~ by ~1~.
2. If ~C-Y~ is not positive, then increase ~Z~ by ~X~.

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 ~1, 2, 4, 8, 16, \dots~. We can also create the numbers ~X, 2X, 4X, 8X, \dots~. Then, we perform ~30~ steps, processing the powers of ~2~ in decreasing order.

In each step:

1. Increment ~C~ by the power of ~2~.
2. If ~C-Y~ is not positive, then increase ~Z~ by the relevant multiple of ~X~.

As a side note, if ~X~ and ~Y~ are both equal to ~0~, we can't actually create any non-zero numbers (such as ~1, 2, 4, 8, 16~). However, since we never create any non-zero numbers, we will still output the correct value of ~0~. This holds true in many other tasks, and explains the condition in the EQUALS task where at least one of ~X~ and ~Y~ 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 ~41~). We want to implement the modulo operation, but if the number we are modulo-ing by is ~0~, 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 ~X~ and ~Y~ by ~2~ 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 ~2 \times 10^6~ in increasing order. First, we will decrease ~X~ by the difference between the current prime and the previous prime, considering the prime preceding ~2~ as ~0~. If ~X~ is non-negative, then we will add ~1~ to the answer.

In order to decrease ~X~ by the difference efficiently, it suffices to precompute small integers. The largest prime gap under ~2 \times 10^6~ is ~132~, so we only need to precompute integers up to ~132~.

Task 7: SORT

First, notice that we can sort two integers ~A~ and ~B~ by replacing them with ~A+B-\max(A, B)~ and ~\max(A, B)~. 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 ~10^6~ statement limit, we need to be able to sort two numbers in at most ~12~ statements.