Harry The Potter
Contest: Codeforces Round 612 (Div. 1)
Difficulty rating: 3100
Tags: brute force, constructive algorithms, dp, fft, implementation, math

To defeat Lord Voldemort, Harry needs to destroy all horcruxes first. The last horcrux is an array $$$a$$$ of $$$n$$$ integers, which also needs to be destroyed. The array is considered destroyed if all its elements are zeroes. To destroy the array, Harry can perform two types of operations:

1. choose an index $$$i$$$ ($$$1 \le i \le n$$$), an integer $$$x$$$, and subtract $$$x$$$ from $$$a_i$$$.
2. choose two indices $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n; i \ne j$$$), an integer $$$x$$$, and subtract $$$x$$$ from $$$a_i$$$ and $$$x + 1$$$ from $$$a_j$$$.

Note that $$$x$$$ does not have to be positive.

Harry is in a hurry, please help him to find the minimum number of operations required to destroy the array and exterminate Lord Voldemort.

Input format:
The first line contains a single integer $$$n$$$ — the size of the array $$$a$$$ ($$$1 \le n \le 20$$$).

The following line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ — array elements ($$$-10^{15} \le a_i \le 10^{15}$$$).

Output format:
Output a single integer — the minimum number of operations required to destroy the array $$$a$$$.

Constraints:
Time limit: 9.0 s
Memory limit: 1024.0 MB

Note:
In the first example one can just apply the operation of the first kind three times.

In the second example, one can apply the operation of the second kind two times: first, choose $$$i = 2, j = 1, x = 4$$$, it transforms the array into $$$(0, -1, -2)$$$, and then choose $$$i = 3, j = 2, x = -2$$$ to destroy the array.

In the third example, there is nothing to be done, since the array is already destroyed.

Example input:
3
1 10 100

Example output:
3

Example input:
3
5 3 -2

Example output:
2

Editorial:
Assume that we have done $$$m$$$ queries of the second type. On the $$$i$$$th query we subtracted $$$x_i$$$ from $$$a_{p_i}$$$ and $$$x_i + 1$$$ from $$$a_{q_i}$$$. Let's construct undirected graph on $$$n$$$ vertices with edges $$$(p_i, q_i)$$$. Assume we have a cycle $$$c_1, c_2, ..., c_k$$$ in this graph, then, we can replace queries along this cycle with single queries of the first type to each vertex. Therefore, in an optimal answer queries of the second type form a forest.
Let's call subset good if it size is $$$k$$$ and it can be destroyed with $$$k - 1$$$ operations of the second type. So, the problem is equivalent to grouping some of the elements of $$$a_i$$$ into maximal number of disjoint good subsets. Elements that do not belong to any set can be destroyed with operations of the first type.
Let's find out whether a subset $$$S$$$ is good or not. Let's forget about + 1 in a query(e.g. we subtract $$$x$$$ and $$$x$$$). Consider a sequence of $$$m$$$ queries $$$p_i$$$, $$$q_i$$$, $$$x_i$$$ that destroys $$$S$$$ and $$$(p_i, q_i)$$$ form a connected tree. Let's select an arbitrary vertex of this tree as a root. Then, it is easy to see that for each vertex only its height modulo 2 is matter. Therefore, we can consider only trees of the following structure:
The elements with the even height contribute positive change to the root, the elements with the odd height contribute negative change to the root. So, our problem is equivalent to finding the set $$$T \subset S$$$ such that $$$sum(S \setminus T) - sum(T) = 0$$$ and $$$T \neq \emptyset, T \neq S$$$.
Now we subtract $$$x$$$ and $$$x + 1$$$. It turns out that it changes the above condition to $$$sum(S \setminus T) - sum(T) \in \{-|S|, -|S| + 2, ..., |S| - 2, |S|\}$$$ and $$$T \neq \emptyset, T \neq S$$$.
Such set $$$T$$$ can be found with MITM in $$$O((1 + \sqrt{2}) ^ n)$$$ time (knapsack in $$$2^{n/2}$$$ over all subsets).
So, now we know all good subsets. Let $$$A_{mask} = 1$$$ if $$$mask$$$ is a good subset and $$$0$$$ otherwise. Let's denote $$$A * B$$$ operation as OR convolution on independent subsets. Suppose $$$p$$$ is a minimum integer such that $$$\underbrace{A * A * ... * A}_\textit{p times} = 0$$$(e.g. all values of the product array are zero). It is clear that $$$n - p$$$ is a minimal number of operations required to destroy the array. OR convolution on independent subsets can be done in $$$O(n^2 \cdot 2^n)$$$ time and the minimal power can be estimated in $$$O(\log{n})$$$ time. Also, this part can be done with dynamic programming on subsets in $$$O(3^n)$$$ time which some participants managed to squeeze.
So, the total time complexity is $$$O((1 + \sqrt{2})^n + \log{n} \cdot n^2 \cdot 2^n)$$$.