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
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.
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
See my answer below, too long for comment.
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).
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.
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.
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.
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
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.
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. 
See below, again too long for comment.
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.
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…
1 Like
… 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?
Can you please make a test case, which you believe, will this solution?
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.
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
@taran_1407 I’m not getting it; maybe I should try this problem when I learn about 2-SAT?
Well, That would be your choice.