Getting TLE using BFS

help
, , ,
1

Following is the problem link of one of Hacker Earth’s practice problems on BFS :

Following is the my solution so far :
Submission (35718188) for Question paper | HackerEarth

But I am getting lots of TLEs. Looked for editorial but unable to relate author’s intiution with his code.

Thanks !!!

2

find() method in set takes O(n) time . So, it will give tle.
You need to create visited array as we do in simple bfs but since negative indices are present,we need to create to create map, but operations on map are usually slow, so it will
also give tle.
Now,what you can do??
You have to create visited array in such a way that negative indices get handled.So we need to shift the negative part to postitve somehow.
Maximum negative it can go is:- 5 x1000 x 20 = 1000000= 1000005(we always increase the size a little )
So this extra must be added in the visited array and hence the indices will never go negative.
Size of visited array = Maximum positive side + this extra = 5x1000x20 + 1000000= 2000000 = 2000001.
Rest part is simple bfs.

2 Likes
3

Does it need bfs? Or graph? General math function won’t give AC?

4

It can be solved without using graph or bfs , you can see in the editorial for that but i think bfs
is the most obvious one

1 Like
5

Thank you very much for such detailed explanation. I was able to get AC in all the test cases.

1 Like