Kill Backtrack: Amazon interview Question

Problem statement: Given a number N. You have to list the ways of obtaining N by using numbers from 1 to N – 1 any number of times.

Example: If N = 4,  I can only use numbers from 1 to 3 . (1 to N – 1)

My answer would be :  {1, 1, 1, 1} , {1, 1, 2}, {1, 3}, {2, 2}   , {3, 1}, {2, 1, 1}, {1, 2, 1} // assuming ordering matters. Here each of the series sums to 4. And I am using numbers from 1 to N – 1. Write an algorithm to generate these series.

Solution Approach:

The implementation for the same is given below:

public class SumN
{
    private static int n;
    private static int[] a;
    private static int[] visited;

    public static void solve(int index, int remSum)
    {
        if(remSum == 0)
        {
            for(int i = 0; i < index; i++)
            {
                System.out.print(a[i] + " ");
            }
            System.out.println();
        }
        else if(remSum > 0)
        {
            for(int i = 1; i <= n - 1; i++)
            {
                a[index] = i;
                solve(index + 1, remSum - i);
            }
        }
    }

    public static void main(String[] args)
    {
        n = 4;
        a = new int[n];
        visited = new int[n];
        solve(0, n);
    }
}

Kill Backtrack: N Queen Problem of Chess

Problem statement: You are given a N x N (N cross N) board. And N queens. You have to design an algorithm to place those N queens in N x N board, so that none of the queens are clashing.

Example: if the board is 1 x 1, then I can place the 1 queen at (0, 0) grid.

if board is 2 x 2, then I cannot place 2 queens. They will definitely clash, and no solution exists for this.

for board 3 x 3, also it’s not possible to get the gird arrangement of queens.

Assume the board size is greater than or equals to 4 x 4.

for 4 x 4, I can place four queens at    (0, 1) , (1, 3), (2, 0), (3, 2).

Given the size of the grid as N, return the possible arrangement.

Solution Approach:   This problem is also solvable by back-tracking :

1. Start in the topmost row.

2. If all queens are placed return true

3. Try all columns in the current row.

Do the following  for every tried column:

a). If the queen can be placed safely in this column then mark this[row, column] as part of the solution and recursively check if placing

queen here leads to a solution.

b). If placing queen in [row, column] leads to a solution then return true.

c). If placing queen doesn’t lead to a solution then unlock this [row, column] (backtrack) and go to step (a) to try for other columns.

4. If all the columns have been tried and nothing worked, return false to trigger backtracking.

You can play N-queen back tracking in:

http://www.hbmeyer.de/backtrack/achtdamen/eight.htm#up

The implementation in Java for the same is given below

public class NQueens
{
    private static int n;
    private static int[] columns;

    public static void placeQueen(int row)
    {
        if(row == n - 1) // we have taken all the n rows.
        {
            for(int i = 0; i < n; i++) System.out.print("( " + i + ", " + columns[i] + ") " );
            System.out.println();
        }
       else
       {
           if(isSafe(row))
           {
               for(int i = 0; i < n; i++)
               {
                   columns[row + 1] = i;
                   placeQueen(row + 1);
               }
           }
       }
    }

    public static boolean isSafe(int row)
    {
        int k = 0; boolean flag = true;
        while(k < row && flag)
        {
            if(columns[row] == columns[k] || Math.abs(columns[row] - columns[k]) == Math.abs(row - k))
                flag = false;
            k++;
        }
        return flag;
    }

    public static void main(String[] args)
    {
        n = 8;
        columns = new int[n];
        placeQueen(0);
    }
}

Worst case bound for this algorithm is worse than the order of exponential.

Kill Backtrack : Sum of Subsets Problem

Problem Statement: You are given an array of numbers and you have to return if we can attain a particular desiredSum by adding any elements or not. If there exists some series then print out that.

Solution Approach: This problem is one of the most popular backtracking questions. Let’s simulate the solution with the example given below:

int a[] = {1, 2, 3, 7, 4, 5, 6};

int desiredSum = 10;

Here, we can get 10 by adding up : 1, 2, 3, 4  or 1, 2, 7 or 1, 3, 6, or 1, 4, 5 or 2, 3, 5, etc.

1. Let’s first sort the given arrays. By sorting the elements I can make decision from current index whether I have to take the element in the (index + 1) in considerations or not.

Thus a becomes {1, 2, 3, 4, 5, 6, 7};

2. Let’s say our current sum is 0. i.e. so far we have not taken any elements in array in considerations.

int curSum = 0;

Then, the remaining sum which I can take up to maximum for considerations is the total sum of the elements of the given array.

int totalSum = totalSumOf(a) = 28

3. Now, let’s me assume that I have taken the index zero in considerations.

That means I have already used element at index zero. So I will set it visited. And check

if(curSum + a[index] == desiredSum) // taking this element at index I can attain the desired Sum and thus print the list(consider only those elements which I have visited)

