1
$\begingroup$

We are given matrix of size at most $21$ by $21$, each number of the matrix is either $-1$, which means empty element, or integer between $1$ and $21$. Each integer may occure several more times in the matrix.

We want to count paths that start in some cell, then moving in one of the four directions (up, down, left, right) visit all $21$ number exactly once.

It is impossible to move on cells marked as $-1$.

For example:

1,  2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, -1, 21
-1,-1,-1,-1,-1,-1,-1,-1,-1, -1, -1, -1, -1, -1, -1, -1, 18, 19, 20
We can start in the upper-left cell, move right until 17 then down, right again, and up on the end.
The second path is the same as the first path but reversed (starting from 21).

My idea is to use dynamic programming with three states $i, j$, coordinates of the current point, and bitmask of the visited cells. However this is pretty slow for numbers up to 21. Is there any way to speed up this calculation.

Link from the task that appeared on the contest: mendo.club/Task.do?id=647

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Could you share the biggest hint of all, whether this problem was created by you or you read this problem somewhere? If it is the former, please explain your motivation. If it is the latter, please add a reference as accessible as possible. $\endgroup$ – John L. Apr 9 '19 at 16:32
  • $\begingroup$ It is one of the problems that appeared on olympiad in informatics in my country couple years ago, however there is no English translation of the problem. $\endgroup$ – someone12321 Apr 9 '19 at 17:15
  • $\begingroup$ It there is a link, please post it, even if it is in Japanese or Romanian or whatever. There is the google website translation tool. In fact, my browser will translate websites automatically to English. I will not delve into the importance of a reference. Let me just say it is too important to miss unless it is obvious not when it appears, for example, in popular textbooks. $\endgroup$ – John L. Apr 9 '19 at 18:18
  • $\begingroup$ mendo.club/Task.do?id=647. Here is link from the task, I avoided posting the link because the given text is very long. $\endgroup$ – someone12321 Apr 9 '19 at 18:29
  • $\begingroup$ Please include the link in your post, not just in the comments -- and please always include the link from the start (without waiting for someone to ask you for it). You've received this feedback many times before: 1, 2, 3, 4, 5, (continued) $\endgroup$ – D.W.♦ Apr 9 '19 at 21:47
0
$\begingroup$

If I understand well, you are looking for an Hamiltonian path which is basically NP-complete. With your DP idea, there is $2^{21} = 2M$ possible bitmasks and there is no way to order them. So I am not sure to understand how it works.

In fact you can start building a graph and get rid of any direction/"-1 cells" consideration. In your example you would get a simple chain from 1 to 21.

Then, in the very general case you may have to explore all possible paths (using DFS for instance). But in this kind of problem you can look for some tricks. The point is to select the 20 edges of the path:

  • Any vertex having only one edge is either start/end (NB a reversed valid path is valid like in your example) and its edge is selected
  • A vertex having 2 edges have these edges selected (unless it is start or end)
  • A vertex having 2 edges selected, have all the other edges removed.
|cite|improve this answer
$\endgroup$
  • $\begingroup$ In the matrix there may be more separated paths since the matrix can have up to 21 x 21 elements maybe with repeating elements, so we still need to save 21*21*2^21 values. $\endgroup$ – someone12321 Apr 9 '19 at 14:04
  • 1
    $\begingroup$ Oh ok, you really have to precise this explicitely in the question ! $\endgroup$ – Optidad Apr 9 '19 at 14:21
0
$\begingroup$

You can use the bitmask of visited numbers instead of the bitmask of visited cells.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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