You are not logged in. Please login at www.codechef.com to post your questions!

×

ROBAGAIN - EDITORIAL

2
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. :P

EXPLANATION:

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

This question is marked "community wiki".

asked 27 Oct, 23:02

taran_1407's gravatar image

6★taran_1407
3.6k1863
accept rate: 23%

edited 27 Oct, 23:20


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?

link

answered 27 Oct, 23:32

vijju123's gravatar image

5★vijju123 ♦
14.9k11856
accept rate: 18%

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.

(28 Oct, 00:07) taran_14076★
1

@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?

(30 Oct, 11:14) the_extractor4★

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.

(30 Oct, 11:57) taran_14076★

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.

(30 Oct, 11:58) taran_14076★
1

@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?

(31 Oct, 21:52) the_extractor4★
1

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}$?

(31 Oct, 22:13) the_extractor4★

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.

(01 Nov, 19:57) taran_14076★
1

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?

(02 Nov, 12:33) the_extractor4★

See my answer below, too long for comment.

(02 Nov, 15:41) taran_14076★
showing 5 of 9 show all

"Second thing, direction assigned to robot y is same."

But to do that, you'll have to store the answer for y somewhere, won't you? Let's take x, y and z as three consecutive indices of robots, or let's just say that there are only 3 robots. Let the only possible configuration for first two robots be LL, and that for second and third robot be RR. Clearly, it's impossible to assign directions here because the direction of the second robot is not same. But you said that your code only checks if all robots have at least one valid configuration:

"We only check if all robots have at least one valid direction."

That means, you'd first take the first two robots and see that LL configuration is possible for them. Next you take the second and the third robot and see that RR configuration is possible. All robots can be provided directions and you'd print the answer as "safe", which is wrong.

If this is not the case, i.e., while solving for 2nd and 3rd robot, you're also checking that second robot has already been given the direction L and hence RR is not possible for this pair of robots, then that means you'll have to store the answer for at least the previous robot somewhere. And in this way you can store the answers for all robots in an array instead of just the previous robot, which means you can also find out the final configuration of robots in your solution just by taking an array and building the configuration string instead of just storing the answer for the previous robot. Doing that arises this question again: https://discuss.codechef.com/questions/138917/robagain-editorial/139464.

link

answered 06 Nov, 00:39

the_extractor's gravatar image

4★the_extractor
1047
accept rate: 7%

edited 06 Nov, 00:47

Well, when we know, that 2nd robot cannot be assigned Right direction, then the third robot also cannot be assigned right direction.

The reason is, that when we check whether we can assign a direction Y to current robot, we check both directions of previous robot.

This check means, whether previous robot can be assigned direction 'X', and direction X for previous robot and direction Y for current robot does not cause collision.

See the line if(!poss[prevPos][cur%2])continue; in my code. For your example, Since 2nd robot cannot be assigned right direction, we don't consider pairs with that.

(06 Nov, 16:17) taran_14076★
1

Well, when we know, that 2nd robot cannot be assigned Right direction, then the third robot also cannot be assigned right direction.

Why? I'm assuming that RR for 2nd and 3rd robot doesn't cause any collision between them, and LL for the first two robots doesn't cause any collision between the first two, i.e., LL is the only possible configuration for the first 2, and RR is the only possible configuration for last two.

When you're checking for the second and the third robot, you'll see that LR, LL and RL are causing collisions between these two, but RR is not, even if giving RR causes a...

(06 Nov, 17:52) the_extractor4★

... collision between 1st and 2nd robot. But that doesn't matter because while solving for 2nd and 3rd robot, we're checking for collisions between 2nd and 3rd robot only, not between 2nd robot and any previous robot, right?

(06 Nov, 17:54) the_extractor4★

Can you please make a test case, which you believe, will this solution?

(06 Nov, 18:25) taran_14076★

I tried but couldn't make one, it's too hard to simulate the movements manually. Had I been able to make a meaningful case, I would have told you in the very beginning.

Plus, the solution I've described above is what you're doing in your solution, not anything different.

(06 Nov, 22:05) the_extractor4★

while checking valid direction for 3rd robot, we also check, if the direction we are choosing for previous robot, is a valid one? That's all.

See continue statement again

(06 Nov, 23:50) taran_14076★

@taran_1407 I'm not getting it; maybe I should try this problem when I learn about 2-SAT?

(07 Nov, 12:21) the_extractor4★

Well, That would be your choice.

(07 Nov, 21:10) taran_14076★
showing 5 of 8 show all

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.

link

answered 02 Nov, 15:41

taran_1407's gravatar image

6★taran_1407
3.6k1863
accept rate: 23%

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

(02 Nov, 19:36) the_extractor4★

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?

link

answered 02 Nov, 19:54

the_extractor's gravatar image

4★the_extractor
1047
accept rate: 7%

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.

(02 Nov, 20:43) taran_14076★

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.

(02 Nov, 20:43) taran_14076★

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.

(02 Nov, 20:43) taran_14076★
1

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?

(02 Nov, 21:07) the_extractor4★

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.

(02 Nov, 21:46) taran_14076★

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

(02 Nov, 21:49) taran_14076★

See below, again too long for comment.

(06 Nov, 00:40) the_extractor4★
showing 5 of 7 show all
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,498
×446
×185
×161
×70
×35
×14
×8

question asked: 27 Oct, 23:02

question was seen: 620 times

last updated: 07 Nov, 21:10