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?

  • $\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


Your Answer

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