Boxer's blog

By Boxer, 7 years ago, In English

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

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
7 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.