Блог пользователя MarioYC

Автор MarioYC, 13 лет назад, По-английски

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?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
13 лет назад, # |
Rev. 7   Проголосовать: нравится 0 Проголосовать: не нравится

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.