4. If the above condition is not met, then we check if I can use current element(at index).

else if(curSum + a[index] + a[index + 1] <= desiredSum) // I have sufficient room to take in considerations that I should take this element. Later on, if this decision was wrong, I will backtrack. So no problem in going on with this.

5. I will have to make decision on not taking the element at index in considerations. I will ignore this element and see the consequences.

if(curSum + remSum – a[index] >= desiredSum && curSum + a[index + 1] <= desiredSum) // analyse why this condition is required.

visited[index] = 0; // not taking this element for while

import java.util.Arrays;
public class SumOfSubsets
{
    private static int[] a;
    private static int[] visited;
    private static int desiredSum;

    public static void sumOfSubsets(int index, int curSum, int remainSum)
    {
        visited[index] = 1;
        if(a[index] + curSum == desiredSum)
        {
            for(int i = 0; i <= index; i++)
            {
                if(visited[i] == 1)
                {
                    System.out.print(a[i] + " ");
                }
            }
            System.out.println();
        }
        else if(index + 1 < a.length && curSum + a[index] + a[index + 1] <= desiredSum)
        {
            sumOfSubsets(index + 1, curSum + a[index], remainSum - a[index]);
        }
        if(index + 1 < a.length && curSum + a[index + 1] <= desiredSum && curSum + remainSum - a[index] >= desiredSum)
        {
            visited[index] = 0;
            sumOfSubsets(index + 1, curSum, remainSum - a[index]);
        }
    }

    public static void main(String[] args)
    {
        a = new int[]{1, 2, 3, 7, 4, 5, 6};
        visited = new int[a.length];
        Arrays.sort(a);
        desiredSum = 10;
        int totalSum = 0;
        for(int item : a) totalSum += item;
        sumOfSubsets(0, 0, totalSum);
    }
}

Reverse a Stack Using recursion

Problem statement: You are given a stack, reverse it without using any other data structures(or without extra memory). You cannot use any memory at all. All what you have to do is use recursion only to attain this.

Problem Approach: This problem is one of the most popular interview questions because of the constraints that you cannot use any extra memory. All you have in memory is the given stack and use some recursion magic to attain the goal.

Suppose the stack is :

3

2

1

Then it should be

1

2

3

Stack operates on LIFO operation, so even if you use multiple recursion(which is in turn using stacks in OS level) wont bring you the direct solution. Let’s attempt the following approach:

1.pop the element from the stack.

2.Get the last element in the stack.

3. Remove that last element from the stack and assign it to temp. variable.

4. Start building the stack(by simply adding once the size of stack upon recursive call becomes 0).

The implementation of the same using Java is given below:

import java.util.Stack;
public class StackReversal
{

    public static void stackReversal(Stack<Integer> s)
    {
        if(s.size() == 0) return;
        int n = getLast(s);
        stackReversal(s);
        s.push(n);
    }

    public static int getLast(Stack<Integer> s)
    {
        int a = s.pop();
        if(s.size() == 0)
        {
            return a;
        }
        else
        {
            int k = getLast(s);
            s.push(a);
            return k;
        }
    }

    public static void main(String[] args)
    {
        Stack <Integer> stack = new Stack <Integer> ();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stackReversal(stack);
        while(stack.size() > 0)
        {
            System.out.println(stack.pop());
        }
    }
}

The above code runs with the time complexity of O(n ^ 2). And requires no any extra memory.

LinkedList Reversal Using Recursion

Problem Statement: Given the pointer to the head of LinkedList reverse it using recursion.

Problem Discusson: Let’s analyse how recursion works for the following example:

Given LinkedList :  1-> 2 -> 3 -> 4 -> NULL (in C, C++ it’s NULL, in Java it’s null)

Here, node1 is pointing to node2 , node2 to node3, node3 to node4 and node4 to NULL. Since each nodes are linked with pointer(address) of the node they are holding, we can attain 4 -> 3 -> 2 -> 1 -> NULL , by just pointing the next node to the current node.

i.e. Let’s say my pointer is currently pointing to node1, Let’s make node1 point to null, and move the pointer to node2, and node2 will point to node1 and finally node4 will point to node3.

Following code in C implements this technique.

node * reverse(node * ptr, node * prev)
{
    if(ptr -> next == NULL)
    {
        ptr -> next = prev;
        return ptr;
    }
    node * temp = reverse(ptr -> next, ptr); // now head becomes the prev.
    ptr -> next = prev;
    return temp;
}

Expectation : Random Sort Riddles.

Meaning:  In probability theory, the expected value (or expectation, or mean, or the first moment) of a random variable is the weighted average of all possible values that this random variable can take on.

Suppose random variable ‘X‘ can take value x1 with probability p1, value x2 with probability p2, and so on, up to value xk with probability pk. Then the expectation of this random variable ‘X’ is defined as:

E[X] = x1*p1 + x2*p2 + x3*p3 + ……………. + xk*pk;

