ROBOTS COOKOFF: Easy Solution

tutorial
, ,
1

Problem: ROBOTS Problem - CodeChef

This problem can be solved by calculating the position in three different directions (along the three lines passing through each point). The angle between each line is 60 rather than the standard 90 degrees.

Assuming these directions to be x, y, z:
Then find the new position, direction after each substring in three axes

calculating new direction relative to previous and accordingly moving the robot:

d = (d + c) % 6;

New position moving 1 unit in this direction:

        if (d == 0)
            x++;
        else if (d == 1)
            y++;
        else if (d == 2)
            z++;
        else if (d == 3)
            x--;
        else if (d == 4)
            y--;
        else if (d == 5)
            z--;

Which can be translated to 2 axes

finalX = x + (y  /  2) - (z /  2);
finalY = (y + z) * sqrt(3) / 2.0;

This will guarantee the required precision but will exceed the time limit.
Time Complexity: O(NQ)
Here is my submission: https://www.codechef.com/viewsolution/27934250

FOR RANGED QUERIES:

Use prefix-calculation storing the position(in three dimensions) and direction after 1 to i queries.
Then find the relative change in position from before the first operation to the last operation in the query.

Detailed Description:

Assuming xs, ys, zs, ds store the position(x[i], y[i], z[i]) and direction(d[i])
after 1 to i operations

FOR l, r QUERY:
Initial Position will be:

d1 = ds[l - 1]
x1 = xs[l - 1]
y1 = ys[l - 1]
z1 = zs[l - 1]

Final Position:

d2 = ds[r]
x2 = xs[r]
y2 = ys[r]
z2 = zs[r]

Relative change in position:

xq = x2 - x1
yq = y2 - y1
zq = z2 - z1

if d1 == 0:
    x = xq
    y = yq
    z = zq
elif d1 == 1:
    x = yq
    y = zq
    z = - xq
elif d1 == 2:
    x = zq
    y = -xq
    z = -yq
elif d1 == 3:
    x = -xq
    y = -yq
    z = - zq
elif d1 == 4:
    x = -yq
    y = -zq
    z = xq
elif d1 == 5:
    x = -zq
    y = xq
    z = yq

Use these formula to find position in x and y:

finalX = x + (y  /  2) - (z /  2);
finalY = (y + z) * sqrt(3) / 2.0;

Time Complexity: O(N+Q)
Here is my AC submission: https://www.codechef.com/viewsolution/27935391

Expecting some likes :slight_smile:

23 Likes
2

Good solution. I unnecessarily complicated my approach by using Segment Trees but it worked anyway. Yours is a far better way to do it.

1 Like
3

Beautiful solution!
respect++

1 Like
4

I must commend this one. The idea of transformation of axis is pretty neat and beautiful. Especially because the lovely prefix trick works there. One :heart: aint enough for this one.

2 Likes
5

It can actually be done in only 2 directions I think. During the contest I also approached the problem in a similar way however got a WA verdict.
My theory was:

Directions are 0 1 2 3 4 5
Now whenever we get 1 or 5, we go forward by 0.5, for 0 we go forward by 1.
Whenever we get 2 or 4, we go backward by 0.5, for 3 we go backward by 1.
Whenever we get 1 or 2, we go up by sqrt(3)/2.
Whenever we get 4 or 5, we go down by sqrt(3)/2.
Using this I made two prefix arrays namely right[] and up[]. However my solution gave a wrong answer. I posted for the same on the after contest discussion thread earlier but got no answer there.
My Solution

6

" the robot starts in the junction (0,0) and it is oriented towards (1,0) i.e. the direction 0."

I guess you can fix you solution by storing the directions and then using some trigonometry…