Sign up ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

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.

share|improve this question
@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

3 Answers 3

up vote 2 down vote accepted

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!

share|improve this answer
+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

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
share|improve this answer

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)

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;

    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]) );
        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]) );

    return 0;
share|improve this answer
I have used Dynamic Programming (Tabulation). If you could post me the implementation using Memoization, I would be pleased. – Prazzzy Sep 5 at 16:59
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 at 18:04

protected by gnat Sep 5 at 17:05

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

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