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

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

Hi everyone , i'm trying to solve this problem Link

I found some discussion in this forum in topcoder Link and they suggest a dp with bitmask.

Well i'm coded a dp with bitmask but i have got TLE

Someone can help me ?

My Implementation : Ideone

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

»
10 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

I'm really skeptical that this problem has a polynomial solution, so it's probably just about optimizing and pruning some type of backtracking.

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

Your solution is ok, but you have to change your dynamic programming by a backtrack to lose the constants of access to std::map, but you have to make some pruning to speed it up.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You know, the word backtrack probably comes from the action of "tracing back" (the last few moves; note that it's 'cing', not 'cking'), not "backing track" :D

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      but it's backtracking, isn't it? :D

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Where I live, we have many words deformed by more comfortable pronounciation (you wouldn't guess what Bluetooth is sometimes called :D). I could be wrong, of course, it's just about what makes more sense to me.