Hi everyone, I found this problem today, the small n suggested to use a bitmask, so I tried a DP with complexity O(L·n·2n) plus some preprocessing using KMP algorithm to find matches.
You can see my code here.
At first I got TLE, I wask doing a for loop to go through all bits of the mask at the dp part, I changed that to use __builtin_ctz in order to access only position with a bit set to 1 in every iteration, that should have cut down the time to the half, since it goes from n·2n combinations to n·2n - 1, and that gave me an AC.
But I see really faster solutions, is there some additional optimization? or maybe another approach?
I've submitted what is currently the fastest solution on there, which is O(N*M*2^N) but uses a memoised DFS and some simple string hashing to prune the search space.
The contest's post-match commentary (ppsx) gives this complexity for the model answer, although of course that doesn't prove that an asymptotically faster solution doesn't exist.