Example : For the six faced dice with faces, 1, 2, 3, 4, 5, 6 : the expectation is: (assuming equal probability of getting all faces).

E[X] = 1* 1/6 + 2 * 1/6 + 3 * 1/6 + 4 * 1/6 + 5 * 1/6 + 6 * 1/6

E[X] = 3.5

Thus the expectation is 3.5.

Problem Section :   Random Sort Riddles using Expectation.

After having a bit of theory of expectation, we will now solve one very tricky riddles using expectation and Dynamic Programming.

Problem Statement:  Problem description can be found at:

http://community.topcoder.com/stat?c=problem_statement&pm=8590&rd=12174&rm=&cr=7452866

Don’t go for navie recursive code. It will for sure exceed the limit of 2second. So think of memoisation technique.

Here below is the implementation for the same using Dynamic Programming (recursion + memoisation approach):

Map <int[], Double> map = new TreeMap <int[], Double>(new Comparator<int[]>()
{
    public int compare(int[] p1, int[] p2)
    {
        for(int i = 0; i < p1.length; i++)
        {
            if(p1[i] != p2[i]) return p1[i] - p2[i];
        }
        return 0;
    }
});
public double solve(int[] p)
{
    double deno = 0, num = 0;
    int[] arr = new int[p.length];
    if(map.containsKey(p)) return map.get(p);
    for(int i = 0; i < p.length; i++)
    {
        for(int j = i + 1; j < p.length; j++)
        {
            if(p[i] > p[j])
            {
                arr = (int[])p.clone();
                int temp =p[i]; p[i] = p[j]; p[j] = temp;

                num += 1 + solve(p);
                deno++;
                temp =p[i]; p[i] = p[j]; p[j] = temp;
            }
        }
    }
    if(deno == 0) num = 0;
    else num /= deno;
    map.put(arr, num);
    return num;
}
public double getExpected(int[] p)
{
 return solve(p);
}

FieldDiagrams : count total number of FIELD diagrams.

Complete description about the problem can be found at:

http://community.topcoder.com/stat?c=problem_statement&pm=8776&rd=12173&rm=&cr=10574855

The most important aspect of this problem is how do u calculate those many possible field diagrams. One way is using recursion. But is that feasible. Here, I have come up with Dynamic Programming approach to solve this riddle.

Below is the implementation of this problem in Java.

private long[][] dp;
public long countDiagrams(int N)
{
    dp = new long[N + 1][N + 1];
    dp[0][0] = 1;
    for(int i = 1; i <= N; i++)
    {
        long sum = 0;
        for(int j = 0; j <= i; j++)
        {
            sum += dp[i - 1][j];
            dp[i][j] = sum;
        }
    }
    long res = 0;
    for(int i = 0; i <= N; i++) res += dp[N][i];
    return res - 1;
}

StrongPrimePower

Problem Statement: You are given number in the range up to 10 ^ 18. Can this number be expressed as P to the power q. ie. P ^q , where P is prime number and q is greater than 1.

Complete problem definition can be found in this site.

http://community.topcoder.com/stat?c=problem_statement&pm=8763

Constraints: This number can be up to 10 ^ 18. So rule out brute force approach. Even if you use improved mathematics, how will you keep track of overflow. This is the most important aspect of this problem.

Here below is the solution for this problem, but better first think yourself. And for overflow case(to handle for large numbers refer my code).

Method 1:

Using BigInteger Class of Java

public boolean isPrime(int n)
{
    if(n == 2) return true;
    if(n % 2 == 0) return false;
    for(int i = 3; i * i <= n; i += 2)
        if(n % i == 0) return false;
    return n > 1;
}
public int[] baseAndExponent(String n)
{

    int[] res = new int[0];
    long n1 = Long.parseLong(n);

    long sqrt = (long)Math.sqrt(n1 * 1.);
    if((long)(sqrt * sqrt) == n1 && isPrime((int)sqrt))
    {
        res = new int[2]; res[0] = (int)sqrt; res[1] = 2;
        return res;
    }

    long cbrt = (long)Math.cbrt(n1);
    if((long)(cbrt * cbrt * cbrt) == n1 && isPrime((int)cbrt))
    {
        res = new int[2]; res[0] = (int)cbrt; res[1] = 3;
        return res;
    }

    BigInteger init = new BigInteger(n);
    outer:
    for(int i = 2; i <= 100000; i++)
    {
        for(int pow = 4; pow <= 63; pow++)
        {
            BigInteger ans = BigInteger.valueOf(i).pow(pow);
            if(ans.compareTo(init) > 0) break;
            if(ans.equals(init) && BigInteger.valueOf(i).isProbablePrime(3))
            {
                res = new int[2];
                res[0] = i; res[1] = pow;
                break outer;
            }
        }
    }
    return res;
}

Method 2

Using Advanced Mathematics concepts(trick to prevent overflow)

The code below is written in C++.

