Jaewoo Song
Jaewoo Song

Categories

  • Tech

https://www.acmicpc.net/problem/14217


While handling this problem, I had some troubles that with the right solution and correct examples, the system responded to the memory exceed and time exceed.

After getting passed, still my solution took too much memory and time compared to others so I searched and found some reasons.


-The reason for excessive memory usage-

  1. I defined a state with struct and put the states into a queue every time I visited a spot in every case.
  2. I used sets instead of vectors. Using a set requires more memory than using a vector.
  3. I kept making the array dist while running through BFS. It was enough to make it as a global array and initialize it in each BFS.


-The reason for excessive time consumption-

  1. I searched in a way that (rest)->(destination), not (destination)->(rest). The former should perform BFS in all cases of the spots but the latter has to execute only once. Honestly, it was so stupid of me because both cases have same length so the latter is obviously more efficient…
  2. I used sets instead of vectors. Usually, when building the relations between nodes, many people use an array of vectors but I thought with sets I could get benefits in adding and deleting. But obviously if it is not necessary, a set is slower than a vector because we can access elements in a vector with indices much faster. A set takes $O(nlogn)$ in all operations so it is wasteful. And by my alumnus, I heard that if we need an $O(nlogn)$ operation, a map is faster than a set.


The result of https://www.acmicpc.net/problem/14217.


Both differences in time and memory are remarkable…