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

Автор brdy, история, 6 лет назад, По-английски

Yes, instead of saying I need "help with problem" or "help with algorithm" where instead I just want you to help debug, I will be straight with you.

I need help debugging.

I have tried debugging for 3 weeks, but no progress.

The problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=230

My Solution (10/11 cases): https://pastebin.com/4kdzmf4F

My solution's idea is basically same as editorial's: convert graph to tsp problem and do tsp like bitmask dp.

But now on RxC = 50x50 and N = 15 case it gets MLE/RTE.

My ideas for what's wrong:

1) Stack exceeded because too deep recursion -- > it's probably not this because I change recursive dp to iterative deepening but it still don't work. (loop decreasing order and call solve())

2) Segfault in dp table -- > I cannot find how it will segfault, I stored 2^16 values for 0...15 element bitmask. 15'th element is ghost island I made so you can start at any other island.

3) Some other memory error -- > I am not experienced enough to find out!

Help me this has been bugging me for so long.

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hey, I still haven't been able to determine the bug. Can somebody advise me on what's going on? (I rechecked all my bounds and input but I don't see how the current objects would fail to store necessary data)

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

You have problem in bfs/add functions. Lets say that you want to add point with coordinates (i,j). You should make grid[i][j] = '.' after you added it to deque immediately, because otherwise the point might be added to deque several times thus be visited several times thus adding another points several times to deque and so on. I am not really sure if it can create loop but it definetely works very long and makes deque's size extremely large thus making MLE.