typedef long long LL;
LL toLL(string s)
{
    stringstream ss;
    ss << s;
    LL n;
    ss >> n;
    return n;
}

bool isPrime(int n)
{
    if(n == 2) return true;
    if(n % 2 == 0) return false;
    for(int i = 3; i * i <= n; i += 2)
        if(n % i == 0) return false;
    return n > 1;
}

vector <int> baseAndExponent(string s)
{
    LL n = toLL(s);
    vector <int> v;
    for(int i = 2; i <= 64; i++)
    {
       LL base = (int)pow(n, 1. / i);
       base = max((LL)2, (LL)(base - 1));
       for(int a = base; a <= base + 2; a++)
       {
           LL N = n; int cnt = 0;
           while(N % a == 0)
           {
               N /= a;
               cnt++;
           }
          if(N == 1 && cnt == i && isPrime(a))
          {
              v.push_back(a);
              v.push_back(i);
              goto there;
          }
       }
    }
    there:
    return v;
}

Find Corporation Salary

The problem statement can be found at :

http://community.topcoder.com/stat?c=problem_statement&pm=9824&rd=12179&rm=&cr=19849563

It expects you to find the salary of an corporation but using the efficient Graph Theory Technique. Here below I am explaining how to solve to using DFS Graph concepts.

long[] dp;
String[] s;
public long solve(int source)
{
    if(dp > 0) return dp;
    for(int i = 0; i < s.length; i++) if(s.charAt(i) == 'Y') dp = dp + solve(i);
    if(dp == 0) dp = 1;
    return dp;
}
public long totalSalary(String[] s)
{
    dp = new long[100];
    this.s = s;
    long ans = 0;
    for(int i = 0; i < s.length; i++) ans += solve(i);
    return ans;
}

SRM 536

This SRM was scheduled for 5:30 pm IST. I was at office then. This time my approach was different. I first approached for DIV-II 250. I was able to successfully submit the code at 240 points. Then I opened 500 points problem. This time 500 points was relatively easy. I was able to submit at 431 points. This ascended me to within 70 ranks in DIV-II (after 25 minutes of SRM starting). I had sufficient time to approach for 1000 points. I opened it, problem was awesome. I thought it in DP + Maths way. After 25 minutes of opening 1000 points , I felt like I cannot do it.

System test results: Both 250 and 500 passed. I couldn’t solve 1000 pointer(i had no idea how to solve during contest). Finally I finished at 113th position in DIV-II among 1350 coders. This time again I ascended to DIV-I.

Let’s discuss the 1000 pointer problem (250 and 500 pointer were simply brute force) :

1000 pointer problem (DIV-II)

http://community.topcoder.com/stat?c=problem_statement&pm=11802&rd=14728&rm=311958&cr=22938770

You can refer the problem from here(p.s. due to copyright issue I am not publishing it’s contents)

 The Java implementation of the above problem is :

double[][] DP = new double[55][55];

public static int INF = Integer.MAX_VALUE;

public double findMaximum(int[] revenues, int k)
{
    Arrays.sort(revenues);
    double ans = -INF;

    for(int i = 0; i <= revenues.length; i++)
    {
        for(int j = 0; j <= revenues.length; j++)
        {
             DP[i][j] = ans;
        }
    }

    DP[0][0] = 0;

    for(int i = 1; i <= revenues.length; i++)
    {
        for(int j = 1; j <= revenues.length; j++)
        {
            int cnt = 0;
	    double sum = DP[i - 1][j - 1];
	    if(i - 1 != 0) cnt++;
	    for(int m = i; m <= revenues.length; m++)
	    {
		cnt++; sum += revenues[m - 1];
		if(cnt >= k) DP[m][j] = Math.max(DP[m][j], 1.*sum / cnt);
	    }
	}
    }
    for(int i = 1; i <= revenues.length; i++) ans = Math.max(DP[revenues.length][i], ans);
    return ans;
}

SRM 535

This SRM was scheduled for 10:35 pm IST. This timing was pretty much good for all the coders from India. This time I was in DIV-II. I had a feeling that I would ascend to DIV-I after this SRM. I decided to approach problems as Hard, Easy, Medium.

Hard problem was a bit tougher and complicated and I gave up after some minutes of reading and thinking. Then I opened easy problem, which I was able to solve for 242 points. Then again I went for Hard. Finally after 40 minutes I gave up and opened Medium problem. Here I am discussing about Medium problem statement of DIV-II.

http://community.topcoder.com/stat?c=problem_statement&pm=11364&rd=15037&rm=311842&cr=22859464

The question is above mentioned. I couldn’t solve this question in time as I opened this question in the last 30 minutes. The question was based on Mathematics.

Below is the code that I wrote after the contest.

