Solution to "Splendid Matrices"

View Problem: Splendid Matrices

For any Splendid Matrix of order N, we can divide it into 4 equal parts:

• The top left part A[1..2^N-1][1..2^N-1] contains numbers in the interval [1..4^N-1]. 
• The top right part A[1..2^N-1][2^N-1+1.. 2^N] contains numbers in the interval
  4^N-1 (offset) + [1..4^N-1]. 
• The bottom left part A[2^N-1+1..2^N][1..2^N] contains numbers in the interval
  2*4^N-1 (offset) + [1..4^N-1]. 
• The bottom right part A[2^N-1+1..2^N][2^N-1+1..2^N] contains numbers in the interval
  3*4^N-1 (offset) + [1..4^N-1]. 

All 4 parts follow a similar pattern of arrangement of the numbers, except for the offsets.

We try to fill the matrix recursively. Assuming we know the value of the top-left corner element in our matrix (say v), the top left corner row and column pair being (r, c), we can write the following recursive algorithm to fill the matrix (let the matrix be A[1..2^N][1..2^N]) :

fill_matrix (v, r, c, N)
{
    if(N == 0)
    {
        A[r][c] = v;
    }
    else
    {
        fill_matrix (v, r, c, N-1);
        fill_matrix (v+4^(N-1), r, c+2^(N-1), N-1);
        fill_matrix (v+2*4^(N-1), r+2^(N-1), c, N-1);
        fill_matrix (v+3*4^(N-1), r+2^(N-1), c+2^(N-1), N-1);
    }
}

fill_matrix(1, 1, 1, N) generates our Splendid Matrix of order N.

Searching for an element K in the matrix can also be performed in a similar recursive fashion. We divide the matrix into 4 equal parts. Since each part represents an interval of numbers, we need to search only in one of them, which can be selected based on the intervals these parts represent. In every step of the recursion, we maintain the top-left corner element v of our current matrix. The below function assumes that the input will be a legal one, i.e. K lies in [1..4^N].

search (K, r, c, v, N)
{
    if(N == 0) // this also means that v = K.
    {
        return (r, c);
    }
    else
    {
        if(v <= K && K < v+4^(N-1))
        {
            return search (K, r, c, v, N-1);
        }
        else if(v+4^(N-1) <= K && K < v+2*4^(N-1))
        {
            return search (K, r, c+2^(N-1), v+4^(N-1), N-1);
        }
        else if(v+2*4^(N-1) <= K && K < v+3*4^(N-1))
        {
            return search (K, r+2^(N-1), c, v+2*4^(N-1), N-1);
        }
        else if(v+3*4^(N-1) <= K && K < v+4^N)
        {
            return search (K, r+2^(N-1), c+2^(N-1), v+3*4^(N-1), N-1);
        }
    }
}

search(K, 1, 1, 1, N) gives us the correct answer.

In Binary Search, we divide the array into 2 equal parts and search in one of them. Since in this case we are dividing the matrix into 4 equal parts and searching in one of them, we can call it Quaternary Search.

To find the value at a particular (R, C), we again perform a similar recursion as the one above. Only difference will be that we will find out in which of the 4 parts (R, C) lies, and depending on that, we add a certain amount to our answer. When we finally reach (R, C), we have added an appropriate amount and hence we obtain the value at (R, C).

val (R, C, i, j, v, N)
{
    if(N == 0) // this also means i = R and j = C
    {
        return v;
    }
    else
    {
        if(R <= i+2^(N-1) && C <= j+2^(N-1))
        {
            return val (R, C, i, j, v, N-1);
        }
        else if(R <= i+2^(N-1) && C > j+2^(N-1))
        {
            return val (R, C, i, j+2^(N-1), v+4^(N-1), N-1);
        }
        else if(R > i+2^(N-1) && C <= j+2^(N-1))
        {
            return val (R, C, i+2^(N-1), j, v+2*4^(N-1), N-1);
        }
        else if(R > i+2^(N-1) && C > j+2^(N-1))
        {
            return val (R, C, i+2^(N-1), j+2^(N-1), v+3*4^(N-1), N-1)
        }
    }
}

val(R, C, 1, 1, 1, N) gives us the correct answer.