what could be the optimal solution , i have tried brute force as usual it’s TLE 
could anybody help ?
It is similar to find the total number of nodes in smallest path from node 1 to node n in a graph.
yes that’s what i have did CodeChef: Practical coding for everyone
but constructing graph will take O(n^2) time ?
The time complexity of this question depends not on N but on M and K.
Since the graph is divided in grids of size K, the entire graph can be created in O(M*K) time and same time would be required for BFS.
The trick here is to create the graph in a shorter time[O(m+n)]. So how to do that?
Note that there are 2 ways I can move from a client. We can either jump to another client in same grid, or we can go from 1 grid to another using a client which is common in 2 grids.
So basically we can say that there are 2 types of nodes, clients or grids. We make 2 graphs, 1 for joining clients with grids(G1), another for grids with clients(G0). Now we iterate both the graphs, starting with the one for clients first(G0). Any unvisited node in this graph will take jumps[grid]+0 moves(mark jumps[0]=1), because to move from 1 grid to another via same client wont take any extra jump. Then we iterate the other graph, where we find number of jumps to reach another client in same grid. Here jumps[client]=jumps[parent]+1.
You can see my implementation here. The actual solution from where I knew about this is here.
The actual problem with less extreme time constraints is UCBINTH.
1 Like