Sticks#1405

Sticks (Editorial)

Let $S$ be the given set of sticks. It is required to find two disjoint subsets $A$ and $B$ of $S$ such that the sticks in each of them can be divided into two subsets with equal total lengths.

For every subset $ma s k \subseteq S$ mask \subseteq S, compute the total length of its sticks and store it in $s u m [ma s k]$ sum[mask].

Iterate over all subsets $I \subset S$ I \subset S. For each subset $I$ , go through all of its subsets $J \subset I$ J \subset I. If there exists such a subset $J$ that $2 \cdot s u m [J] = s u m [I]$ 2 \cdot sum[J] = sum[I] (that is, the total length of sticks in $J$ is exactly half of the total length of sticks in $I$ ), then the subset $I$ can be used as a pair of opposite sides of a rectangle. In this case, set $c an [I] = t r u e$ can[I] = true.

The entire procedure runs in $O (3^{n})$ O(3^n).

Iterate over all subsets of the set of sticks. If for some subset I there exists a subset $J \subset I$ J \subset I such that $c an [J] = t r u e$ can[J] = true and $c an [I x or J] = t r u e$ can[I~xor~J] = true (that is, the subsets $J$ and $I x or J$ I~xor~J are disjoint), then we obtain one of the possible distributions of sticks between the horizontal and vertical sides of the rectangle.

The side lengths of such a rectangle are $s u m [J] /2$ sum[J] / 2 and $s u m [I x or J] /2$ sum[I~xor~J] / 2. Among all such possible rectangles, choose the one with the maximum area.

Algorithm implementation

The lengths of the sticks are stored in the array $a$ . For each subset of sticks $ma s k$ , store their total length in the array $s u m [ma s k]$ sum[mask]. The value $c an [ma s k]$ can[mask] is set to $t r u e$ if the subset $ma s k$ can be divided into two parts with equal total lengths — these will correspond to the opposite sides of a rectangle.

#define MAX 16
int a[MAX];
int sum[1 << MAX];
bool can[1 << MAX];

The main part of the program. Read the input data.

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

Iterate over all subsets of sticks and compute the total length of each subset.

for (i = 0; i < 1 << n; i++)
  for (j = 0; j < n; j++)
    if (i & (1 << j)) sum[i] += a[j];

Then, iterate through all possible subsets of the set of sticks. If for some subset $I$ there exists a subset $J \subset I$ J \subset I such that the total length of sticks in $J$ is exactly half of the total length of sticks in $I$ , set $c an [I] = t r u e$ can[I] = true. In this case, the sticks from subset $I$ can be used as opposite sides of a rectangle.

for (i = 1; i < 1 << n; i++) 
{
  int s = sum[i];
  for (j = i; j > 0; j = (j - 1) & i)
    if (sum[j] * 2 == s) 
    {
      can[i] = true;
      break;
    }
}

C++

Iterate over all subsets of the set of sticks. If for some subset $I$ there exists a subset $J \subset I$ J \subset I such that $c an [J] = t r u e$ can[J] = true and $c an [I x or J] = t r u e$ can[I~xor~J] = true, then we obtain one of the possible distributions of sticks between the horizontal and vertical sides of the rectangle. The side lengths of such a rectangle are $s u m [J] /2$ sum[J] / 2 and $s u m [I x or J] /2$ sum[I xor J] / 2.

res = 0;
for (i = 1; i < 1 << n; i++)
  for (j = i; j > 0; j = (j - 1) & i)
    if (can[j] && can[i ^ j])
      res = max(res, sum[j] / 2 * 1LL * sum[i ^ j] / 2);

Print the area of the rectangle with the maximum size found.

printf("%lld\n",res);