Problem Link:Difficulty:Easy Prerequisites:Adhoc, Coding Intensive Problem:You are given a room in which at each 90 degree corner, a child is standing. Children swap positions by walking along the wall of the room. Inside the room, any number of swaps may happen simultaneously. Each child takes one unit of time to walk one cell of the room. What is the minimum time that certain pairs of friends can cross each other? For description of the input format of the room, kindly refer the original Problem link. Quick Explanation:Make a graph : nodes are children, edges are between adjacent children and have weight = length of the walk between the two. This graph is a cycle. Now, given a pair of vertices, find if they were to take the clockwise path, how early would they reach. If we were to fix the particular edge at which they cross, then the time required to make the crossing decreases then increases. This is because, the time to make the crossing for A and B, if they choose the edge CD to make the crossing is: max(dist(A, C), dist(B, D)) + 1/2 len(CD). Distances can be found in O(1) time by precomputing prefixsum distances along the cycle. Then bruteforce over the edge CD for each testcase. Alternately, you could start from A and B, and as long as there is more than one edge between the two, make them both walk towards each other. The hardest part then, is constructing the graph from the input. This can be done in many ways, one of which is by literally walking along the wall. Assume you have your 4 directions in order of say E, N, W, S. That is, for each direction, the next one is when you turn left. It is a very good strategy in a number of problems to have the following two arrays
Now, let us say we have our right hand along the wall and we have just moved to the free cell curx, cury. The following pseudocode will get you to your next position.
Now, we just need to find one place from which to start our traversal, and then this walkalongthewall "robot" will enumerate the movement. Whenever we hit a corner, we note down the distance traveled. Detailed Explanation:In this problem, let us consider a graph where children who are at corners are vertices and adjacency is as given in the problem: where you consider two children are adjacent if they reach each other by walking along the wall. Further, lets give weight of edges as the length required to walk between the two corners. This graph is now a cycle. Now, given a pair A, B of children, we have to decide whether they will take the anticlockwise route, or the clockwise route, and how much time will it take in the minimum between the two. Let us write down the edge lengths in a line
Note that since its a cycle, the last person is same as the first. Now, if we were to ask for what edge will the pair say, (C, F) choose to cross? A good tactic to use when you have a circle is to write down the values twice so that wrapping around amounts to just going further in the same direction. That means we now have something that looks like:
Now, if C to F chose the clockwise route, that would mean Notice how writing the thing twice makes the wraparound the circle now just a linear chain, between two choices. Hence, let us use this. Now, we know that C and F are at some point going to cross. What if we iterate over this point? Let us only consider the CDEF route, since the other is more or less similar. If they crossed at: DE: EF: Hence, among these three choices, they would take 12.5 time. In general, what can we say? We have some M nodes in our graph. And we have got a chain of length 2M, by unwrapping the circle. Now, what is the minimum time for nodes i and j to cross each other? Assume i < j. So now, given that we wish to find our answer between i and j. Let us precompute prefixsum lengths along the cycle. Prefix sums help because if we wanted to find the distance between node i and node j, we would just ask prefsum[j]  prefsum[i]. So, in our example, we have the prefix sums looking like Hence, we are given i = node C = 2, and j = node F = 5, and ask between 2 and 5 which edge to choose. Thus, complexity = O(T * M) where M is the number of nodes. To construct the graph would take O(N^2) time for walking and finding out distances. The fact that a horizontal line between two points inside the room is always within the room puts the bound that M <= 2*N. Setter's Solution:Can be found here Tester's Solution:Can be found here
This question is marked "community wiki".
asked 13 Feb '13, 22:16

You can also precompute the answer for all pairs in O(N^2) time, using a sliding algorithm  for a fixed start node, as the end increases, the crossover edge does not decrease. Fun problem :) answered 14 Feb '13, 11:15

i got TLE with this approach.(submission id 1817676) had to implement binary search to get AC (submission id 1819189) answered 14 Feb '13, 11:48

Both solutions are not available.
Fixed the links.
link to practice problem is broken, so can't submit under practice