3
$\begingroup$

Regarding this question: Rummikub algorithm.

I was reading the first part of the solution in the posted answer (specifically, when there are no jokers involved, all tiles are distinct and only four colours are involved). Then, I reached the part in which the says that the algorithm runs in $O(ABCD(A+B+C+D))$ time, which is easy to determine why.

However, he the goes on to saying that we can speed up the algorithm so as to run in $O(ABCD)$ time by changing "the recurrence to ensure this occurs only once while maintaining correctness, which leads to $O(1)$ time for every 'cell' in the DP-table".

My problem is: I do not see how this can be done. I have tried playing around a bit with the recurrence, but I do not see how it can be modified, or what else we should keep track of so that we can speed up the time.

Can someone please give me a hint/explanation on how this can be done?

Improve this question
$\endgroup$
1
  • $\begingroup$ I must confess that the answer I wrote is not entirely correct: I don't know how to do this with only one check, but I can do it with 3, which is still a constant and is fine. For a hint: note that any run of length at least 6 can be split into more runs. Then, do we really need to look for runs of length larger than 5? $\endgroup$
    – Discrete lizard ♦
    Sep 27, 2020 at 14:28

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.