Max Correct Set
Contest: Educational Codeforces Round 100 (Rated for Div. 2)
Difficulty rating: 3100
Tags: bitmasks, dp, math

Let's call the set of positive integers $$$S$$$ correct if the following two conditions are met:

- $$$S \subseteq \{1, 2, \dots, n\}$$$;
- if $$$a \in S$$$ and $$$b \in S$$$, then $$$|a-b| \neq x$$$ and $$$|a-b| \neq y$$$.

For the given values $$$n$$$, $$$x$$$, and $$$y$$$, you have to find the maximum size of the correct set.

Input format:
A single line contains three integers $$$n$$$, $$$x$$$ and $$$y$$$ ($$$1 \le n \le 10^9$$$; $$$1 \le x, y \le 22$$$).

Output format:
Print one integer — the maximum size of the correct set.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Example input:
10 2 5

Example output:
5

Example input:
21 4 6

Example output:
9

Editorial:
The key idea of the task is to prove that there is an optimal answer where the chosen elements in $$$S$$$ has a period equal to $$$p = x + y$$$. Let's work with $$$0, 1, \dots, n - 1$$$ instead of $$$1, 2, \dots, n$$$.
Firstly, let's prove that if we've chosen correct set $$$a_1, \dots, a_k$$$ in interval $$$[l, l + p)$$$ then if we take all $$$a_i + p$$$ then set $$$\{ a_1, \dots, a_k, a_1 + p, \dots a_k + p \}$$$ will be corect as well. By contradiction: suppose we have $$$a_i + p - a_j = x$$$ ($$$y$$$), then $$$a_i - a_j = x - p = x - x - y = -y$$$ ($$$-x$$$) or $$$|a_i - a_j| = y$$$ ($$$x$$$) — contradiction.
It means that if we take the correct set in interval $$$[l, l + p)$$$ we can create a periodic answer by copying this interval several times.
Next, let's prove that there is an optimal periodic answer. Let's look at any optimal answer and its indicator vector (binary vector of length $$$n$$$ where $$$id_i = 1$$$ iff $$$i$$$ is in the set). Let $$$r = n \bmod p$$$.
Let's split the vector in $$$2 \left\lfloor \frac{n}{p} \right\rfloor + 1$$$ intervals: $$$[0, r), [r, p), [p, p + r), [p + r, 2p), \dots, [n - r, n)$$$. The $$$1$$$-st, $$$3$$$-rd, $$$5$$$-th... segments have length $$$r$$$ and $$$2$$$-nd, $$$4$$$-th,... segments have length $$$p - r$$$. If we choose any two consecutive segments its total length will be equal to $$$p$$$ and we can use it to make periodic answer by replacing all length $$$r$$$ segments with the chosen one and $$$p - r$$$ segments with the other one.
We can prove that we can always find such two consecutive segments that the induced answer will be greater or equal to the initial one. If we create vector where $$$v_i$$$ is equal to the sum of $$$id_j$$$ in the $$$i$$$-th segment, then the task is equivalent to finding $$$v_i$$$ and $$$v_{i + 1}$$$ such that replacing all $$$v_{i \pm 2z}$$$ by $$$v_i$$$ and all $$$v_{i + 1 \pm 2z}$$$ by $$$v_{i + 1}$$$ won't decrease array $$$v$$$ sum. The proof is down below.
Now, since the answer is periodical, taking element $$$c$$$ ($$$0 \le c < p$$$) is equivalent to taking all elements $$$d \equiv c \bmod p$$$, so for each $$$c$$$ we can calc $$$val_c$$$ — the number of integers with the same remainder. And for each $$$c$$$ we either take it or not.
So we can write $$$dp[p][2^{\max(x, y)}]$$$, where $$$dp[i][msk]$$$ is the maximum sum if we processed $$$i$$$ elements and last $$$\max(x, y)$$$ elements are described by mask $$$msk$$$. We start with $$$dp[0][0]$$$ and, when look at the $$$i$$$-th element, either take it (if we can) or skip it.
Time complexity is $$$O((x + y) 2^{\max(x, y)})$$$.
==========
Let's prove that for any array $$$v_1, v_2, \dots, v_{2n + 1}$$$ we can find pair $$$v_p, v_{p + 1}$$$ such that replacing all $$$v_{p \pm 2z}$$$ with $$$v_p$$$ and all $$$v_{p + 1 \pm 2z}$$$ with $$$v_{p + 1}$$$ won't decrease the total sum.
Let's define $$$S_o = \sum\limits_{i = 1}^{n + 1}{v_{2i - 1}}$$$ and $$$S_e = \sum\limits_{i = 1}^{n}{v_{2i}}$$$. Let's make array $$$b_1, \dots, b_{2n + 1}$$$, where $$$b_{2i - 1} = (n + 1)v_{2i - 1} - S_o$$$ and $$$b_{2i} = n \cdot v_{2i} - S_e$$$. The meaning behind $$$b_i$$$ is how changes the total sum if we replace corresponding elements by $$$v_i$$$.
Note, that finding a good pair $$$v_p, v_{p + 1}$$$ is equivalent to finding $$$b_p + b_{p + 1} \ge 0$$$. Also, note that $$$\sum\limits_{i = 1}^{n + 1}{b_{2i - 1}} = (n + 1)S_o - (n + 1)S_o = 0$$$ and analogically, $$$\sum\limits_{i = 1}^{n}{b_{2i}} = n \cdot S_e - n \cdot S_e = 0$$$.
Let's prove by contradiction: suppose that for any $$$i$$$ $$$b_i + b_{i + 1} < 0$$$. Let's look at $$$\sum\limits_{i = 1}^{2n + 1}{b_i} = \sum\limits_{i = 1}^{n + 1}{b_{2i - 1}} + \sum\limits_{i = 1}^{n}{b_{2i}} = 0$$$. But from the other side, we know that $$$b_2 + b_3 < 0$$$, $$$b_4 + b_5 < 0$$$, ..., $$$b_{2n} + b_{2n + 1} < 0$$$, so $$$b_1 > 0$$$, otherwise $$$\sum\limits_{i = 1}^{2n + 1}{b_i}$$$ will be negative.
In the same way, since $$$b_1 + b_2 < 0$$$, $$$b_4 + b_5 < 0$$$, ..., $$$b_{2n} + b_{2n + 1} < 0$$$, then $$$b_3 > 0$$$. Analogically we can prove that each $$$b_{2i - 1} > 0$$$, but $$$\sum\limits_{i = 1}^{n + 1}{b_{2i - 1}} = 0$$$ — contradiction. So, there is always a pair $$$b_p + b_{p + 1} \ge 0$$$, i. e. a pair $$$v_p, v_{p + 1}$$$.