public long GCD(long a, long b)
{
    if (a < 0) return GCD(-a, b);
    if (b < 0) return GCD(a, -b);
    return b == 0 ? a : GCD(b, a % b);
}
public long get(long G, long L)
{
    long ans = (long)1e18;
    if(L % G != 0) return -1;
    for(int d = 1; ; d++)
    {
        if(G * d > L / d) break;
        if(L % d != 0) continue;
        if(GCD(G * d , L / d) == G)
        {
            ans = Math.min(ans, G * d + L / d);
        }
    }
    return ans == (long)1e18 ? - 1 : ans;
}

Explanation and Mathematical Proof:

Let’s say the two numbers are a and b such that a <= b. The maximum value GCD can have is the minimum number between a  and b. Here a <= b. Therefore GCD always lie towards the left region of ‘a’ with some factor f. Similarly the minimum value LCM will have is the maximum number between a and b. Here b is greater than a. Therefore LCM lies towards the right region of ‘b’ with some factor.

Example : Let’s say gcd(a, b) = 3 and lcm(a, b) = 36.

Then a = 9, b = 12. i.e. GCD lies towards the left region of [a, b] and LCM lies towards the right region of [a, b]. And in each case it lies with some factor f. Thus we can deduce the concept that

a = someMultiple * gcd  and b = lcm / someMultiple. Thus keeping gcd * lcm constant. The same logic is induced in the code given above.

The above mentioned code runs at max. 10^6 times. Thus can be computed in the range of 2 seconds.

Overview: Bit Manipulation

Bit manipulation is used in different varieties of problem. Bit is one of the most effective and efficient low-level optimization technique.

Bit Operators:

The bit-manipulation approach lies around the use of bit-wise operators & (and), | (or), ~ (not) and ^ (xor).  The first three of them we are already familiar through their boolean form (&&, ||, !).  Have a quick re-cap of the following table :

The bit-wise versions of the operations are the same, except that instead of interpreting their arguments as true or false, they operate on each bit of the arguments. Thus, if A is 1010 and B is 1100,

• A & B = 1000
• A | B = 1110
• A ^ B = 0110
• ~A = 11110101 (the number of 1’s depends on the type of A).

Remember that   :

‘&‘  indicates  ‘AND‘ operation,

‘|‘ indicates  ‘OR‘ operation,

‘~‘ indicates ‘NOT‘ operation,

‘^‘ indicates ‘XOR‘ operation

The other two operators we will discuss are :  “<<” and “>>“. The former is Left Shift operator and the later is Right Shift operator.

=>  a << b  : This shifts all the bits in a to the left by b positions.

=>  a   >>  b  : This shifts all the bits in a to the right by b positions.

For simplicity you can think left shifting by b as multiplication with  2^b and right shifting by b as division with 2^b.

i.e.   a << b  = a * 2^b

         a >> b = a / 2^b

The most common use for shifting is to access a particular bit, for example, 1 << x is a binary number with bit x set and the others clear (bits are almost always counted from the right-most/least-significant bit, which is numbered 0).

In general, we will use an integer to represent a set on a domain of up to 32 values (or 64, using a 64-bit integer), with a 1 bit representing a member that is present and a 0 bit one that is absent. Then the following operations are quite straightforward, where ALL_BITS is a number with 1’s for all bits corresponding to the elements of the domain:

If in bit-s representation the number has i-th bit as 0 it is called unset bit and if i-th bit is 1 it is called set bit.

Some interesting bit-magics:

 

1) If you XOR a bit with its own negated value, you will always get 1. Therefore the solution to a ^ (~a)  will be the sequence of 1s.

consider a is of data-type byte.

example:

a = 00000001

~a  = 11111110

Now a ^ (~a) = 11111111

 

2) An operation like x & (~0 << n) clears the n rightmost bits of x. The value ~o is the sequences of 1s, so by shifting it by n, we have a bunch of ones followed by n zeros. By doing AND we clear the the rightmost n digits of x.

 

3) Bit Facts and Tricks:

x ^ 0’s = x                                       x & 0’s = 0                          x | 0’s = x

x ^ 1’s = ~x                                     x & 1’s = x                            x | 1’s = 1’s

x ^ x = 0                                         x & x = x                               x | x = x

 

4)  Get Bit :

If I want to get the bit at i-th position, this method shifts 1 over by i bits , creating a value and performing an AND operation with the number num. If the resultant value is zero, that bit is unset else, that bit is set.

boolean getBit(int num, int i) {
    return ((num & (1 << i)) != 0);
}

 

5) Set Bit:

If I want to set the bit at i-th position, this method shifts 1 over by i bits , creating a value and performing an OR operation with the number num.

public int setBit(int num, int i) {
    return num | (1 << i);
}

 

6) Clear Bit:

This method operates in reverse way as the setBit method works. To clear the i-th bit we first negate the result obtained from 1 << i and perform AND operation with the number num.

public int clearBit(int num, int i) {
    int mask = ~(1 << i);
    return num & mask;
}

7) Clear all the MSB through i (inclusive)

This method is meant for clearing all the MSB’s (Most Significant Bits) through i (inclusive) we do:

