Editorial for BPC 1 S4 - Binary Matrices - DMOJ: Modern Online Judge

Editorial for BPC 1 S4 - Binary Matrices

Remember to use this editorial 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: BalintR

Hint 1

Try isolating the most significant bit that's different in $A$ ~A~ and $B$ ~B~.

Hint 2

Try making a register that's all $1$ ~1~s if $A$ ~A~ and $B$ ~B~ need to be swapped, and all $0$ ~0~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 $1$ ~1~ bits in the register in the specified direction. This function can be implemented either by looping $N$ ~N~ times and always shifting by one more, or by looping $\log N$ ~\log N~ times and always doubling the shift size.

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

To elaborate a bit on the above, we can use the following code to find the first row where $A$ ~A~ and $B$ ~B~ 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 $A$ ~A~ or $B$ ~B~ is bigger and set $C$ ~C~ to all $1$ ~1~s if $A$ ~A~ and $B$ ~B~ 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 $5$ ~5~ or $32$ ~32~ 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

There are no comments at the moment.