snake's blog

Contest 8
By snake, 15 years ago, In English
A: STL find(in contest, i was confused with the function find_first_of and find_last_of ,which caused me 3 wa's)

B: Construct the map with obstacles but where the robot moved, Then do a straightforward BFS.

C:Dynamic Program. Every state s's bit means an object, 1 for gotten. And dp[s] means the minimum time for tidying the things.So 
dp[s] = min(mini(dp[s - (1 <  < i)] + singledis[i]), minij(dp[s - (1 <  < i) - (1 <  < j)] + doubledis[i][j]))
Note that there is a important optimization, or TLE.

Waiting for D and E

BTW, I found Khromov solved the Problem C with greedy algorithm!
  • Vote: I like it
  • 0
  • Vote: I do not like it

15 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Note that B can be solved without BFS.
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    What do you mean under "Construct the map with obstacles but where the robot moved"? Do you look through all possible maps or what?

    What about use or not use BFS, I didn't. It can be easier to implement switch-choice: if position next to current but not previous was already visited then BUG. Alone corner case is when there's a string with two letters - "UD", "DU", "LR" or "RL". This case you may check separately.
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      For example,assume that the start point of robot is (100,100).If the movement is "LUR", only (99,100), (100,101), (101,100) can be moved to.
      This case, i think the answer should be BUG. What about yours?
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        Really, I said improperly. I mean SUBstring with such two letters. On every step I check if robot returns to previous adjacent position.
        → Reply
        • 15 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          yeah, I think ur solution is better than mine:)
          → Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    u r right:)
    → Reply