Introduction to the Problem

POLYGON aims at testing the technical skills in Algorithms. More precisely, it is intended to check if the contestants understand the essentials of Complexity Theory and if they are able to apply some of the classical algorithm design techniques (namely, divide and conquer, memory function, or dynamic programming).

It is not difficult to realise that this problem deals with arithmetic expressions. Basically, the first move gives rise to an expression without brackets (which is, in general, ambiguous) and the subsequent moves correspond to the evaluation of a fully parenthesised version of that expression. Since the number of distinct first moves in a polygon with ~N~ vertices is ~N~ (thus, polynomially related to the size of the input), the crucial point is to find out, among the set of the fully parenthesised versions of each of those expressions, which is the highest represented value.

The next issue concerns algorithms for solving POLYGON. Let then ~N~ be the number of vertices of the input polygon, and ~E~ be an arithmetic expression without brackets, generated after the first move. Obviously, ~E~ comprises ~N~ integers and ~N-1~ operators. As we have already mentioned, the question is how to compute the maximum value of the fully parenthesised versions of ~E~ (referred to as parenthesizations of ~E~).

Greedy description

Due to the presence of positive and negative integers, none of the obvious greedy strategies seem to work. Consequently, even if there are algorithms of this sort, they have not been studied.

Brute force

A naive (yet, the most difficult to implement) algorithm generates and evaluates all the possible parenthesizations of the expression. Needless to say, it runs in exponential time, given that the number of distinct parenthesizations of an arithmetic expression with ~k~ operators is the ~(k-1)^{th}~ Catalan number (and it is well known that the Catalan numbers grow exponentially).

According to the divide and conquer approach, we may try to compute the maximum value of ~E~, recursively, in terms of the maximum values of the sub-expressions of ~E~. In this case, although additions do not raise any problem, in that:

$$\displaystyle \max(E_1+E_2) = \max(E_1)+\max(E_2)$$

The rule for products is not so simple, because negative numbers are allowed. Nevertheless, the following equalities hold:

$$\displaystyle \begin{align*} \max(E_1 \times E_2) &= \max\{\max(E_1) \times \max(E_2), \max(E_1) \times \min(E_2), \min(E_1) \times \max(E_2), \min(E_1) \times \min(E_2)\} \\ \min(E_1 \times E_2) &= \min\{\max(E_1) \times \max(E_2), \max(E_1) \times \min(E_2), \min(E_1) \times \max(E_2), \min(E_1) \times \min(E_2)\} \end{align*}$$

Besides,

$$\displaystyle \min(E_1+E_2) = \min(E_1)+\min(E_2)$$

and, if ~I~ denotes an integer (that is to say, an expression without operators),

$$\displaystyle \max(I) = \min(I) = I$$

Moreover, since every expression ~E' = I_1 \circ_1 I_2 \circ_2 I_3 \dots I_k \circ_k I_{k+1}~, with ~k~ operators, can be seen in ~k~ different ways,

$$\displaystyle \begin{align*} &(F_1) \circ_1 (F_2 \circ_2 F_3 \dots F_k \circ_k F_{k+1}) \\ &(F_1 \circ_1 F_2) \circ_2 (F_3 \dots F_k \circ_k F_{k+1}) \\ &\vdots \\ &(F_1 \circ_1 F_2 \circ_2 F_3 \dots F_k) \circ_k (F_{k+1}) \end{align*}$$

we must compute the maximum and the minimum values of each one of them, in order to determine the maximum and the minimum values of ~E'~. Notice that, apart from the specific arithmetic calculations, this problem is very similar to the Matrix-Chain Multiplication one.

It is not difficult to verify that a direct implementation of this algorithm generates many equal recursive calls. As a result, it also falls in the exponential pit (like, for instance, the direct recursive implementation of the Fibonacci function).

Polynomial Algorithms — ~\mathcal O(N^4)~

To overcome the drawbacks caused by equal recursive calls, we can apply two distinct techniques: memory function or dynamic programming. The resulting algorithms run in ~\mathcal O(N^3)~ time and require ~\mathcal O(N^2)~ space, as expected. All the same, the time complexity of POLYGON turns out to be ~\mathcal O(N^4)~, because ~N~ problems (one for each generated expression) are solved.

Polynomial Algorithms — ~\mathcal O(N^3)~

At first sight, we can be led to believe that expressions generated by different first moves are independent. However, after a close examination, we conclude that they actually have many common sub-expressions. So, we can calculate the maximum and the minimum values of each sub-expression only when they are needed for the first time, and use them thereafter, saving a lot of computations. In practice, as the number of distinct sub-expressions is ~N^2~, both the memory function and the dynamic programming algorithms for solving POLYGON run in ~\mathcal O(N^3)~ time and require ~\mathcal O(N^2)~ space.