Grassland Fence#1526

Grassland Fence (Editorial)

The area of a triangle with sides $a, b$ and $c$ is computed in the function area using Heron's formula:

S = (p (p - a) (p - b) (p - c)), где p = (a + b + c) /2

S = \sqrt{(p (p - a)(p - b)(p - c))},~где~p = (a + b + c) / 2

Let $P$ be some subset of the available fence pieces. The function FindSol( $ma s k$ ) finds the maximum area that can be enclosed using triangles formed from the pieces in this subset.

The variable $ma s k$ represents a subset mask: it is a $16$ -bit number whose $i$ -th bit is equal to $1$ if the subset $P$ contains the piece $f e n ces [i]$ fences[i], and $0$ otherwise.

The answer to the problem is the value FindSol( $2^{n} - 1)$ 2^n - 1), where $n$ is the number of elements in the array $f e n ces$ .

The values of all possible masks $ma s k$ lie in the range from $0$ to $2^{16} - 1$ 2^{16} - 1 (since, according to the constraints, there are no more than $16$ fence pieces). The array entry $b es t [ma s k]$ best[mask] stores the maximum area that can be enclosed by the subset of fence pieces corresponding to the mask $ma s k$ .

To compute FindSol( $ma s k$ ) all possible triples of fence pieces $i, j, k$ i, j, k that are present in $ma s k$ should be enumerated. For each triple, the triangle inequality is checked to ensure that a triangle can be formed from these pieces. If a triangle is possible, the following sum is computed:

a r e a (f e n ces [i], f e n ces [j], f e n ces [k]) + F in d S o l (ma s k i, j, k)

area(fences[i], fences[j], fences[k]) + FindSol(mask \ {i, j, k})

Next, all such triples $(i, j, k)$ (i, j, k) are considered, and the one for which this sum is maximal is selected. This maximum value is assigned to $b es t [ma s k]$ best[mask]:

F in d S o l (ma s k) = (i, j, k) \in ma s k 0 \leq i < j < k < n max (a r e a (f e n ces [i], f e n ces [j], f e n ces [k]) + F in d S o l (ma s k ∖ {i, j, k}))

FindSol(mask) = \max_{\substack{(i,j,k) \in mask \\ 0 \le i < j < k < n}} (area(fences[i], fences[j],fences[k]) + FindSol(mask \setminus \{i, j, k\}))

If the lengths of the fence pieces are initially sorted, then when checking the triangle inequality (for a triangle with sides $f e n ces [i], f e n ces [j], f e n ces [k]$ fences[i], fences[j], fences[k]), it is sufficient to check only one condition:

f e n ces [i] + f e n ces [j] > f e n ces [k]

fences[i] + fences[j] > fences[k]

Since after sorting we have

f e n ces [i] \leq f e n ces [j] \leq f e n ces [k],

fences[i] \le fences[j] \le fences[k],

it always follows that

f e n ces [i] + f e n ces [k] > f e n ces [j] и f e n ces [j] + f e n ces [k] > f e n ces [i] .

fences[i] + fences[k] > fences[j] и fences[j] + fences[k] > fences[i].

Example

In the first test, the optimal triangles to construct have sides $(4, 5, 6)$ (4, 5, 6) and $(7, 8, 9)$ (7, 8, 9). The total enclosed area in this case is $36.7544$ .

In the second test, the answer is $0$ , since no triangle can be formed from the available fences.

In the third test, a triangle with sides $(4, 4, 4)$ (4, 4, 4) should be constructed. Note that fence lengths can be repeated.

Algorithm implementation

Declare the global variables.

#define MAX 16
double best[1<<MAX];
int f[MAX+1];

The function area computes the area of a triangle using Heron's formula.

double area(int a, int b, int c)
{
  double p = (a + b + c) / 2.0;
  return sqrt(p * (p - a) * (p - b) * (p - c));
}

The function FindSol returns the maximum area that can be enclosed using triangles formed from the fences included in the mask $ma s k$ .

double FindSol(int mask)
{

If the value in the array $b es t [ma s k]$ best[mask] is greater than or equal to zero, it has already been computed, and the function returns this value. This avoids redundant computations and speeds up the algorithm.

  if (best[mask] >= 0.0) return best[mask];

Initialize $b es t [ma s k] = 0$ best[mask] = 0.

  best[mask] = 0;

Iterate over all possible triples of indices $(i, j, k)$ (i, j, k) such that the corresponding fences are included in $ma s k$ .

  for (int i = 0; i < n - 2; i++)     if (mask & (1 << i))
  for (int j = i + 1; j < n - 1; j++) if (mask & (1 << j))
  for (int k = j + 1; k < n; k++)     if (mask & (1 << k))

Check the triangle existence condition. Since the fences are initially sorted, this condition is sufficient to ensure that a triangle can be formed.

    if (f[i] + f[j] > f[k])

If the triangle exists, compute the sum:

the area of the current triangle $a r e a (f [i], f [j], f [k])$ area(f[i], f[j], f[k]);
plus the maximum area that can be enclosed with the remaining fences, excluding those used in this triple:

F in d S o l (ma s k^(1 << i)^(1 << j)^(1 << k))

FindSol(mask~\hat{}~(1 << i)~\hat{}~(1 << j)~\hat{}~(1 << k))

      best[mask] = max(best[mask], area(f[i],f[j],f[k]) + 
          FindSol(mask ^ (1 << i) ^ (1 << j) ^ (1 << k)));
  return best[mask];
}

The main part of the program. Read the number of fences $n$ .

while (scanf("%d",&n) == 1)
{
  memset(f,0,sizeof(f));

Read the lengths of the fences and sort them in non-decreasing order.

  for (i = 0; i < n; i++) scanf("%d",&f[i]);
  sort(f,f + n);

Initialize the array $b es t$ .

  for (i = 0; i < (1 << MAX); i++) best[i] = -1.0;

Compute and print the answer.

  printf("%.4lf\n",FindSol((1 << n) - 1));
}