“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.
1 Like
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.