## Monday, September 8, 2014

### a bit of codeforces: Multiplication Table (Interesting Binary Search)

Problem Statement:
448 D - Multiplication Table

Summary:
Given a table of dimension M x N, where $$1 \leq M,N \leq 10^5$$, and with the property that cell $$i,j$$ contains $$i*j$$, find the $$k$$-th largest element in the table.

We can certainly generate all $$i*j$$ and store them inside a vector, and simply iterate through to the $$k$$-th element ($$O(N^2)$$), but that will take forever when $$M,N$$ are large. Furthermore, we actually can perform a very cool binary search to find the k-th element! Firstly, notice that if we are given a number $$S$$, we can find its rank in $$O(N)$$ time by simply checking on each row how many cells are less than or equal to $$S$$ (we will actually end up with the largest rank of $$S$$ if $$S$$ occurs several times on the table). After obtaining the rank, we can check whether it is less than or bigger than $$k$$, and we perform a corresponding binary search until we end up with the correct value of S. The approach is therefore $$O(N\lg{N})$$ which is fast enough for the time limit.