Definitely MAGIC-

Problem: http://www.spoj.com/problems/AMR11A/

 

This problem really got me thinking, at first glance problem seems pretty do-able, but after two wrong submissions, I realized, my DP state is completely wrong! Finally when I solved it, it made my day.


If you haven’t tried, really do it. You’ll have fun.

Solution:

Ok, straight forward, the question doesn’t ask us to maximize Harry’s path value. We must make sure he is alive! ( 😛 ). The question is to assign minimum amount of strength at the beginning of the grid so that Harry can choose a path and collect the Sorcerer’s stone (while being alive, ok this seems redundant).
The regular dp-maximizing the path value doesn’t work. Let me give an example, suppose the grid is


0 -1
-2 0

So Harry starts with 1/0 strength (hypothetical), then either path he takes, his strength decreases (<=0) and he dies. So we must assign him a minimum strength of 2.


The dp state is surprisingly simple,
suppose we are at the cell (r-1,c-1) and we want to go to (r,c). For Harry to be alive, it is sufficient for him to end up at (r,c) with resultant strength ‘1’. So we choose the path that maximizes Harry’s strength (alternately if negative values, we choose the one which decreases his strength least).

Suppose that the cell values are in s[1…..r][1….c]

initialization:

last row:
 for( int i=c-1; i>0; –i)
 {
  s[r][i] = s[r][i+1] – s[r][i];
  if(s[r][i]0; –i)
 {
  s[i][c] = s[i+1][c] – s[i][c];
  if(s[i][c]<1)
  {
   s[i][c] = 1;
  }
 }

for other rows and columns:
 for( int i=r-1; i>0; –i )
 {
  for( int j=c-1; j>0; –j )
  {
   if(s[i+1][j]>s[i][j+1])
    s[i][j] = s[i][j+1] – s[i][j];
   else
    s[i][j] = s[i+1][j] – s[i][j];

   if(s[i][j]<1)
    s[i][j] = 1;
  }
 }

🙂 Happy New Year

Let’s rob a store, shall we?

Suppose we decide to rob a store for whatever reasons (let it be “for fun” :P). Before making a fool out of ourselves during the robbery, we have a make a plan A, a plan B if ‘A’ fails, a plan C if ‘B’ fails… and so on.

 

The great Le Marc (apparently he is an awesome thief in Ocean’s Twelve movie) wants to help us out and makes all the entry and exit strategies. But leaves the work of actually stealing the items to us.
Of course we are greedy and want to get as much value items as possible. But there is a limit on the weight a person can carry (C’mon we are only human). Moreover we are Computer Science Engineers and we love everything to be optimal. 🙂

The 0-1 Knapsack problem

There are different items in the store, each item is valued differently and has a different weight. Now our job is to rob the place in such a manner that we get the highest loot. What items should we take? The most valued item may in fact weigh a lot. And Le Marc has imposed another condition on us, we have a rob an item as a whole, we cannot break it.

Solution

A greedy approach does not solve our problem (Why? take an example and try it out).
In the 0-1 knapsack problem, we have to decide whether to include an item (in the knapsack) or not. The original problem consists of subproblems- one that includes an item with the solution and another which does not include the particular item. This forms many overlapping sub-problems and can be solved using dynamic programming.

Recursion and memoization

Let w[] denote the weights of the items and v[] denote the values of those items. Suppose that we have a knapsack that can carry only upto ‘wt’ weight and ‘n’ is the number of items.

then, the recursive solution can be written as

int knapsack( int w[], int v[], int wt, int n )
{
 if(wt==0 || n==0)
  return 0;

 if( w[n-1]>wt )
  return knapsack(w, v, wt, n-1);
 else
 {
  return max(v[n-1]+knapsack(w,v,wt-w[n-1],n-1), knapsack(w,v,wt,n-1));
 }
}

This can be easily be improved by using memoization. Initialize a 2d array knapsack[n+1][wt+1] with ‘0’. knapsack[i][j] represents the maximum value that can be obtained from the first ‘i’ items and maximum weight=j.

for( i=0; i<=n; i++ )
{
 for( j=0; j<=wt; j++ )
 {
  if( i==0 || j==0 )
  {
   knapsack[i][j]= 0;
  }
  else if( w[i-1]<=j )
  {
   knapsack[i][j] = max( v[i-1]+knapsack[i-1][j-w[i-1]], knapsack[i-1][j] );
  }
  else
  {
   knapsack[i][j] = knapsack[i-1][j];
  }
 }
}

Spoj: Permutations – Memoization

Problem : Spoj ( www.spoj.com/problems/PERMUT1/ )
 
In this problem we need to calculate the number of inversions. ‘a’ contains numbers from 1 to n in a specific order. An ‘inversion’ here is defined as a(i) > a(j) && i<=j in one permutation. So the problem reduces to finding those sequences over all permutations such that they have exactly ‘k’ permutations. This can be done by brute force- listing out all permutations of numbers (from 1 to n) and counting those sequences which have exactly k inversions. Since listing all the permutations takes O(n!), this method would be pointless even for large values of n.
 
We can try a recursive approach for this problem. Note that if n=0, number of permutations is 0, and if k = 0 number of permutations = 1.

we can define the recursion as
permut(n)=
{ 0 if n==0; 
1 if k==0; 
sum(permut(n-1, k-i)) (for 0<=i=0) otherwise  
} 

This recursion can be coupled with memoization to take care of redundant solving of subproblems. ( NOTE: if there are many queries, it is better to follow a bottom-up approach rather than memoization. In this particular problem there are less than 10 queries ). Initialize a 2d array dp[n][k] with -1. 

permut(int n, int k)
{
 if( n==0 )
  return 0;
 if( k==0 )
  return 1;
 if( dp[n][k]!=-1 )
  return dp[n][k];
 
 int sum = 0;
 for( int i=0; i=0; i++ )
 {
   sum += permut(n-1, k-i);
 }
 return ( dp[n][k]=sum );
}


Happy memoization!

Spoj : Treat for the Cows – DP, Memoization

Problem: Spoj ( http://www.spoj.com/problems/TRT/ )

On first look, we may be urged to use a greedy approach, i.e., always take the lesser value ‘treat’ among the two end ‘treats’. Well, the greedy approach is wrong. Figure it out! 🙂

( Hint: Check for the testcase -> 11, 2, 11, 10 )

How to go about this problem?

Using recursion – Every time we have an array( size: n ) of treats, the maximum values that we can obtain is,


max( arr[mini]*day + treat( mini+1, maxi ), arr[maxi]*day + treat( mini, maxi-1 ) )


‘day’ is the current day, treat is the function that calculates the max value obtainable recursively ( initially we call the function, treat( 0, n )). mini and maxi values represent that arr[mini – maxi] are the treats that are available. Also note that, we don’t need to worry about passing the current day value each time. We can calculate it as,


current day =  n - maxi +mini


Clearly, we can observe that we are making a lot of redundant computations. The time complexity of this recursive approach is O(2^n).

The original problem consists of many overlapping sub problems. Suppose we calculate a particular problem once and store it in memory, we can use it in the future computations if required. create an n X n matrix and initialize all values with -1. when calling the recursive function, check if that particular value has already been updated, if it is not -1, return  that value, otherwise calculate that value.


int func( int top, int bottom )
{
if( top> bottom )
{
return 0;
}

if( cache[top][bottom]!=-1 )
{
return cache[top][bottom];
}

int day = n + top - bottom;

return cache[top][bottom] = max(func(top+1,bottom)+day*arr[top], func(top,bottom-1)+day*arr[bottom]);
}


 

Happy coding !

 

 

A DP problem explained

Problem: Philosopher’s Stone – Spoj (http://www.spoj.com/problems/BYTESM2/)

Approach 1:

This problem can be solved by a decision tree. Every possibility is taken into consideration and the path with maximum sum is taken. Since the number of test cases is very large, this might not be a feasible solution, but still makes a very good exercise.

 

Approach 2:

This problem is a simple application of Dynamic Programming. We are asked to find the maximum number of stones that Harry can pick up.

The idea:

Suppose that we need to find the number of stones to be picked up in the current position (i,j), i.e., we have already computed number of stones picked up so far (up to row i-1).

The current position is (i,j). When we were in the previous row (i-1), the column elements that could access the current column (j) are j-1, j and j+1.

Let us call the given array of numbers as A. Create another array B where we store the cumulative sum of stones collected for every row. Initially, fill the first row of array B with the elements of first row of array A. After that, loop over array B to find all the entries. For a given position (i,j), B(i,j) is the sum of A(i,j) and the maximum of B(i-1,j-1), B(i-1,j) and B(i-1,j+1).

for j=0 to (No_of_columns)

B[0][j]=A[0][j]

for i=1 to (No_of_rows)

for j=0 to (No_of_columns)

B[i][j]= A[i][j] + max( B[i-1][j-1], B[i-1][j], B[i-1][j+1] )

Maximum= B[0][0]

No_of_rows = t

for i=1 to (No_of_columns)

if ( maximum > B[t-1][i] )

maximum= B[t-1][i]

t is the number of rows. Since array index starts from 0, (t-1) refers to the last row. ‘Maximum’ is the max number of stones picked up.

Since it is the cumulative sum, the maximum number of stones picked up is biggest element in the last row of array B.