utils/scrapers/prescraped/codeforces/Editorials/1552D

Suppose that a solution $$$b_1, \, \dots, \, b_n$$$ exists. For each $$$1 \le i \le n$$$, let $$$j_i, \, k_i$$$ be the indices such that $$$a_i = b_{j_i} - b_{k_i}$$$.
Consider the directed graph on vertices $$$1, \, \dots, \, n$$$, with the $$$n$$$ edges $$$j_i \rightarrow k_i$$$. If we ignore, for a moment, the orientations, we are left with an undirected graph with $$$n$$$ vertices and $$$n$$$ edges, which must contain a cycle (possibly a loop). Let $$$m$$$ be the length of one such cycle, and let $$$v_1, \, \dots, v_m$$$ be its vertices.
Now, of course $$$(b_{v_1} - b_{v_2}) + (b_{v_2} - b_{v_3}) + \cdots + (b_{v_m} - b_{v_1}) = 0$$$, since all the terms cancel out. Notice that, for each $$$i$$$, there exists $$$1 \le t_i \le n$$$ such that (indices are taken modulo $$$m$$$, so that $$$v_{m + 1} = v_1$$$) $$$$$$ b_{v_i} - b_{v_{i + 1}} = \begin{cases} a_{t_i} & \text{if there is an edge } v_i \rightarrow v_{i + 1}, \\ -a_{t_i} & \text{if there is an edge } v_i \leftarrow v_{i + 1}. \end{cases} $$$$$$
Thus, there must be a nonempty subset $$$\{t_1, \, \dots, \, t_m\} \subseteq \{1, \, \dots, \, n\}$$$ and a choice of signs $$$s_1, \, \dots, \, s_m$$$ ($$$s_i \in \{+1, \, -1\}$$$) such that $$$$$$\tag{$\star$} s_1a_{t_1} + \cdots + s_ma_{t_m} = 0. $$$$$$
Let us show that this condition is also sufficient for the existence of a valid sequence $$$b_1, \, \dots, \, b_n$$$. Suppose there exist $$$m$$$, $$$t_1, \, \dots, \, t_m$$$ and $$$s_1, \, \dots, \, s_m$$$ so that $$$(\star)$$$ holds. We construct $$$b_1, \, \dots, \, b_n$$$ as follows. Set $$$b_{t_1} = 0$$$. Then, inductively, for each $$$1 \le i < m$$$ set $$$b_{t_{i + 1}} = b_{t_i} - s_ia_{t_i}$$$. Finally, for $$$i \not\in \{t_1, \, \dots, \, t_m\}$$$, set $$$b_i = a_i$$$. It is easy to check that this construction works.
The algorithm that iterates over all $$$3^n - 1$$$ choices of the subset and the signs (for each $$$i$$$ we decide whether $$$a_i$$$ is included in the subset and if it is included, whether its sign is positive or negative) and checks if for one of them $$$(\star)$$$ holds, is sufficient to solve the problem under the given constraints. 
Alternatively, one may treat the problem as a knapsack instance (the weights are $$$a_i$$$, but can be chosen with arbitrary sign, and we shall understand whether we can fill precisely a knapsack with $$$0$$$ capacity). With this approach, the complexity is $$$O(n^2\max|a_i|)$$$.
 Solve the problem with complexity $$$O(n3^{\frac{n}{2}})$$$.
 $$$O(n3^n)$$$.
**Implementation**
123771071

**E**
**Hints for Solution 1**
**Hint 1.**
It is always convenient to choose $$$a_i, \, b_i$$$ so that the color $$$i$$$ does not appear in $$$a_i + 1, \, a_i + 2, \, \dots, \, b_i - 1$$$. So, for each color there are $$$k - 1$$$ "candidate intervals".
**Hint 2.**
$$$(k - 1)\left\lceil \frac{n}{k - 1} \right\rceil \ge n$$$.
**Hint 3.**
Choose the intervals in chunks of $$$\left\lceil \frac{n}{k - 1} \right\rceil$$$. The intervals in the first chunk should be strictly to the left of the intervals in the second chunk, which should be strictly to the left of the intervals of the third chunk, and so on.
**Hint 4.**
For the $$$t$$$-th chunk, only consider (among the remaining colors) the candidate intervals whose left endpoint is the $$$t$$$-th occurrence of its color.
**Hints for Solution 2**
**Hint 1.**
Try to come up with a greedy algorithm.
**Hint 2.**
Order the candidate intervals (defined as above) by second endpoint.
**Hint 3.**
Scan the sorted intervals and always select one if you are allowed to.
**Solution**