Subtask 1

We can brute force over all possible removal orders of the integers. When we remove an integer, we will add the maximum possible value of performing any of the operations with this integer and any of the remaining integers to the total score.

Time complexity: ~\mathcal{O}(N! \times N^2)~

Subtask 2

We can optimise our previous solution using bitmask DP.

Time complexity: ~\mathcal{O}(2^N \times N^2)~

Subtask 3

Each of our operations will either add ~0~ or ~1~ to the total score. Therefore, we only have to try to maximise the number of operations which yield a value of ~1~. We only perform ~N-1~ operations, so the maximum possible score is ~N-1~.

Consider the case where there exists an odd integer, ~x~. For any other integer ~y~, either ~(x+y)~ modulo ~2~ or ~(x \times y)~ modulo ~2~ will be ~1~. Hence, for all integers ~y~ other than ~x~, we can perform the addition or multiplication operation with ~x~ and ~y~, and then delete ~y~. This yields a maximum possible score of ~N-1~.

Now, all we have to deal with is the case where all integers are even. Observe that the addition, subtraction and multiplication operations will yield a value of ~0~, so the only operation we have to consider is the division operation.

Let ~f(x)~ be the maximum number of times we can divide ~x~ by ~2~ and still remain with an integer, i.e., ~x~ is the number of ~2~s in the prime factorisation of ~x~. Then, the division operation between ~x~ and ~y~ will yield a value of ~1~ if and only if ~f(x) = f(y)~.

With this in mind, let's group integers in the array by their value of ~f~. Let ~c[x]~ be the number of integers in the array with a value of ~f(x)~. Then for each value of ~x~, the group of integers with this value of ~f~ can contribute at most ~\max(0, c[x]-1)~ to the total score, since the total whenever two integers in this group contribute ~1~ to the score, one of them must be deleted. Hence, the answer is ~\sum_{i=0}^{29} \max(0, c[x]-1)~.

Time complexity: ~\mathcal{O}(N)~ or ~\mathcal{O}(N \log(\max(A)))~

Subtask 4, Part 1

Let ~w(i, j)~ be the maximum value of any of the operations between ~A_i~ and ~A_j~.

Let's consider a graph containing ~N~ nodes labelled from ~1~ to ~N~, and whenever we make an operation involving ~A_i~ and ~A_j~, we add an edge between ~i~ and ~j~ in the graph. This edge will have a weight equal to the value of ~w(i, j)~.

At any point in time, each connected component in the graph will have exactly one of its elements remaining in ~A~. Since we end up with only one element in ~A~, the graph must have exactly one connected component. Furthermore, the graph contains ~N-1~ edges since ~N-1~ operations are made. Hence, the edges must form a spanning tree. The total score is simply the sum of the weights of the edges in the spanning tree.

Conversely, any spanning tree is achievable. This is because we can continuously choose a leaf in the tree, perform an operation on ~A~ involving the elements corresponding to the leaf and its only neighbour, and then delete the leaf.

Thus, if we build a complete graph where the weight of the edge between nodes ~i~ and ~j~ is ~w(i, j)~, then we simply wish to determine the maximum spanning tree of this graph.

Time complexity: ~\mathcal{O}(N^2 \log N)~

Space complexity: ~\mathcal{O}(N^2)~

Subtask 4, Part 2

Now, we just need a more memory efficient implementation for the maximum spanning tree on the complete graph. We can modify Prim's algorithm to reduce the space complexity.

Firstly, note that we do not need to store any of the edges in the graph - we can recompute any edge's weight at any time.

In Prim's algorithm, let ~S~ be the set of nodes that are part of are spanning tree. Originally, ~S~ only contains node ~1~.

We need to repeatedly find the maximum weight edge between a node in ~S~ and a node outside ~S~. To do this, let ~dist[x]~ store the maximum weight edge of node ~x~ to any node in ~S~, where ~x~ is a node outside ~S~. We can then find the maximum weight edge between a node in ~S~ and a node outside ~S~ by choosing the value of ~x~ with the maximum ~dist[x]~. We will then add ~dist[x]~ to the total score.

Then, we need to add node ~x~ to ~S~, and update the remaining distances. For each node ~y~ that is still not in ~S~, we will set ~dist[y] = \max(dist[y], w(x, y))~.

Time complexity: ~\mathcal{O}(N^2)~

Space complexity: ~\mathcal{O}(N)~