2

(As I am new and may not be aware of the code of conduct, feel free to edit this post to make this better and more helpful to other people.)

Greetings everybody!

This problem is related to this: Problem Link

The problem in brief:

Given a 2xM array and we want to tile it with 2x1 tiles such that the sum of absolute values of the differences of the values "covered" via the individual tiles is maximized. We want to report this max sum.

The problem in detail:

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.

Below is my code for it. Basically, I've done a sort of a recursive thing because there are two cases: (1) One vertical 2x1 tile in the start and (2) Two horizontal 2x1 laid together to cover 2 columns.

#include <bits/stdc++.h>
using namespace std;

int maxScore(int array[][2], int N, int i);

int main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N;
    int array[N][2]; for(int i=0;i<N;i++) cin >> array[i][0] >> array[i][1]; 

    cout << maxScore(array, N, 0);

    return 0;
}

int maxScore(int array[][2], int N, int i){
    int score1 = abs(array[i][0] - array[i][1]) + maxScore(array, N, i+1);
    int score2 = abs(array[i][0] - array[i+1][0]) + abs(array[i][1] - array[i+1][1]) + maxScore(array, N, i+2);
    return max(score1, score2);
}

However, this seems to be a very inefficient solution and I can't really understand how to cover the base cases (otherwise this would go on forever).

Any help would be really appreciated. Thank You! (BTW I want to create a new tag - Competitive Programming, can anybody help me do so?)

Community
  • 1
  • 1
Vasu090
  • 79
  • 1
  • 10
  • If you are new, I recommend taking the [tour], and [ask]. For new tags check this: https://meta.stackoverflow.com/questions/252944/when-is-it-appropriate-to-create-a-tag-and-how-does-it-work -- do not combine off-topic questions into your question. – chtz Nov 27 '19 at 12:57
  • 2
    And for each question tagged with "competitive-programming" SO should automatically add first comment with these links: [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). – Evg Nov 27 '19 at 12:59
  • 2
    The issue is that you are performing several times the same evaluations. You can avoid such duplicates with *memoization*, i.e. creating an array `known_value[N]`. That being said, in such a situation, I will try to implement a simple `for` loop`. – Damien Nov 27 '19 at 13:09
  • 1
    Do you have to cover every square? It seems like there could be cases where you leave uncovered squares in order to get pairs with large differences. – stark Nov 27 '19 at 13:12
  • @Damien Thank you for the help. I am not very comfortable with memoization and how to apply it here. Also, of course, a greedy algorithms wont help here. Do you have any ideas if we can do this by a top down or bottom up approach? Thanks again. – Vasu090 Nov 27 '19 at 13:15
  • @stark "You have to place tiles to cover all the squares in the grid" (the in detail part of the problem) so I guess the answer is yes. – Vasu090 Nov 27 '19 at 13:18
  • Concerning memoization: at the end of the `maxScore`, just add `known_value[i] = max(...)` and at the begining of the same function : `if (known_value[i] != -1) return ...;`But again a `for` loop could be faster a little bit. – Damien Nov 27 '19 at 13:18
  • `for` loop: `score[i] = max (score[i-2] + ..., score[i-1] + ...);` – Damien Nov 27 '19 at 13:24
  • Another comment on style: `int array[N][2];` with `N` unknown at compile-time is not standard C++: https://godbolt.org/z/dVXsAA, better use something like `std::vector >` – chtz Nov 27 '19 at 13:29

2 Answers2

1

This is intentionally not a complete solution, but should help you find a much faster implementation.

Since you need to cover every square of a 2xM grid, there is no way you have dominoes placed like this:

. . .[#|#]. .
. .[#|#]. . .

So essentially, for every sub-block the right most domino is vertical, or there are two horizontal ones above each other.

If you start from the left, you only need to remember what your best result was for the first n or n-1 tiles, then try placing a vertical domino right to the n-solution or two horizontal dominoes right to the n-1 solution. The better solution is the best n+1 solution. You can compute this in a simple for-loop, as a first step, store all partial solutions in a std::vector.

chtz
  • 17,329
  • 4
  • 26
  • 56
  • Hi chtz! Thanks for the help! But.. how do I code this? I am having difficulty on how to code the approach you've suggested.. Any help would be appreciated. Thanks again – Vasu090 Nov 28 '19 at 11:06
  • I won't extend this answer unless you have very specific questions about it. Maybe find a [good book on c++](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) – chtz Nov 28 '19 at 15:19
1

Maintain an array of the best solutions, where the value in column i of the array is the best solution considering only the matching colums of the input matrix. Then arr[i] = max possible by adding either one tile to the arr[i-1] solution, or 2 to the arr[i-2] solution. Treat arr[-1] as 0 and set arr[0] to the val of one vertical dominoe.

Dave
  • 7,460
  • 3
  • 26
  • 39