2

Problem Statement -

Problem Statement

Given a 2xN grid of numbers, the task is to find the most profitable tiling combination (each tile covers 2x1 cells; vertically or horizontally) covering all tiles.

I thought of approaching it in the greedy way, enqueuing the max possible for any cell, but it has a fallback that a low-profit choice at i, could yield a greater profit at i+n tiles.

So what should be the approach?

EDIT - Test Data Range - N<=105

Source - INOI 2008 Q Paper

UPDATE - Working out the plausibility of a Dynamic programming Approach.

UPDATE 2 - Worked out an answer using DP.

  • @Dennis Test Data Range is N<=10^5. Brute-force, would be the last-resort. Still, I'd be interested in knowing a better approach... – 7Aces Dec 24 '12 at 11:11
  • Deleted my previous comment, are you interested in finding the best solution only, or in finding a good solution in a reasonable time (thus resort to heuristics)? – Dennis Jaheruddin Dec 24 '12 at 11:15
  • @Dennis The Q demands the best solution in the least time. – 7Aces Dec 24 '12 at 11:20
2

Worked out a Dynamic Programming Approach to the problem -

int t[n][2]; //Stores grid values
int b[n]; //Stores best solution upto a particular column
b[0]= t[0][1]-t[0][0]; //Compute score for first column (Absolute Value)
b[1]= Max (b[0] + Score for column 1 vertically, Score for first 2 horizontal columns);
for i=0...n 
  b[i]= Max ( b[i-1] + Score for column i vertically, b[i-2] + Score for horizontal columns i & i-1);
print b[n-1];

Works efficiently on the given data set, with a linear time complexity!

  • +1 Excellent solution and question. Any reasons why you feel Dynamic Programming Approach was appropriate? Is this possible with brute force and if so how would it compare performance wise? – maple_shaft Dec 24 '12 at 13:12
  • Note that the performance may be improved if you also run it on the reversed/rotated version of your testset. @maple_shaft Given the size of the testset brute force would probably not be possible. – Dennis Jaheruddin Dec 27 '12 at 9:00
2

Here is one way to approach/describe the problem:

When looking at the 2xN grid, you can see that any tiling is uniquely defined in the following way:

For the most left block, see if it is horizontal or vertical. Then look at the next block.

Suppose 2 stands for horizontal and 1 stands for vertical your Tiling 1 can be written as: 121 whilst Tiling 2 can be written as 22

Given each vector, calculating the total cost should be straightforward.

Now you can use this algorithm:

  1. Find a starting position (probably your own algorithm can do the trick here)
  2. Given a window length (say 5) try all combinations of ones and zeros within the window and calculate what the maximum improvement is.
  3. Optional: Execute this improvement
  4. Shift the window, so instead of looking at the first 5 odd columns now look at odd column 2 to 6
  5. If you are not yet at the end, go to step 2, else execute the improvement.
  6. Optional: If you found any improvements, you can go to step 1
-2

Here's C++ implementation in O(n) :

Using dynamic programming, we are building from the bottom-up, the best solution for each and every column.

Base cases are column 0 and 1 :

Best[0] => The score for mini tiles of column 0

Best[1] => The maximum out of 2 possible solutions set! (1. Row wise pairing and 2. column wise pairing)

Otherwise :

Best[n] => The maximum out of 2 possible solutions set again (1. The sum of new column and the older best solution B[n-1] 2. The sum of older best solution B[n-2] and the new 2x2 tile square formed)

#include<iostream> 
using namespace std;
int abs(int n) { if(n < 0) return -1*n ; else return n; }

int main()
{
    int n, A[100001][2], B[100001], i, j;
    cin>>n;
    for(i=0;i<2;i++)
    {
        for(j=0;j<n;j++)
            cin>>A[j][i];
    }

    B[0] = abs(A[0][0] - A[0][1]);
    B[1] = max( B[0] + abs(A[1][0]-A[1][1]) , abs(A[1][0]-A[0][0])+abs(A[1][1]-A[0][1]) );
    for(i=2;i<n;i++)
        B[i] = max( B[i-1] + abs(A[i][0]-A[i][1]) , B[i-2] + abs(A[i][0]-A[i-1][0]) + abs(A[i][1]-A[i-1][1]) );

    cout<<B[n-1]<<endl;
    return 0;
}
  • I have used Dynamic Programming (Tabulation). If you could post me the implementation using Memoization, I would be pleased. – Prazzzy Sep 5 '15 at 16:59
  • 3
    Prazzy, Programmers.SE isn't about writing code for other people. You can propose algorithms or architectural advice. Moreover, the OP was looking for an algorithm/approach to solving the problem. I suggest reading the Help Center's guidelines. – Chris Cirefice Sep 5 '15 at 18:04

Not the answer you're looking for? Browse other questions tagged or ask your own question.