Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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
add comment

2 Answers

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
add comment

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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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