Hello everyone, I am trying to solve Move and Turn problem on codeforces. Basically, the problem says that "A Robot is standing at origin and can choose any of the 4 directions to move in 1st step, then it should turn $$$90^\circ$$$ either to left or right at every step. Now, given that Robot has made exactly $$$n$$$ steps, then what is the number of unique points robot can be present at?"
I got the solution presented in the editorial but there is a DP solution given in the comments, which I am trying to understand but not able to.
DP solution
If someone can help me in understanding it, I would highly appreciate it.
When $$$n$$$ is small, you can draw where robot can be present at, then you may understand it better.
The dp solution presented is mostly the same as the author solution. if you reach a point in even
imoves you can do a 4 move sequence likeURDLorLURD, and be in the same point soa[i]is atleasta[i-4]. but because we are alowed 4 more moves some new points are now reachable. if i is even these new points are counted in4*((i+1)/2)you can draw your ponints up to n=8 and circle around new points in even steps to find the pattern. Odd case is more interesting. Consider the first move in oddisteps to reach a point and let it beRfor example, we can replace this first move withU, R, Dand also reverse all the following moves in the sequence so we reach another point. every point reached this way is 1-1 reflection of a point reached withi-2moves. we still have to add newly reachable points with 2 more moves. I didn't have time to draw the steps but if the code is correct, i think the above explanation is the reason.