Kitchen Robot#2268

Kitchen Robot (Editorial)

Let $A$ and $B$ be two bottles that the robot will pick up sequentially. After the robot picks up bottle $A$ , it must carry it to one of the four edges of the table and dispose of it. Only then may the robot proceed to bottle $B$ . We need to find the shortest path for the robot from point $A (x_{i}, y_{i})$ A(x_i, y_i) to point $B (x_{j}, y_{j})$ B(x_j, y_j), with a mandatory visit to the table's edge.

The distance $A K + K B = A K + K P = A P$ AK + KB = AK + KP = AP. Knowing the coordinates of points $A (x_{i}, y_{i})$ A(x_i, y_i) and $P (x_{j}, - y_{j})$ P(x_j, -y_j), we can compute this distance:

A P = (x_{j} - x_{i})^{2} + (- y_{j} - y_{i})^{2} = (x_{j} - x_{i})^{2} + (y_{j} + y_{i})^{2}

AP = \sqrt{(x_j - x_i)^2 + (-y_j - y_i)^2} = \sqrt{(x_j - x_i)^2 + (y_j + y_i)^2}

The distance $A L + L B = A L + L Q = A Q$ AL + LB = AL + LQ = AQ. The $x$ -coordinate of point $Q$ equals $w + (w - x_{j}) = 2 w - x_{j}$ w + (w - x_j) = 2w - x_j. Knowing the coordinates of points $A (x_{i}, y_{i})$ A(x_i, y_i) and $Q (2 w - x_{j}, y_{j})$ Q(2w - x_j, y_j), we can compute this distance:

A Q = (2 w - x_{j} - x_{i})^{2} + (y_{j} - y_{i})^{2}

AQ = \sqrt{(2w - x_j - x_i)^2 + (y_j - y_i)^2}

The distance $A E + E B = A E + E T = A T$ AE + EB = AE + ET = AT. Knowing the coordinates of points $A (x_{i}, y_{i})$ A(x_i, y_i) and $T (- x_{j}, y_{j})$ T(-x_j, y_j), we can compute this distance:

A T = (- x_{j} - x_{i})^{2} + (y_{j} - y_{i})^{2} = (x_{j} + x_{i})^{2} + (y_{j} - y_{i})^{2}

AT = \sqrt{(-x_j - x_i)^2 + (y_j - y_i)^2} = \sqrt{(x_j + x_i)^2 + (y_j - y_i)^2}

The distance $A D + D B = A D + D S = A S$ AD + DB = AD + DS = AS. The $y$ -coordinate of point $S$ equals $l + (l - y_{j}) = 2 l - y_{j}$ l + (l - y_j) = 2l - y_j. Knowing the coordinates of points $A (x_{i}, y_{i})$ A(x_i, y_i) and $S (x_{j}, 2 l - y_{j})$ S(x_j, 2l - y_j), we can compute this distance:

A S = (x_{j} - x_{i})^{2} + (2 l - y_{j} - y_{i})^{2}

AS = \sqrt{(x_j - x_i)^2 + (2l - y_j - y_i)^2}

Let us find the minimum distance the robot must travel to throw away the bottle located at point $(x_{i}, y_{i})$ (x_i, y_i) over the edge of the table. This distance is equal to the minimum of the four values:

min (x_{i}, y_{i}, w - x_{i}, l - y_{i})

min(x_i, y_i, w - x_i, l - y_i)

This is exactly the path the robot will have to take to dispose of the last bottle.

The initial position of the robot and the coordinates of all bottles are given. Consider a graph where vertex $0$ corresponds to the robot’s starting position, and the remaining vertices correspond to the bottles. The distance between vertex 0 and any other vertex is defined as the Euclidean distance between the corresponding points. The distance between bottles $i$ and $j$ is defined as the minimum path the robot must travel from bottle $i$ to bottle $j$ , with the requirement that it must touch the edge of the table. Since there are $n$ bottles on the table, the graph will contain $n + 1$ n + 1 vertices.

Next, we need to find a Hamiltonian path of minimum length in this graph. After the robot reaches the last bottle, we must add the distance required to throw this bottle off the edge of the table to the total path length. The Hamiltonian path is computed using dynamic programming over subsets, with a time complexity of $O (n^{2} \cdot 2^{n})$ O(n^2 \cdot 2^n).

Example

Below are the robot's initial position and the coordinates of the bottles.

The length of the robot's shortest path is

1 + 3^{2} + 2^{2} + 1 = 2 + 13 \approx 5.605

1 + \sqrt{3^2 + 2^2} + 1 = 2 + \sqrt{13} ≈ 5.605

Algorithm implementation

Let's define the constant $I N F$ to represent infinity, and the constant $M A X$ as the maximum number of points in the Hamiltonian path.

#define INF 1e18
#define MAX 20

Declare an array $d p$ that will store the values $d p (S, i)$ dp(S, i), which are computed dynamically. The coordinates of the bottles are stored as points $(x_{i}, y_{i}) (1 \leq i \leq n)$ (x_i, y_i)~(1 \le i \le n). The robot's initial position is stored at the point $(x_{0}, y_{0})$ (x_0, y_0).

