KOL16H - Editorial

PROBLEM LINK:

Practice
Contest

Editorialist: Soumik Sarkar

DIFFICULTY:

EASY

PREREQUISITES:

Binary, Gray code

PROBLEM:

Given a number of binary inputs switches n, determine the number of switch flips required to go through all 2^n input configurations.

EXPLANATION:

It is always possible to enumerate all 2^n input configurations with just 1 flip between two consecutive configurations. Such a sequence is called unit distance code for obvious reasons, otherwise known as the Gray code. Hence by following the Gray code, it is possible to go through all configurations with 2^n-1 moves, and clearly it is impossible to do better than that.

However n can be at most 10^{20}, so calculating 2^n-1 is not a good idea. The way out lies in the fact that the problem asks for the answer modulo 2^{33}. We need to use two observations about binary numbers:

  1. In binary, x modulo 2^b is simply the lowest b bits of x.
  2. In binary, 2^b-1 contains only the bit 1 repeated b times.

So, if n > 33, the answer will be 1 repeated >33 times in binary. And that number modulo 2^{33} will be just the lowest 33 bits, which are all 1! This is nothing but the number 2^{33}-1.
Concluding, if n < 33 the answer is 2^n-1, and otherwise the answer is 2^{33}-1.

Complexity is \mathcal{O}(1).
PS: The time limit is set to 2 sec, perhaps to confuse people? :stuck_out_tongue:

EDITORIALIST’S SOLUTIONS:

Editorialist’s solution can be found here.