Solution to "House of Cards"

View Problem: House of Cards

Let us assume that instead of spending the night in the last house he visits, Underwood returns to his house the same day. Clearly, in such a case, the distance he travels will be 2 x (Number of Edges in the Tree) = 2(N-1). Now, if he does stay back in the last house he visits, it will be best if the distance between his own house and this last house (say D) is as large as possible. This is because the distance traveled by him in this case will be 2(N-1) - D. Hence, the minimum distance traveled by Underwood will be 2(N-1) - (Length of the longest path between the root to a leaf).

House of Cards

Frank Underwood is running for the post of "President of the United States of America". He is now in his home state South Carolina for campaigning. Today, he is visiting the city he grew up in, Gaffney.

Houses in Gaffney are arranged in the form of a tree with N nodes. Houses are denoted by the nodes, and roads (each of length 1 unit) are denoted by the edges of the tree. At present, Frank is at his house, which also happens to be the root of the tree. He plans on visiting each and every house in the city. It will be very late by the time Frank finishes visiting all the houses and he will have to spend the night in the last house he visits.

Given the map of Gaffney, can you state the minimum distance he has to travel today to visit each and every house in the city? Let us look at an example:

If Frank travels as shown in Fig 1, the distance traveled by him will be 3 + 3 + 2 = 8 units. However, if he travels as shown in Fig 2, the distance traveled by him will be 2 + 2 + 3 = 7 units. Clearly, Fig 2 depicts a better way of visiting the houses.

View Solution: Solution to "House of Cards"

Solution to "Squary Numbers"

View Problem: Squary Numbers

We will solve this problem by using a Dynamic Programming (DP) approach. Let us assume the number N is given to us in a string format s[1..L] where L is the number of digits in N. s[i..j] denotes the sub-string starting at index i (inclusive) and ending at index j (again inclusive).

s[i..j] is Squary if and only if for at least one k in [i..j-1], both s[i..k] and s[k+1..j] are Squary. This is our sub-problem for the Dynamic Programming approach:

dp[1..L][1..L] = 0;

for(i=1; i<=L; i++)
{
    for(j=i; j<=L; j++)
    {
        if(isPerfectSquare(s[i..j]))
        {
            dp[i][j] = 1;
        }
    }
}

for(l=1; l<=L; l++)
{
    for(i=1; i<=L-l+1; i++)
    {
        j = i+l-1;

        for(k=i; k<=j-1; k++)
        {
            if(dp[i][k] == 1 && dp[k+1][j] == 1)
            {
                dp[i][j] = 1;
            }
        }
    }
}

dp[i][j] = 1 only if s[i..j] is Squary, otherwise dp[i][j]=0. So, if dp[1][L] = 1, then N is Squary, otherwise it isn't.

To find a valid partitioning for a Squary number, we use the following simple recursive algorithm:

partitions(i, j, s, dp)
{
    if(isPerfectSquare(s[i..j]))
    {
       return(pair(i,j)); 
    }
    else
    {
        for(k=i; k<=j-1; k++)
        {
            if(dp[i][k] == 1 && dp[k+1][j] == 1)
            {
                return(partitions(i, k, s, dp) + partitions(k+1, j, s, dp));
            }
        }
    }
}

Calling partitions(1, L, s, dp) will return a set of pairs of indices denoting the starting and ending indices of all the partitions.

Solution to "Multiplying Nines"

View Problem: Multiplying Nines

The trick lies in writing a number with K 9's (i.e. 999...9 occurring K times) as 10^K-1. So, the numbers A and B can be written as A = 10^N-1 and B = 10^M-1.

A x B = (10^N-1) x (10^M-1) = 10^N+M - 10^N - 10^M + 1

Without loss of generality, let N >= M. Let us now try to compute the above result:

   10000...0000     // N+M 0's
-     1000..000     // N 0's
-       100..00     // M 0's
+             1
-------------------------------------------------------------
[(M-1) 9's]  [1 8]  [(N-M-1) 9's]  [1 9]  [(M-1) 0's]  [1 1]
-------------------------------------------------------------

The answer can obtained by making simple observations while performing the subtractions and addition as shown above.

Solution to "Divided Tree Processing"

View Problem: Divided Tree Processing

Initially, let us assume that the task can be completed in 0 time. This would mean that each parent assigns sub-tasks to its children at the same time which is T = 0. We will now delay the sub-task distribution only where it will be required, thus minimizing the time to complete the task.

Let time_received[i] denote the time at which node i received its task. Let time_completed[i] denote the time at which node i completed its task. If node i has children, let child[i][0] and child[i][1] denote the indices of its children.

Let us say that both the children complete their tasks at the same time. This case has to be avoided, so we simply delay the giving away of sub-task for one of the children by 1 time unit. This will work due to our initial assumption that all parents distribute the sub-tasks to their children at the same time. We then apply this condition recursively (assume initially for all i, time_received[i] = time_completed[i] = 0):

calculate(i)
{
    if(!hasChildren(i))
    {
        time_received[i] = 0;
        time_completed[i] = 0;
    }
    else
    {
        calculate(child[i][0]);
        calculate(child[i][1]);

        if(time_completed[child[i][0]] == time_completed[child[i][1]])
        {
            /*
             Increment by 1 the time_received[i] and time_completed[i] for all i 
             such that node i belongs to the sub-tree rooted at node child[i][1].
            */

            time_completed[i] = time_completed[child[i][0]] + 1;
        }
        else
        {
            time_completed[i] = max(time_completed[child[i][0]], time_completed[child[i][1]]); 
        }
    }
}

calculate(1) fills time_received[i] and time_completed[i] for all i. time_completed[1] gives us the minimum time taken by the system to complete the entire task.

The above algorithm can be optimized. Instead of incrementing the values of time_completed[i] and time_received[i] for all i which belong to the sub-tree rooted at node child[i][1], we can store separately for which sub-tree the increment has to be performed. In the end, these stored values can be added in a cumulative fashion by following a top-down approach.

Solution to "Sum of Digits"

View Problem: Sum of Digits

The value of the number abc is equal to 100*a + 10*b + c. Similarly, the value of def is equal to 100*d + 10*e + f. Adding these two gives us 100*(a+d) + 10*(b+e) + (c+f), which is the value of ghij. Let us try to represent g, h, i and j in terms of a, b, c, d, e and f:

Case 1: (a+d) < 10, (b+e) < 10, (c+f) < 10

For this case,

• g = 0
• h = a+d
• i = b+e
• j = c+f

So, g + h + i + j = a + b + c + d + e + f. Hence (a + b + c + d + e + f) % 9 = (g + h + i + j)%9

Case 2: (a+d) >= 10, (b+e) < 10, (c+f) < 10

For this case,

• g = 1
• h = (a+d)%10
• i = b+e
• j = c+f

If we prove that (a + b + c + d + e + f - (g + h + i + j)) % 9 = 0, we are done.

  (a + b + c + d + e + f - (g + h + i + j)) % 9 
= (a + b + c + d + e + f - (1 + (a+d)%10 + b+e + c+f)) % 9
= (a + d - 1 - (a+d)%10) % 9
= (10-1) % 9 //(a+d)-(a+d)%10 = 10 as a, d lie in [0..9] so (a+d) lies in [0..18]
= 9 % 9
= 0

Hence proved for this case.

Similarly, the proof can be continued for all cases, and generalized as well.

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.