PROBLEM LINK:
Editorialist: Soumik Sarkar
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Binary, Bitwise operations
PROBLEM:
A procedure to merge two numbers, each less than 30000, into one number is provided. Given a list of such merged numbers, find a way to recover the two original numbers from each merged number.
QUICK EXPLANATION:
Each pair of number is combined into one number m. Obtain the two original numbers from each new number as m & 0xffff and m >> 16.
EXPLANATION:
The procedure to merge two numbers is described as such
int encodeInteger(int x, int n){
n = n<<(1<<(1<<(1<<1)));
x = x | n;
return x;
}
We can simplify n = n<<(1<<(1<<(1<<1))) to n = n << 16. The next step is x = x | n. So, put together, the numbers x and n are merged to get the number x | (n << 16). In other words, the number x is kept in the lower 16 bits, and the number n is bit shifted left by 16 to occupy the next 16 bits. These are then bitwise OR-ed together.
For example:
Let x = 30000, which is 111010100110000 in binary
Let n = 12321, which is 11000000100001 in binary.
Shifting n left by 16 bits, we get 110000001000010000000000000000.
Bitwise OR-ing, 000000000000000111010100110000 OR 110000001000010000000000000000 ------------------------------ 110000001000010111010100110000
The OR-ed result turns out to be 807499056 in this case.
It is possible to obtain the original numbers in many ways.
Let m be the merged number. Then,
x = m & 0b1111111111111111, or
x = m & 0xffff, or
x = m & ((1 << 16) - 1)
All of these do the same thing, they use bitwise AND to keep only the lowest 16 bits of m, which we know is x. 110000001000010111010100110000 AND 000000000000001111111111111111 ------------------------------ 000000000000000111010100110000
To find n, the simplest way is
n = m >> 16.
Shifting m 16 bits to the right removes the lower 16 bits and only the value of n remains. 110000001000010111010100110000 ↓ SHIFT RIGHT BY 16 ↓ 000000000000000011000000100001
EDITORIALIST’S SOLUTION:
Editorialist’s solution can be found here.