Vessels, Heights and Two Versions (Easy Version)

Think in layers

The condition is annoying if we stare at full heights $w_i$. So don’t. Slice the water horizontally.

For an integer layer $y$, vessel $v$ contains this layer iff

$$w_v \ge y.$$

Since

$$\sum_{v=1}^{n} w_v = \sum_{y\ge 1} \#\{v : w_v \ge y\},$$

we can maximize the contribution of every layer separately — as long as the chosen sets are nested. Luckily, they will be.

What happens at one layer?

Consider an edge between two neighboring vessels with partition height $h_e$.

If $h_e < y$, then layer $y$ lies above this partition. Therefore, if one side has water at layer $y$, the other side must also have water at layer $y$. In the formal condition: one height is at least $y > h_e$, so differing heights would be illegal.

So at layer $y$, all vertices connected by edges satisfying

$$h_e < y$$

must either all contain this layer or all not contain it.

Now fix the vessel $r$ that must remain empty, i.e. $w_r = 0$. It never contains any layer. Therefore, every vessel in the connected component of $r$ using only edges with $h_e < y$ also cannot contain layer $y$.

All other vessels can contain layer $y$.

Thus the maximum possible contribution of layer $y$ is

$$n - |\operatorname{comp}_y(r)|,$$

where $\operatorname{comp}_y(r)$ is the component of $r$ in the graph containing exactly edges with $h_e < y$.

Why this upper bound is attainable

For every layer $y$, fill exactly the vessels outside $r$'s component in the graph of edges with $h_e < y$.

As $y$ increases, more edges become active, so $r$'s component only grows. Therefore the set of filled vessels only shrinks. These layer choices are nested, so they define valid integer heights $w_v$.

Also, if two neighboring vessels get different final heights, let the larger height be $L$. At layer $L$, one side is filled and the other is not, so their edge could not have been active. Hence

$$h_e \ge L = \max(w_u,w_v),$$

which is exactly the condition needed for a good array. No black magic, just layers doing the heavy lifting.

Computing the sum

The graph changes only when $y$ passes some height $h_i$.

Sort all cycle edges by height. For a fixed empty vessel $r$, maintain a DSU containing all edges with height at most prev. These are exactly the edges with

$$h_e < y$$

for every layer $y$ in the next interval.

Suppose the next distinct edge height is $x$. For all layers

$$\text{prev}+1,\text{prev}+2,\ldots,x,$$

the active edges are unchanged. There are $x-\text{prev}$ such layers, and each contributes

$$n - |\operatorname{comp}(r)|.$$

So we add

$$(x-\text{prev})\cdot (n - |\operatorname{comp}(r)|).$$

Then union all edges of height $x$, set $\text{prev}=x$, and continue.

After the largest height, all cycle edges are active, so every vessel is connected to $r$ and the contribution becomes $0$ forever.

We repeat this process for each possible empty vessel $r$.

Complexity

For each root, we process $n$ edges with DSU operations. Therefore one test case costs

$$O(n^2 \alpha(n)),$$

and since the statement guarantees

$$\sum n \le 3000,$$

this easily fits. Memory usage is

$$O(n).$$