## Editorial for Yet Another Contest 2 P4 - No More Arithmetic

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Josh

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:

We can optimise our previous solution using bitmask DP.

Time complexity:

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

Consider the case where there exists an odd integer, . For any other integer , either modulo or modulo will be . Hence, for all integers other than , we can perform the addition or multiplication operation with and , and then delete . This yields a maximum possible score of .

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 , so the only operation we have to consider is the division operation.

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

With this in mind, let's group integers in the array by their value of . Let be the number of integers in the array with a value of . Then for each value of , the group of integers with this value of can contribute at most to the total score, since the total whenever two integers in this group contribute to the score, one of them must be deleted. Hence, the answer is .

Time complexity: or

Let be the maximum value of any of the operations between and .

Let's consider a graph containing nodes labelled from to , and whenever we make an operation involving and , we add an edge between and in the graph. This edge will have a weight equal to the value of .

At any point in time, each connected component in the graph will have exactly one of its elements remaining in . Since we end up with only one element in , the graph must have exactly one connected component. Furthermore, the graph contains edges since 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 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 and is , then we simply wish to determine the maximum spanning tree of this graph.

Time complexity:

Space complexity:

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 be the set of nodes that are part of are spanning tree. Originally, only contains node .

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

Then, we need to add node to , and update the remaining distances. For each node that is still not in , we will set .

Time complexity:

Space complexity: