dmkz's blog

1137C. Museums Tour: WA79 again and again [FIXED]
By dmkz, history, 6 years ago, In English

Hi, I cant understand, why my solution to problem 1137C. Museums Tour is getting WA79. Testcase is large, I tried to found by brute force on small graphs for n <= 4 and d <= 4 and compare with other accepted solutions and did not found counter-test. Can anybody help with understanding why my solution got WA79?

UPD. Fixed. Looks like we can't use dynamic programming on topological order, where we will update dp like: dp[next] = std::max(dp[next], dp[curr] + value[next]) for all edges curr->next, we only allowed use dynamic programming like dp[curr] = std::max(dp[curr], dp[prev]+value[curr]) for all edges prev->curr. Accepted try, difference with wa79.

  • Vote: I like it
  • -23
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +18 Vote: I do not like it

there are 3 guys in submission history who fixed their WA79 solutions — nhho, dobito6 and jzqjzq. You can check what exactly they fixed :D

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

    Thanks, fix from dobito6 helped. Problem was in next: I used dynamic programming from curr to next, it means that for each edge curr->next we update dp[next] as dp[next] = std::max(dp[next], dp[curr] + val[next]). dobito6 changed this dynamic to dynamic prev->curr, it means that for each edge prev->curr we update dp[curr] as dp[curr] = std::max(dp[curr], val[curr] + dp[prev]). I can't believe that we can't use dynamic curr->next on topological order and need to use prev->curr only. Accepted try after this fix and difference with wa79 try — only 3 lines changed: order in dp.

    → Reply