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: