Here is another problem that explores the concept used in the last of my problems.
This problem has been taken from INOI 2008.
Domino Solitaire
In Domino Solitaire, you have a grid with two rows and many columns. Each square in the grid contains an integer. You are given a supply of rectangular 2 × 1 tiles, each of which exactly covers two adjacent squares of the grid. You have to place tiles to cover all the squares in the grid such that each tile covers two squares and no pair of tiles overlap. The score for a tile is the difference between the bigger and the smaller number that are covered by the tile. The aim of the game is to maximize the sum of the scores of all the tiles. Here is an example of a grid, along with two different tilings and their scores.
The score for Tiling 1 is 12 = (9 − 8) + (6 − 2) + (7 − 1) + (3 − 2) while the score for Tiling 2 is 6 = (8 − 6) + (9 − 7) + (3 − 2) + (2 − 1). There are other tilings possible for this grid, but you can check that Tiling 1 has the maximum score among all tilings. Your task is to read the grid of numbers and compute the maximum score that can be achieved by any tiling of the grid.
Input format
The first line contains one integer N, the number of columns in the grid. This is followed by 2 lines describing the grid. Each of these lines consists of N integers, separated by blanks.
Output format
A single integer indicating the maximum score that can be achieved by any tiling of the given grid.
Test data
For all inputs, 1 < = N <=10^5. Each integer in the grid is in the range {0, 1, . . . , 10^4}.
we can make a table with each cell containing two values:the difference of the cell and the one to its left and the difference of the cell and the cell above it(for the second row)…..for the given example:
8 6 2 3
9 7 1 2
the table could look like
0,0 2,0 4,0 1,0
0,1 2,1 6,1 1,1
here 0,0 is for 8; 2,0 is for 6 and so on
now the task is to find the maximum possible sum of some of these values in accordance with given rules(that tiles cannot overlap)
this can be done by:
domino(first cell);
domino(cell){
flag[cell]=1 …….to show that it has been visited
score=score + max(domino() of all the cells that are not immediately to the left, right, top or bottom of the current cell and those cells that have not been visited till now)
return score
}
What I understand from your solution is that you are using recursion in your algorithm.
But the thing is that the number of combinations are huge and it wont be a good method(as n is quite large)
I dont know the official solution to the porblem (if any) and so I wont say that your program would(not) work. But indeed, I was able to find out a better way using DP.
So think about Dynamic Programming to solve the problem.
Sorry for the late reply.
hello…never mind about the delay, after all your preboards are going on
yes i have used recursion to check all possibilities which is not very efficient
i have thought of a DP solution:
we proceed by updating the max score that can be obtained till that particular column for all columns from 1 to n
this can be done by:
max[1]=(difference of the cells of the first column)
max[2]=maximum(score obtained by putting both tiles horizontally, score obtained by putting both tiles vertically)
Now,
For i=3 to n (where n is the number of columns)
temp=maximum(score obtained by putting both tiles horizontally in square formed by column i-1 & i, score obtained by putting both tiles vertically)
if temp>max[i-1] then
max[i]=temp + max[i-2]
else
max[i]=max[i-1] + difference of cells in column i
in the end return max[n]
here maximum is a function that returns the greater of two values and max[] is an array of size n
Yes,
This is what I thought and I think this is good enough to secure 100% marks.