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

Contest 8
Автор snake, 15 лет назад, По-английски
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!
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

15 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Note that B can be solved without BFS.
→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    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.
    → Ответить
    • 15 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      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?
      → Ответить
      • 15 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        Really, I said improperly. I mean SUBstring with such two letters. On every step I check if robot returns to previous adjacent position.
        → Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    u r right:)
    → Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
My WA idea for C:
Robot way don`t have self-intersecting.
And my AC idea for C:
Every step of robot must have no more than 1 cells, which robot have been.
i.e. check on every step.

Sample (1-way):
08760
09050
12340

9 step - 2 neighbors => BUG
054
123
5 step - 2 neighbors => BUG

If all steps are check without BUG  then OK
→ Ответить