public int clearBitsMSBThrough(int num, int i) {
    int mask = ( 1 << (i + 1) ) - 1;
    return num & mask;
}

8) Clear all the bits from i through o(inclusive)

This method is meant for clearing all the bits from i through 0 from the number num:

public int clearBitsIthrough0(int num, int i) {
    int mask = ~(1 << (i + 1)) - 1;
    return num & mask;
}

Bit magic : Check if a number is power of 2

Problem Statement:  How do you check if a number of power of 2 or not. i.e. if the number is one among 1, 2, 4, 8, 16, … and so on.

Approach:  A number is power of two means it has only one set bit. Let’s say that number can be stored with ‘x’ bits. A number just less than n i.e. (n – 1) will have (x – 1) set bits and the x-th bit being unset.

For example :

n = 16 ;    1 0 0 0 0

Therefore, n – 1 = 15 ;    0 1 1 1 1

i.e. n & (n – 1)  is equals to zero(0).

Thus, the above property depicts that if n & (n – 1) == 0 , then ‘n‘ is the power of 2.

public boolean isPowerOfTwo(int n)
{
    return (n & (n - 1)) == 0;
}

SRM 534

This SRM was scheduled for 7:30 am IST. I woke up at 7:05 am IST, quickly registered for the match. As usual, being in DIV-I i thought of opening 250 points problem first.

Problem definition: 

http://community.topcoder.com/stat?=problem_statement&pm=11791&rd=14727&rm=311688&cr=22859464

My Approach:

I first saw the constraints, and felt that greedy approach won’t work( i thought of greedy approach just after reading the problem). I simulated the test cases to produce results, and felt that it requires bit-masking. I thought simple approach wont work, as the constraint could have been grown more for simple approach. I quit thinking in greedy approach. But verdict was, I was wrong. The optimal solution exists even with the greedy approach.

Using greedy approach:

Since every checkers can move until they reach the end of the board, the answer was simple. If the sum of difference between last index and checkers current position is odd, player A wins else player B wins. Pretty much simple approach.

public String getWinner(String board)
{
    int ans = 0;
    for(int i = 0; i < board.length(); i++)
    {
        if(board.charAt(i) == 'o') ans += board.length() - 1 - i;
    }
    if(ans % 2 > 0) return "YES";
    return "NO";
}

Using bit masking to generate all the possibilities:

private int N;
private int[] M = new int[1 << 20];
public int solve(int mask)
{
    if ((mask & 1) > 0)
        mask--;
    if (mask == 0)
        return 2;
    if (M[mask] != 0)
        return M[mask];
    boolean flag = false;
    int i, k;
    for (i = 1; i < N && !flag; i++)
    {
        if ((mask & (1 << i)) != 0)
        {
            if ((mask & (1 << (i - 1))) == 0)
            {
                k = (mask - (1 << i)) + (1 << (i - 1));
                if (solve(k) == 2)
                flag = true;
            }
            if (i > 2 && (mask&(1 << (i - 1))) != 0 && (mask&(1 << (i - 2))) != 0 && (mask & (1 << (i - 3))) == 0)   
            {
                k = (mask - (1 << i)) + (1 << (i - 3));
                if (solve(k) == 2)
                    flag = true;
            }
        }
    }
    if (flag)
        return M[mask] = 1;
    else
        return M[mask] = 2;
}
public String getWinner(String board)
{
    N = board.length();
    int i, j, k;
    k = 0;
    for (i = N - 1, j = 0; i >= 0; i--, j++)
    {
        if (board.charAt(i) == 'o')
            k = (k | (1 << j));
    }
   if (solve(k) == 1)
       return "YES";
   else
       return "NO";
}

Bit Practice Questions

The following two questions will clear your bits-concept to some extent.

http://community.topcoder.com/stat?c=problem_statement&pm=11791&rd=14727&rm=311688&cr=22859464

http://community.topcoder.com/stat?c=problem_statement&pm=10878&rd=14156

Due to copy-right issues, I cannot directly have the same questions here. You feel free to refer these questions through Topcoder’s site.

Dynamic Programming Meanings

In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure (described below). When applicable, the method takes far less time than naive methods. In the upcoming examples and text, Dynamic Programming is aliased as DP.

To be able to use DP, the original problem must have:

1. Optimal sub-structure property : Optimal solution to the problem contains within it optimal solutions to sub-problems
2. Overlapping sub-problems property : We accidentally recalculate the same problem twice or more.

There are 2 types of DP:

• We can either build up solutions of sub-problems from small to large (bottom up)
• We can save results of solutions of sub-problems in a table (top down + memoization)

 

Fibonacci Series

Let’s start with a sample of Dynamic Programming (DP) technique. We will examine the simplest form of overlapping sub-problems. Remember Fibonacci? A popular problem which creates a lot of redundancy if you use standard recursion fn = fn-1 + fn-2.

1. Simple Recursive Fibonacci Appraoch

