Contest Duration: - (local time) (120 minutes) Back to Home

## D - く / L Editorial by evima

For each L-placement of stones, let us consider the sum of $$x$$-coordinates and that of $$y$$-coordinates: $$(ax+bx+cx, ay+by+cy)$$. Different placements have different pairs of coordinate sums, which can be shown as follows:

Let $$(x, y)$$ be the coordinates of the stone at the center of an L. We can then represent the coordinates of the other stones as $$(x+dx, y), (x, y+dy)$$, where $$dx, dy\in \{1,-1\}$$. Here, the sums of $$x$$- and $$y$$-coordinates are $$(3x+dx, 3y+dy)$$. Thus, when the sums of $$x$$- and $$y$$-coordinates are $$(X, Y)$$, we can compute the $$x$$-coordinate of the central stone by rounding off $$X/3$$. We can also compute $$dx, dy$$, so we can restore the coordinates of each stone from the sums of $$x$$- and $$y$$-coordinates, completing the proof.

Therefore, the problem can be rephrased as changing the pairs of coordinate sums from $$(1,1)$$ to $$(ax+bx+cx, ay+by+cy)$$. With a breadth-first search, let us find the shortest paths within a small region. The result is as follows:

 7,  , 6, 6,  , 6, 6,  , 6, 6,  , 6, 6,  , 6, 6,  , 6, 6,  , 7,
,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,
7,  , 6, 5,  , 5, 5,  , 5, 5,  , 5, 5,  , 5, 5,  , 5, 6,  , 6,
7,  , 6, 5,  , 4, 4,  , 4, 4,  , 4, 4,  , 4, 4,  , 5, 5,  , 6,
,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,
7,  , 6, 5,  , 4, 3,  , 3, 3,  , 3, 3,  , 3, 4,  , 4, 5,  , 6,
7,  , 6, 5,  , 4, 3,  , 2, 2,  , 2, 2,  , 3, 3,  , 4, 5,  , 6,
,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,
7,  , 6, 5,  , 4, 3,  , 2, 1,  , 1, 1,  , 2, 3,  , 4, 5,  , 6,
7,  , 6, 5,  , 4, 3,  , 2, 1,  , 0, 1,  , 2, 3,  , 4, 5,  , 6,
,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,
7,  , 6, 5,  , 4, 3,  , 2, 2,  , 1, 1,  , 2, 3,  , 4, 5,  , 6,
7,  , 6, 5,  , 4, 3,  , 3, 2,  , 2, 2,  , 2, 3,  , 4, 5,  , 6,
,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,
7,  , 6, 5,  , 4, 4,  , 3, 3,  , 3, 3,  , 3, 3,  , 4, 5,  , 6,
7,  , 6, 5,  , 5, 4,  , 4, 4,  , 4, 4,  , 4, 4,  , 4, 5,  , 6,
,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,
7,  , 6, 6,  , 5, 5,  , 5, 5,  , 5, 5,  , 5, 5,  , 5, 5,  , 6,
7,  , 7, 6,  , 6, 6,  , 6, 6,  , 6, 6,  , 6, 6,  , 6, 6,  , 6,
,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,
8,  , 7, 7,  , 7, 7,  , 7, 7,  , 7, 7,  , 7, 7,  , 7, 7,  , 7,


By observing this table, we can see that the whole table can be computed as follows:

long long solve(long long x,long long y) {
x = (x>0 ? x-x/3 : x+(2-x)/3) - 1;
y = (y>0 ? y-y/3 : y+(2-y)/3) - 1;
if(x==0 && y==0) return 0;
if(x==1 && y==1) return 1;
return max({x,-x,y,-y}) + (x==y);
}


We can prove the validity of this by mathematical induction on the number of steps where we consider the change on the pair of coordinate sums by each way of moving a stone.

Sample Implementation in C++

posted:
last update: