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.
there are 3 guys in submission history who fixed their WA79 solutions — nhho, dobito6 and jzqjzq. You can check what exactly they fixed :D
Thanks, fix from dobito6 helped. Problem was in next: I used dynamic programming from
currtonext, it means that for each edgecurr->nextwe updatedp[next]asdp[next] = std::max(dp[next], dp[curr] + val[next]). dobito6 changed this dynamic to dynamicprev->curr, it means that for each edgeprev->currwe updatedp[curr]asdp[curr] = std::max(dp[curr], val[curr] + dp[prev]). I can't believe that we can't use dynamiccurr->nexton topological order and need to useprev->curronly. Accepted try after this fix and difference with wa79 try — only 3 lines changed: order in dp.