------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Hello again! Here comes a brief edit because the original message is very unclear:
The problem we are trying to solve is https://open.kattis.com/problems/tray.
The other problem I am discussing, the python code and the video are only to give some background about a similar problem. You can just ignore my blabla, and jump to the problem
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Hello!
It's probably very bad and shameful style from me to ask for help for another problem while the last one (Eulerian path in engineering forum) is not yet solved, but I feel stuck. And you already helped me out so much dynamic programming that I feel confident we will solve it
Here is the
problem description. You are supposed to fill a grid 3 by n, with dominos that are 1 by 1, or 2 by one, placed horizontally or vertically. Some places are forbidden.
It is very similar
to this other problem, where you have only 2 by one dominos. You can generate all solutions column by column, where every solution depends on the previous column. If we represent each column as a binary 2^3, then to have a 1 in column [i+1], the previous column is either completely occupied ([i][7]) or we can place a domino horizontally at the bottom of [i], that will trespass to [i+1], means that we have [i][6] in the previous column. There is a video about it
from William Fiset.
While it is apparently possible to do a similar solution for the new problem, there is an alternative more elegant solution with 2^6 matrix, and recursive calls. I cannot come up with it and don't know how to start experimenting. Will you help me find the way, like we crossed the Hydra?