Double Elimination
Contest: VK Cup 2019-2020 - Elimination Round (Engine)
Difficulty rating: 2500
Tags: dp, implementation

The biggest event of the year – Cota 2 world championship "The Innernational" is right around the corner. $$$2^n$$$ teams will compete in a double-elimination format (please, carefully read problem statement even if you know what is it) to identify the champion.

Teams are numbered from $$$1$$$ to $$$2^n$$$ and will play games one-on-one. All teams start in the upper bracket.

All upper bracket matches will be held played between teams that haven't lost any games yet. Teams are split into games by team numbers. Game winner advances in the next round of upper bracket, losers drop into the lower bracket.

Lower bracket starts with $$$2^{n-1}$$$ teams that lost the first upper bracket game. Each lower bracket round consists of two games. In the first game of a round $$$2^k$$$ teams play a game with each other (teams are split into games by team numbers). $$$2^{k-1}$$$ loosing teams are eliminated from the championship, $$$2^{k-1}$$$ winning teams are playing $$$2^{k-1}$$$ teams that got eliminated in this round of upper bracket (again, teams are split into games by team numbers). As a result of each round both upper and lower bracket have $$$2^{k-1}$$$ teams remaining. See example notes for better understanding.

Single remaining team of upper bracket plays with single remaining team of lower bracket in grand-finals to identify championship winner.

You are a fan of teams with numbers $$$a_1, a_2, ..., a_k$$$. You want the championship to have as many games with your favourite teams as possible. Luckily, you can affect results of every championship game the way you want. What's maximal possible number of championship games that include teams you're fan of?

Input format:
First input line has two integers $$$n, k$$$ — $$$2^n$$$ teams are competing in the championship. You are a fan of $$$k$$$ teams ($$$2 \le n \le 17; 0 \le k \le 2^n$$$).

Second input line has $$$k$$$ distinct integers $$$a_1, \ldots, a_k$$$ — numbers of teams you're a fan of ($$$1 \le a_i \le 2^n$$$).

Output format:
Output single integer — maximal possible number of championship games that include teams you're fan of.

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

Note:
On the image, each game of the championship is denoted with an English letter ($$$a$$$ to $$$n$$$). Winner of game $$$i$$$ is denoted as $$$Wi$$$, loser is denoted as $$$Li$$$. Teams you're a fan of are highlighted with red background.

In the first example, team $$$6$$$ will play in 6 games if it looses the first upper bracket game (game $$$c$$$) and wins all lower bracket games (games $$$h, j, l, m$$$).

In the second example, teams $$$7$$$ and $$$8$$$ have to play with each other in the first game of upper bracket (game $$$d$$$). Team $$$8$$$ can win all remaining games in upper bracket, when teams $$$1$$$ and $$$7$$$ will compete in the lower bracket.

In the third example, your favourite teams can play in all games of the championship.

Example input:
3 1
6

Example output:
6

Example input:
3 3
1 7 8

Example output:
11

Editorial:
The main observation in this problem is that for each set of players that lie in the subtree of any vertex of a binary tree of the upper bracket, exactly one player will win all matches in the upper bracket, and exactly one player will win all matches in the lower bracket. We can define this set of players (in 0-indexation instead of 1-indexation from statement) as $$$[a \cdot 2^t; (a+1) \cdot 2^t)$$$ for some $$$1 \le t \le n$$$, $$$0 \le a < {{2^n} \over {2^t}}$$$. For each fixed $$$t$$$ the players with different values of $$${id \over {2^t}}$$$ don't play with each other, and their upper and lower brackets are independent.
For each of these sets of players, we are interested only in a number of interesting matches between them, and if the winner of their upper and lower brackets are the teams that are we're fans of. This leads us to the dynamic programming solution:
$$$dp[l \ldots r][f_{up}][f_{lower}]$$$ — the maximal number of matches between teams with indices in $$$[l; r)$$$, if $$$f_{up} \in \{ 0, 1 \}$$$ is 1 if the we're fans of winner of upper bracket, and $$$f_{lower} \in \{ 0, 1 \}$$$ is 1 if the we're fans of winner of lower bracket. Again, $$$l \ldots r$$$ is the special segment: $$$l = a \cdot 2^t, r =(a+1) \cdot 2^t - 1$$$ for some $$$1 \le t \le n$$$, $$$0 \le a < {{2^n} \over {2^t}}$$$.
$$$dp[l \ldots r][f_{up}][f_{lower}]$$$ can be recalculated from $$$dp[l \ldots {{l+r} \over 2}][f_{up}^l][f_{lower}^l]$$$ and $$$dp[{{l+r} \over 2} \ldots r][f_{up}^r][f_{lower}^r]$$$ — we just iterate over all possible $$$f_{up}^l, f_{lower}^l, f_{up}^r, f_{lower}^r$$$, and the results of all three matches (one in the upper bracket and two in the lower bracket).
In the end, we use $$$dp[0 \ldots 2^n][f_{up}][f_{lower}]$$$ to count the result with the last, grand-finals match.
This solution works in something like $$$\mathcal{O}(2^n \cdot 2^7)$$$ because there are $$$2^n$$$ interesting segments.