public int fibonacci(int n)
{
    if(n == 0 || n == 1) return n;
    else return fibonacci(n - 1) + fibonacci(n - 2);
}

The above code runs in O(2 ^ n).

2. Using Dynamic Programming Approach

int[] dp = new int[100]; //assuming n will be less than 100.
public int fibonacci(int n)
{
    if(n == 0 || n == 1) return dp[n] = n;
    if(dp[n] > 0) return dp[n]; // instead of once again recursively calling method for 'n' which is already calculated. we memoise it and return there by.
    return dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
}

The above code runs considerably fast i.e. O(n). The above code memoises all the fibonacci values for all zero-th to N-th fibonacci  number.

3. Nth Fibonacci Number in order of log(n)

If we are interested in finding the Nth fibonacci number, it can calculated in order of log(n) using power-matrix. ({1, 1}, {1, 0} )

N-th fibonacci is nothing just:

The matrix representation gives the following closed expression for the Fibonacci numbers:

Where Fn is the n-th fibonacci number.

import java.util.Scanner;

public class Main {
    public int fibonacci(int n) {
        int[][] F = { { 1, 1 }, { 1, 0 } };
        if (n == 0 || n == 1)
            return n;
        power(F, n);
        return F[0][1];
    }

    public void multiply(int[][] F, int[][] M) {
        int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
        int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
        int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
        int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];

        F[0][0] = x;
        F[0][1] = y;
        F[1][0] = z;
        F[1][1] = w;
    }

    public void power(int[][] F, int n) {
        if(n == 0 || n == 1) return;
        int[][] M = { { 1, 1 }, { 1, 0 } };

        power(F, n / 2);
        multiply(F, F);

        if (n % 2 != 0)
        multiply(F, M);
    }
    public static void main(String[] args) {
        Scanner si = new Scanner(System.in);
        int b = si.nextInt();
        int n = new Main().fibonacci(b);
        System.out.println(n);
    }
}

The above approach uses divide and conquer approach to calculate n-th Fib. number in O(log(n)).

4.Binet’s Formula for the nth Fibonacci number in almost constant time

Can we find a formula for F(n) which involves only n and does not need any other (earlier) Fibonacci values?

Yes! It involves our golden section number Phi and its reciprocal phi: Here it is:

We can also write this in terms of square root of 5 since         Phi = 1·61803 39887 49894 84820 45868

34365 63811 77203 09179 80576 … . and  (phi = 1 / Phi). Note : small ‘p’ and capital ‘P’.

                             

The above given formula calculates n-th fibonacci in constant time.  Since golden section number never terminates after decimal, our calculating devices may not give exact result or for very large numbers they may given significantly contrasting results. So in real scenario, we prefer Power – Matrix one (in O(log(n)).            

  

Calculate nCr using DP

nCr is the number of selecting r items from n items.  Mathematically it is calculated as :

nCr = n! / (r! * (n – r) ! );

If the value of n or r grows significantly large, then computation of n! or r! may result in overflow and extra care has to be used for computation. But when we observe the pattern of nCr, it follows some realtions like:

nCr = n-1Cr + n-1Cr-1

We will compute the same pattern by recursively calling the method and terminating when r == 0 or r == 1 or n == r.

public long nCr(int n, int r)
{
    if(r == 0) return 1;
    if(r == 1) return (long)n;
    if(n == r) return 1;
    return nCr(n - 1, r) + nCr(n - 1, r - 1);
}

But this approach may not be efficient for large value of n. Here, instead of recursively calling method , we can memoise the result and if the subproblem already exists in memoised result, then return the result straight forward from there itself. Thus significantly reducing the time complexity.

Using DP it can be computed as:

long dp[][] = new long[100][100];
long nCr(int n, int r)
{
    if (r == 0)
        return dp[n][r] = 1;
    if (r == 1)
        return dp[n][r] = (long)n;
    if (n == r)
        return dp[n][r] = 1;
    if (dp[n][r] > 0)
        return dp[n][r];
    return dp[n][r] = nCr(n - 1, r) + nCr(n - 1, r - 1);
}

Longest Continuous Subsequences(LCS)

Let us discuss Longest Common Subsequence (LCS) problem as one more example problem that can be solved using Dynamic Programming.

LCS Problem Statement: Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n has 2^n different possible subsequences.

It is a classic computer science problem, the basis of diff (a file comparison program that outputs the differences between two files), and has applications in bioinformatics.

Examples:
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.
LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.

The naive solution for this problem is to generate all subsequences of both given sequences and find the longest matching subsequence. This solution is exponential in term of time complexity. Let us see how this problem possesses both important properties of a Dynamic Programming (DP) Problem.

1) Optimal Substructure:
Let the input sequences be X[0..m-1] and Y[0..n-1] of lengths m and n respectively. And let L(X[0..m-1], Y[0..n-1]) be the length of LCS of the two sequences X and Y. Following is the recursive definition of L(X[0..m-1], Y[0..n-1]).

