ROBAGAIN - EDITORIAL

general
, , , , , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Jatin Yadav and Praveen Dhinwa
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh

DIFFICULTY:

Medium

PREREQUISITES:

Observations, 2-satisfactability and Simulation.

PROBLEM:

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. :stuck_out_tongue:

EXPLANATION:

Once again, I will be sharing two solutions, one intended, and another one as usual mine. :stuck_out_tongue: (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.

SOLUTION 1:

Observations:

  • 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.

SOLUTION 2:

For this solution, readers should be aware of 2-satisfiability which you may read here.

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).

Time Complexity

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:

Setter’s solution
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

2 Likes
2 
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.

I also thought of this, but what of the case when some scenario like this happens-

Robot 1- Can be assigned any direction
Robot-2- Can be assigned any direction
.
.
Robot K- A valid configuration for this exists iff Robot 1 is assigned Left.

I felt if K is large, it might lead to either a WA or deep backtracking?

1 Like
3

We just consider every adjacent pair, since I proved, that ordering or robots at even distances will never change, which implies, if any robot will collide first only with an adjacent robot.

4

@taran_1407 There could be a situation that the Kth robot could collide with the (K-1)th robot if the 1st robot is assigned left, but the Kth robot could be safe if the 1st robot is assigned right. And the 1st and the 2nd robots can be assigned any of the four combinations of directions. How to choose the direction of the first robot in this case then?

1 Like
5

See, we assign directions to leftmost robot first, then second and so on.

We find for every robot, which directions they can be assigned. Suppose we can assign left direction to (K-1) robot, but not right. This means, that there’s a possible assignment of first (k-1) robots such that (k-1) robot can be assigned left without collision with any of the robot lying at left.

As i proved, that robots cannot cross each other, hence, for assigning direction to kth robot, we need to check if it collide with immediate left robot only.

6

You can see in my solution, that i assigned directions from left to right, stored in poss[node][dir] array. poss[node][dir] is true, if robot at position node can be assigned dir direction.

7

@taran_1407 What I mean is, if there are multiple possible configurations for the first K-1 robots, will the Kth robot be compatible with all of the configurations of the previous robots, given that it is compatible with at least 1 configuration?

By taking a few test cases, it seems like it is true, but can it be proven?

1 Like
8

To be precise, let a configuration of n robots be denoted by a string of length n consisting only of Ls and Rs, where an L denotes left and an R denotes right.

Let C_k be a valid configuration of the first k robots and C_{k - 1} be a valid configuration of the first k-1 robots. Now let’s say that there exists another valid configuration C_{k-1}' of the first k-1 robots such that at least 1 character of C_{k-1} and C_{k-1}' is different.

My question is, will a valid C_k' exist for all valid C_{k-1}' \neq C_{k-1}?

1 Like
9

Well, If we mark a composition Ck as valid, that means, that there will be at least one composition C_{k-1} which complies with C_k. It is possible that other configurations C'_{k-1} may or may not comply, but the main point is, at least one configuration will comply, and that’s what we need.

10

Let’s say there are five valid configurations C_{k-1} and one valid C_k, and this C_k complies with only one of the five C_{k-1} configurations. So when I’m finding out C_{k-1}, how can I be sure that my code will find that particular C_{k-1} which complies with C_k? It may find another configuration C_{k-1} too because there are five valid values of that. In such a case, my code may give a wrong answer if it calculates a valid C_{k-1} and later checks that there’s no possible C_k with this particular C_{k-1}. So how to handle this?

1 Like
11

Well, I think you misunderstood the whole idea of Solution 1. See, For every robot, we find out whether we can assign this robot without colliding with any of the robot lying to its left.

To find this, We check all four pairs LL, LR, RL, RR, whether these two robot collides if assigned these directions, where the first character is the direction of the previous robot while the second character is the direction of the current robot. Suppose for the previous robot, we already know, it can be assigned only right direction. Now, even if with LL or LR combination, robots don’t collide, it’s useless, since we cannot assign Left direction to the previous robot.