double dp[1 << MAX][MAX + 1];
double x[MAX], y[MAX], m[MAX][MAX];

The function solve computes the value $d p (S, l a s t)$ dp(S, last) — the minimum distance required to visit all points in the set $S$ , finishing at the vertex $l a s t$ . The set $S$ is encoded by an integer $ma s k$ . Then:

d p (S, l a s t) = i \in S ∖ l a s t min (d p (S ∖ l a s t, i) + m [i] [l a s t]),

dp(S, last) = \min_{i \in S \setminus {last}}⁡(dp(S \setminus {last},i) + m[i][last]),

where

$m [i] [l a s t]$ m[i][last] is the distance between points $i$ and $l a s t$ ,
$S ∖ l a s t = ma s k ˆ (1 << l a s t)$ S\setminus {last} = mask~\^{}~(1<< last) is the set $S$ without the element $l a s t$ .

The variable $r es$ corresponds to the cell $d p [ma s k] [l a s t]$ dp[mask][last], so when $r es$ is updated, the value of $d p [ma s k] [l a s t]$ dp[mask][last] is automatically updated as well.

double solve(int mask, int last)
{
  double &res = dp[mask][last];
  if (res == INF)
  {
    mask ^= (1 << last);
    for (int i = 1; i < n; i++)
      if ((mask & (1 << i)) && (i != last)) 
        res = min(res, solve(mask, i) + m[i][last]);
  }
  return res;
}

C++

The function f returns the shortest distance from the point $(x [i], y [i])$ (x[i], y[i]) to the edge of the table.

double f(int i)
{
  return min(min(x[i], y[i]), min(l - y[i], w - x[i]));
}

The function dist returns the distance between the points $(x [i], y [i])$ (x[i], y[i]) and $(x [j], y [j])$ (x[j], y[j]).

double dist(int i, int j)
{
  return sqrt((x[i] - x[j])*(x[i] - x[j]) + 
              (y[i] - y[j])*(y[i] - y[j]));
}

The main part of the program. Read the table dimensions $w$ and $l$ .

scanf("%d %d", &w, &l);

Read the number of bottles $n$ and their coordinates $(x [i], y [i])$ (x[i], y[i]).

scanf("%d", &n);
for (i = 1; i <= n; i++)
  scanf("%lf %lf", &x[i], &y[i]);

The robot’s initial coordinates are stored in $(x [0], y [0])$ (x[0], y[0]).

scanf("%lf %lf", &x[0], &y[0]);

We add a zero vertex to the $n$ bottles, corresponding to the robot's initial position. After that, $n$ is increased by one and becomes the total number of vertices in the graph. The graph vertices are numbered $0, 1, ..., n - 1$ 0, 1, ..., n - 1.

n++;

Let's compute all pairwise distances between the bottles. The distance between bottles $i$ and $j$ is defined as the minimum path the robot must travel from bottle $i$ to bottle $j$ , with the requirement that it must touch the edge of the table.

for (i = 1; i < n - 1; i++)
for (j = i + 1; j < n; j++)
  m[i][j] = m[j][i] =
    min(
 	min(sqrt((x[i] + x[j])*(x[i] + x[j]) + (y[i] - y[j])*(y[i] - y[j])),
     sqrt((2 * w - x[i] - x[j])*(2 * w - x[i] - x[j]) + 
          (y[i] - y[j])*(y[i] - y[j]))),
 min(sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] + y[j])*(y[i] + y[j])),
     sqrt((x[i] - x[j])*(x[i] - x[j]) + 
          (2 * l - y[i] - y[j])*(2 * l - y[i] - y[j])))
       );

C++

Initially, the values of $d p (S, i)$ dp(S, i) are unknown, so we assign them positive infinity.

for (i = 0; i < 1 << n; i++)
for (j = 0; j < n; j++)
  dp[i][j] = INF;

The set ${0}$ corresponds to the mask $1$ . Set $d p ({0}, 0) = 0$ dp(\{0\}, 0) = 0, since the minimum path from the zero vertex to itself without visiting other vertices is zero. The variable $t o t a l$ will store the required minimum length of the Hamiltonian path.

dp[1][0] = 0; total = INF;
for (i = 1; i < n; i++) dp[1 | (1 << i)][i] = dist(0, i);

Find the Hamiltonian path of minimum length. The value $2 n - 1$ 2n - 1 corresponds to the set of all vertices ${0, 1, 2, ..., n - 1}$ \{0, 1, 2, ..., n - 1\}. Compute the minimum among all values:

d p ({0, 1, 2, ..., n - 1}, i) + f (i), 1 \leq i < n

dp(\{0, 1, 2, ..., n - 1\}, i) + f(i), 1 \le i < n

After obtaining the minimum length of the Hamiltonian path, we must add the distance the robot needs to travel to throw the final bottle $i$ off the edge of the table — this distance is $f (i)$ .

for (i = 1; i < n; i++)
  total = min(total, solve((1 << n) - 1, i) + f(i));

Print the required minimum path length.

printf("%.6lf\n", total);