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.