Now, Suppose, both pairs RL and RR cause a collision between these two robots, then the answer is impossible. Otherwise, if RL is valid, and we know, Right direction to the previous robot doesn’t cause collision, we also know, that due to even distances, robots cannot collide with any other robot except neighboring ones, We can be sure, that we can assign Left direction to current robot without causing collision. Using this, repeat the process for the next robot.

The point of all this, which you are missing I guess, is that directions assigned to robots to left of robot k-1 don’t affect the direction of kth robot directly, but affect only through their effect on valid directions for (k-1) robot.

12

See my answer below, too long for comment.

13

I had understood the solution. But my question is a bit different from what you’ve answered. I’ve stated it with an example below (too long for comment).

14

Let k = 7. Now, while calculating the answer for (k-1)th robot, I only have to look at (k-2)th robot. I’ll try all possible combinations for (k-1)th and (k-2)th robot, i.e., LL, RL, LR and RR. Now let’s say, up to first k-2 robots, I have calculated the answer manually, and I know both these configurations are right for the first k-2 robots:

LRLLL
RRLRL

We can see that (k-2)th robot can only be assigned the left direction. Now while calculating the answer for (k-1)th robot, let’s say that it can be assigned both left and right without colliding with (k-2)th robot. So there are four possible valid configurations up to the first k-1 robots:

LRLLLL
LRLLLR
RRLRLL
RRLRLR

Now we’ve to find the answer for the kth robot. Let’s say the kth robot will NOT collide with the (k-1)th robot only if (k-1)th robot is assigned left and kth robot is assigned right. So these will be the two possible configurations up to the first k robots:

LRLLLLR
RRLRLLR

Now the thing is, all the four configurations I’ve written above for the first (k-1) robots are valid, so my code may compute any one of them. But if it computes the second or the fourth one, both of which end with an R, it’ll see that no possible configuration exists for the kth robot (since (k-1)th robot should be L but it is R), and hence it’ll print “unsafe”, which is certainly wrong. So how do I handle this?

15

My solution is initially made for only checking if a valid configuration exists or not. For your example, valid directions for k-1th robot will be L and R, while valid directions for robot k is R only. We only check if all robots have at least one valid direction.

16

If we want to construct a valid configuration, we need to store additional information. We will build the output string from the last robot to first. We know which direction we can assign to last robot, say R. Then, we check, if LR is valid, as well as we know, we have Left direction possible (we know this) without collision with the leftward robot, we can assign 2nd last robot left direction.

17

Otherwise, say Right direction was possible, and not left, then we will assign right direction to second last robot. See, If both left and right are possible, we know, none of the directions will cause collisions, and we may have multiple correct answers, in this case, you may print any of them.

In case you think if both left and right directions not possible for the k-1 robot, then answer is automatically impossible.

18

My solution is initially made for only checking if a valid configuration exists or not. For your example, valid directions for k-1th robot will be L and R, while valid directions for robot k is R only. We only check if all robots have at least one valid direction.

Then you’re essentially making this assumption:

“Let x, y and z be the indices of three robots such that x < y < z. If a valid configuration exists for robots x to y as well as for robots y to z, this implies that a valid configuration exists for robots x to z.”

Can you prove this?

1 Like
19

Correct assumption: “Let x, y and z be the indices of three robots such that x < y < z. If a valid configuration exists for robot x to robot y as well as for robots y to z, this implies that a valid configuration exists for robots x to z.” And,

Adjacent Robots should have even distances. Second thing, direction assigned to robot y is same.

20

Proof: Distance between two robots at any point of time is abs(d+2*x) (x can be negative too) where d is initial distance. if d is odd, above absolute value can never be zero, hence, cannot collide if the initial distance is odd.

Second thing, if you assign LR or RR for pair (x,y) and LL or LR for pair (y,z) this may turn out to be wrong.

But, if direction assigned to y is same, then the configuration, with above assumption, will be correct.

If still a doubt, Make test case to fail my solution. Keep robots at even distance and don’t include 0 power robots for simplicity, though you can. :slight_smile: