ROBAGAIN - EDITORIAL

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:

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.