Snakes
Contest: Codeforces Round 995 (Div. 3)
Difficulty rating: 2100
Tags: bitmasks, dp, dsu, graphs

Suppose you play a game where the game field looks like a strip of $$$1 \times 10^9$$$ square cells, numbered from $$$1$$$ to $$$10^9$$$.

You have $$$n$$$ snakes (numbered from $$$1$$$ to $$$n$$$) you need to place into some cells. Initially, each snake occupies exactly one cell, and you can't place more than one snake into one cell. After that, the game starts.

The game lasts for $$$q$$$ seconds. There are two types of events that may happen each second:

- snake $$$s_i$$$ enlarges: if snake $$$s_i$$$ occupied cells $$$[l, r]$$$, it enlarges to a segment $$$[l, r + 1]$$$;
- snake $$$s_i$$$ shrinks: if snake $$$s_i$$$ occupied cells $$$[l, r]$$$, it shrinks to a segment $$$[l + 1, r]$$$.

Each second, exactly one of the events happens.

If at any moment of time, any snake runs into some obstacle (either another snake or the end of the strip), you lose. Otherwise, you win with the score equal to the maximum cell occupied by any snake so far.

What is the minimum possible score you can achieve?

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n \le 20$$$; $$$1 \le q \le 2 \cdot 10^5$$$) — the number of snakes and the number of events. Next $$$q$$$ lines contain the description of events — one per line.

The $$$i$$$-th line contains

- either "$$$s_i$$$ +" ($$$1 \le s_i \le n$$$) meaning that the $$$s_i$$$-th snake enlarges
- or "$$$s_i$$$ -" ($$$1 \le s_i \le n$$$) meaning that the $$$s_i$$$-th snake shrinks.

Additional constraint on the input: the given sequence of events is valid, i. e. a snake of length $$$1$$$ never shrinks.

Output format:
Print one integer — the minimum possible score.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first test, the optimal strategy is to place the second snake at cell $$$1$$$, the third snake — at $$$2$$$, and the first one — at $$$3$$$. The maximum occupied cell is cell $$$4$$$, and it's the minimum possible score.

In the second test, one of the optimal strategies is to place:

- snake $$$2$$$ at position $$$1$$$;
- snake $$$3$$$ at position $$$4$$$;
- snake $$$5$$$ at position $$$6$$$;
- snake $$$1$$$ at position $$$9$$$;
- snake $$$4$$$ at position $$$10$$$.

Example input:
3 6
1 +
1 -
3 +
3 -
2 +
2 -

Example output:
4

Example input:
5 13
5 +
3 +
5 -
2 +
4 +
3 +
5 +
5 -
2 +
3 -
3 +
3 -
2 +

Example output:
11

Editorial:
Note that when you place snakes on the strip in some order, they form some permutation. And when you fix that permutation, you can place them greedily.
In other words, when you know in what order you'll place snakes, it's always optimal to place them as close to each other as possible. Since the bigger the initial distance — the bigger the resulting distance of the farthest snake (or the bigger the final score). We can even calculate that final score precisely: it's equal to $$$1 + \texttt{sum of distances} + \texttt{number of times the last snake enlarges}$$$.
So, we can solve the task in two steps. First, let's calculate $$$\mathrm{minDist}[i][j]$$$ — the minimum possible distance between snakes $$$i$$$ and $$$j$$$ if we plan to place snake $$$j$$$ right after snake $$$i$$$. Suppose the initial gap between these snakes is $$$x$$$. Let's skim through all events:
• each time the $$$i$$$-th snake enlarges, our gap decreases, or $$$x' = x - 1$$$.
• each time the $$$j$$$-th snake shrinks, our gap increases, or $$$x' = x + 1$$$.
• if at any moment $$$x'$$$ becomes negative, then we lose. In other words, we needed bigger initial $$$x$$$.
We can rephrase what happens more formally: for each event $$$i$$$ let $$$e_i = 1$$$ if $$$x$$$ increases, $$$e_i = -1$$$ if $$$x$$$ decreases or $$$0$$$ otherwise. Then after the $$$i$$$-th event the current gap will be equal to $$$x' = x + \sum_{j=1}^{i}{e_j}$$$.
The following inequality should hold for each $$$i$$$: $$$x + \sum_{j=1}^{i}{e_j} \ge 0$$$ or $$$x \ge -\sum_{j=1}^{i}{e_j}$$$. So, if we will find the minimum $$$\min\limits_{1 \le i \le q}{\sum_{j=1}^{i}{e_j}}$$$ then we can set the initial distance to this minimum gap plus one, or $$$\mathrm{minDist}[i][j] = -\min\limits_{1 \le i \le q}{\sum_{j=1}^{i}{e_j}} + 1$$$.
Now we know the minimum distances between neighboring snakes, so we can find the optimal order. Let's do it with bitmask dp $$$d[mask][lst]$$$, since all we need to know in each state is the set of already placed snakes $$$mask$$$ and the last snake $$$lst$$$. Transitions are straightforward: let's just choose the next snake to place and place it at distance $$$\mathrm{minDist}$$$.
The initial states are $$$d[2^i][i] = 1$$$ for each $$$i$$$. The answer is $$$\min\limits_{1 \le i \le n}{d[2^n - 1][i] + \texttt{number of times snake $$$i$$$ enlarges}}$$$, i. e. we just choose the last snake.
The time complexity is $$$O(n^2 q)$$$ for the first part (or $$$O(n q)$$$ if written more optimally) plus $$$O(2^n n^2)$$$ for the second part.