NoTwo's blog

strange issue when submitting 590 div. 1C
By NoTwo, history, 9 years ago, In English

Hi, Ok so i solved this problem by converting the map to a graph and then merging all vertices that are in the same country and then i found the minimum connecting subgraph for the 3 vertices. ok now the strange part is that in test case 5, n and m are 1000 and my solution passes this test but in test case 19 n, m are 995 and 997 but i get Memory Limit Exceeded and i cant understand why. i would be grateful if someone helped me out. Thanks...
The link to my submission: 13957392
The link to the problem: 590C - Three States

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

My guess is people aren't willing to help because your code is quite long. I'm not sure what's wrong with it, kind of for the same reason, but I'll pitch in some suggestions:

  1. Don't store the graph explicitly when you have a simple, straightforward implicit structure. Just navigate through all directions {{-1, 0}, {1, 0}, {0, -1}, {0, 1}} for each cell. Storing the graph only causes overhead, which can be significant if you use vector [] and there are many nodes, as is the case here.
  2. Your BFS functions might not behave as expected. I TLE'd this problem during the contest because I didn't realize that in my implementation I had 2 types of edges, so basically I had written Bellman-Ford and its run-time went through the roof. This might also manifest by MLE, because the queue can get very large. See if there's any reason why that may happen.
  3. Your code has a lot of casework which isn't necessary. General tip, try to simplify your code as much as possible before implementing it. It will make possible mistakes come out more easily.

For reference, here's my fixed submission, maybe it helps. http://codeforces.net/contest/590/submission/13855446

→ Reply