Problem Link:
Difficulty:
Easy
Pre-requisites:
Ad-hoc, 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 C-D to make the crossing is: max(dist(A, C), dist(B, D)) + 1/2 len(C-D). Distances can be found in O(1) time by precomputing prefix-sum distances along the cycle. Then brute-force over the edge C-D for each test-case. 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
int dx[] = {0, -1, 0, 1};
int dy[] = {1, 0, -1, 0};
int dir; //in 0 to 3. Turning left is just dir = (dir+1)%4; and right is dir = (dir+3)%4;
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.
FindNextPositionAndDirection (curx, cury, dir)
//first check if the cell to your right is free, then keep moving your direction left one by one and move forward as soon as you can.
dir = (dir+3)%4;
while( (curx + dx[dir], cury + dy[dir]) is a wall)
dir = (dir + 1) % 4;
return (curx + dx[dir], cury + dy[dir], dir);
Now, we just need to find one place from which to start our traversal, and then this walk-along-the-wall “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
|-----|------|-----------|---|-------|----|
A 5 B 6 C 11 D 3 E 7 F 4 A
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:
A--5--B--6--C--11--D--3--E--7--F--4--A--5--B--6--C--11--D--3--E--7--F--4--A
Now, if C to F chose the clockwise route, that would mean
............C--11--D--3--E--7--F...... etc.
whereas if they chose the anticlockwise route, it would mean
...............................F--4--A--5--B--6--C....... etc.
Notice how writing the thing twice makes the wrap-around 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 C–D--E–F route, since the other is more or less similar.
If they crossed at:
C–D:
C would take 0 time to reach its point, and would wait for F
F would take 7 time to reach E and then again 3 time to reach D
Thus at time point 10 = max(dist(C, C), dist(F, D)), they would start swapping, and they’d cross finally at 10 + (len(CD)/2) = 15.5 time.
D–E:
C would take 11 time to reach D,
F would take 7 time to reach E, and then have to wait for C
Thus at time point 11 = max(dist(C, D), dist(F, E)), they would start swapping, and they’d cross finally at time 11 + (len(DE)/2) = 12.5 time.
E–F:
C would take 11 time to reach D and then 3 time to reach E.
F would wait for C to reach.
Thus at time point 14 = max(dist(C, E), dist(F, E)), they would start swapping, and they’d cross finally at time 14 + (len(EF)/2) = 17.5
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.
Now, we have to decide whether they take anticlockwise or clockwise. That amounts to asking, do they cross along the i-j route or along the j-(i+M) route. Let us find the answer for both and take the minimum.
So now, given that we wish to find our answer between i and j.
Let us vary over the edge k-(k+1) that we choose to make the crossing, for i <= k < j. As a function of k, the crossover time = max(dist(i, k), dist(j, k+1)) + 1/2 len(k, k+1).
Let us precompute prefix-sum 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
[5; 11; 22; 25; 32; 36; 41; 47; 58; 61; 68; 72].
Now, we get dist(C, C) = 11 - 11 = 0
dist(C, D) = 22 - 11 = 11
dist(C, E) = 25 - 11 = 14
etc.
Hence, we are given i = node C = 2, and j = node F = 5, and ask between 2 and 5 which edge to choose.
Case k = 2:
max(11-11, 32-22) + 11/2 = 10 + 11/2 = 15.5
etc.
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
