Boxer's blog

ECNA 2007 Problem H: Target Practice
By Boxer, 12 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

»
12 years ago, hide # |
 
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.

→ Reply
»
12 years ago, hide # |
← 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.

→ Reply
  • »
    »
    12 years ago, hide # ^ |
     
    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

    → Reply
    • »
      »
      »
      12 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        12 years ago, hide # ^ |
         
        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.

        → Reply