Observations, 2-satisfactability and Simulation.
Given a field of length N with some robots having range d implying they can move anywhere in the range p-d, p+d if within the field, one step at a time, Can we assign directions to each of the robots in such a manner that none of the robots collide. You can assume that the robot once reaching either end of their range, will flip their direction and continue moving and they continue to move till the end of the universe.
Once again, I will be sharing two solutions, one intended, and another one as usual mine. (Seems like this is happening a lot with me xD). SOLUTION 1 is my solution, while SOLUTION 2 is intended one. So, here you go.
If two robots at time 0 have odd distance, they can never be at the same position ever Because both of them keep moving at same pace. So, Solve this problem assuming each robot have even distance from all others.
See, Since each robot move by one step in either direction once step, then parity of position of each robot flip after every second. The only exception is robots with range 0, which remain at their position always. Assume 0 range robots don’t exist for now.
Since all robots have even distance, they can never cross each other without colliding with each other. Thus, all the robots now will preserve their initial ordering always.
If two robots try to come near each other, their distance reduces by a factor of 2 every second. The initial distance between them is also even, so it is bound to become 0 before becoming negative. 0 distance implies collision.
With these two observations, we can solve the problem in a much simpler manner. Now, no robot can ever cross each other, which means that any robot, if collide, can only collide with neighboring robots only.
After splitting the robots, we try to assign direction to the current robot, making sure no robot at previous positions collides. We try all four combinations of directions for two robots.
Now, the problem is, how to check if two robots collide. First of all, if their distance is above 20, they can never collide. After that, We can just simulate their movement over X steps. How to decide X? X is just the LCM ie Least Common Multiple of path lengths of both robots. Since path lengths \leq 20, we can safely take X = 400 and run simulation for X steps. If they do collide at the current combination of directions, this combination of direction cannot work. Suppose we get a combination (prev, cur) such that it is possible to assign “prev” direction to previous robots without collision, and this combination does not cause a collision, then the current robot can be assigned “cur” direction.
This way, valid assignment exists if and only if all robots have a direction which they can be assigned, without causing a collision.
Now, considering robots of range 0. They never move, thus dividing the whole range into parts, one to the left and other to the right. We can simply check, if any other robot’s range includes the current position of any 0 range robot, it will collide with the current robot no matter what direction they are assigned, resulting in an unsafe assignment.
Since checking the existence of valid assignment is pretty simple if we get the implication graph, I will be talking mostly about Construction of Implication graph.
Keep one variable for each robot in the graph. Variable value false means robot is assigned direction left, while value True means variable is assigned direction left.
For every pair of the robot, which are near (meaning having distance less than 20), we check by simulation if they ever collide for all four combinations of directions. If they collide, we add a directed edge in implication graph.
For example, suppose if robot 1 (denoted by variable R1) and robot 2 (denoted by R2) collide, if they are assigned direction (left, right), then we add to graph an edge !R1 implies !R2 (read R1 bar implies R2 bar).
This way, we have the implication graph ready, now just run the standard SCC algorithm to get all strongly connected components. If we have R1 and !R1 in the same SCC, There doesn’t exist any valid assignment of direction, hence unsafe. Otherwise, It can be proven that the valid assignment always exists. (SOLUTION 1 also gets the assignment in the process).
For solution 1, the time complexity is O(N) with a constant factor.
For solution 2, The number of edges is bounded by a factor of N, and the time complexity is just the time taken to add edges to graph and finding SCCs which take O(V+E) time, Overall Time complexity is O(N).
AUTHOR’S AND TESTER’S SOLUTIONS:
Feel free to Share your approach, If it differs. Suggestions are always welcomed.