## Editorial for BPC 1 S4 - Binary Matrices

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Author:

## Hint 1

Try isolating the most significant bit that's different in and .

## Hint 2

Try making a register that's all s if and need to be swapped, and all s otherwise.

## Solution

First, we define a `RepeatShift`

function as we will see it will be useful several times later.
This function will take a direction and potentially a register as arguments, and will repeatedly use a shift operation on the register.
After every iteration, it will also OR the result with the initial register.
This effectively "extends" any bits in the register in the specified direction.
This function can be implemented either by looping times and always shifting by one more, or by looping times and always doubling the shift size.

To actually solve the problem, we will find the most significant bit where and differ, check whether or have a set bit there, extend that bit using RepeatShift operations so the entire register is either all s or all s, then swap and if the register is all s.

To elaborate a bit on the above, we can use the following code to find the first row where and differ, then AND with the result and use the same idea to find the first bit in that row where they differ.

```
XOR C A B
RepeatShift C LEFT
RepeatShift C RIGHT
RepeatShift C DOWN
DOWN D C 1
XOR C C D
```

Once we have determined whether or is bigger and set to all s if and need to be swapped and 0 otherwise, we can use the following operations to swap them while only using one extra register:

```
XOR D A B
AND D D C
XOR A A D
XOR B B D
```

## Final Remarks

The problem was adversarial in a few ways.
First the whole thing about having a `standard`

checker so that you can submit in *Text* is misleading.
Due to all known solutions having something equivalent to the `RepeatShift`

operation, submitting in *Text* is not very convenient as you would have to write or lines every time that operation is used.
Second, the `ADD`

operation is mostly useless for this problem, and exists to attempt to throw off contestants who used the `ADD`

operation for ioi21p6.

## Comments