PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
The problem statement is simple, imagine a huge 2D visited array. Initially, only visited[0][0] = true and rest all are false. In each step you move in one of the four directions for a specified distance and find the number of previously unvisited cells along the path. We can solve it using visited array if the consrtaints were small, but the distance can be up to a billion. You start from (0,0), move to (x1,y1) and then to (x2,y2) so on. Still we use the same basic idea and maintain a grid. The value of cells on X-axis now are not 0,1,2,3… but only the values of x coordinates at which we stop. If we encounter the cells (0,0), (10,0), (10,20), (5,20), then its enough to maintain the distinct X values {0,5,10} and distinct Y values {0,20}. Note that each step introduces either a new X value or a new Y value, so the grid size is O(N * N). Adjacent cells (i,j) and (i+1,j) in this grid are not actually at distance 1 from each other. You can imagine a line-segment of length X[i+1] - X[i] connecting them. Along with maintaining visited information for cells, you also need to maintain the visited information for these O(N*N) line-segments. This improved bruteforce runs in time O(N * N).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.