If last characters of both sequences match (or X[m-1] == Y[n-1]) then
L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2])

If last characters of both sequences do not match (or X[m-1] != Y[n-1]) then
L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2])

Examples:
1) Consider the input strings “AGGTAB” and “GXTXAYB”. Last characters match for the strings. So length of LCS can be written as:
L(“AGGTAB”, “GXTXAYB”) = 1 + L(“AGGTA”, “GXTXAY”)

2) Consider the input strings “ABCDGH” and “AEDFHR. Last characters do not match for the strings. So length of LCS can be written as:
L(“ABCDGH”, “AEDFHR”) = MAX ( L(“ABCDG”, “AEDFHR”), L(“ABCDGH”, “AEDFH”) )

So the LCS problem has optimal substructure property as the main problem can be solved using solutions to subproblems.

2) Overlapping Subproblems:
Following is simple recursive implementation of the LCS problem. The implementation simply follows the recursive structure mentioned above.

static final int MAX = 505;
String X, Y;
int[][] L; int[][] D ; // L - LCS length & D - LCS direction
public int LCS()
{
    L = new int[MAX][MAX];
    D = new int[MAX][MAX];
    int m = X.length();
    int n = Y.length();

    for(int i = 1; i <= m; i++) L[i][0] = 0;
    for(int j = 0; j <= n; j++) L[0][j] = 0;

    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(X.charAt(i - 1) == Y.charAt(j - 1))
            {
                L[i][j] = L[i - 1][j - 1] + 1;
                D[i][j] = 1;
            }
            else if(L[i - 1][j] >= L[i][j - 1])
            {
                L[i][j] = L[i - 1][j];
                D[i][j] = 2;
            }
            else
            {
                L[i][j] = L[i][j - 1];
                D[i][j] = 3;
            }
        }
    }
    return L[m][n];
}
public void print(int i, int j)
{
 if (i == 0 || j == 0) return;

 if (D[i][j] == 1)
 {
    print(i - 1, j - 1);
    System.out.print(X.charAt(i - 1));
 }
 else if (D[i][j] == 2)
    print(i - 1, j);
 else
    print(i, j - 1);
}

Time Complexity of the above implementation is O(mn) which is much better than the worst case time complexity of Naive Recursive implementation.

Longest Increasing Subsequence

The longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, length of LIS for { 10, 22, 9, 33, 21, 50, 41, 60, 80 } is 6 and LIS is {10, 22, 33, 50, 60, 80}.

Optimal Substructure:
Let arr[0..n-1] be the input array and L(i) be the length of the LIS till index i such that arr[i] is part of LIS and arr[i] is the last element in LIS, then L(i) can be recursively written as.
LIS(i) = { 1 + Max ( LIS(j) ) } where j < i and arr[j] < arr[i] and if there is no such j then LIS(i) = 1.
So the LIS problem has optimal substructure property as the main problem can be solved using solutions to subproblems.

Overlapping Subproblems:
Following is simple recursive implementation of the LIS problem. The implementation simply follows the recursive structure mentioned above.

Input: Given a sequence
Output: The longest subsequence of the given sequence such that all values in this longest subsequence is strictly increasing.

public void LIS()
{
    int[] Height = {10, 22, 9, 33, 21, 50, 41, 60, 80};

    int[] Length = new int[Height.length];

    for(int i = 0; i < Length.length; i++) Length[i] = 1;

    int[] predecessor = new int[Height.length];

    for(int i = 0; i < predecessor.length; i++) predecessor[i] = -1;

    for(int i = 0; i < Height.length; i++)
    {
        for(int j = i + 1; j < Height.length; j++)
        {
            if( Height[j] > Height[i] && Length[i] + 1 > Length[j])
            {
                Length[j] = Length[i] + 1;
                predecessor[j] = i;
            }
        }
    }
    int index = -1; int max = -1;
    for(int i = 0; i < predecessor.length; i++)
    {
        if(predecessor[i] > max)
        {
            max = predecessor[i];
            index = i;
        }
    }
    if(max == -1) // elements are in descending order.
    {
        System.out.println("Number of elements in LIS is 1"); // all elements in desc.order.
        System.out.println(Height[0]);  // We can choose any one element in LIS.
        return;
    }

    int[] A = new int[max + 2]; int j = 0;
    for(int i = 0; i < A.length; i++) A[i] = Integer.MIN_VALUE;
    while(index != -1)
    {
        A[j++] = Height[index];
        index = predecessor[index];
    }
    for(int i = 0; i < A.length / 2; i++)
    {
        int temp = A[i];
        A[i] = A[A.length - 1 - i];
        A[A.length - 1 - i] = temp;
    }
    System.out.println("The elements in LIS are ");
    for(int i = 0; i < A.length; i++) if(A[i] != Integer.MIN_VALUE) System.out.print(A[i] + " ");
 }