https://codeforces.net/contest/1882/problem/B
I tried so many times for solving this problem using DP. But it seems impossible. Can anyone help me?
# | User | Rating |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 155 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | djm03178 | 152 |
https://codeforces.net/contest/1882/problem/B
I tried so many times for solving this problem using DP. But it seems impossible. Can anyone help me?
Name |
---|
There's a simple cubic-time solution: for each $$$x \in \bigcup_i S_i$$$ (i.e. each $$$x$$$ that occurs in at least one set), take the union of all sets that don't contain x. The answer is the size of the largest set you can create this way. If implemented in the obvious way, the time complexity is $$$\mathcal{O}\left(\left|\bigcup_i S_i\right| \cdot \sum_i \left| S_i\right|\right) = \mathcal{O}\left(n m^2\right)$$$, where $$$m$$$ is the maximum size of any input set.
I don't think it improves clarity in any way, but you can technically recast this algorithm in DP terms. Let $$$dp\left(i, x, y\right)$$$ be a Boolean value which is true iff one of the first $$$i$$$ input sets contains $$$y$$$ but not $$$x$$$. Then, $$$dp\left(0, x, y\right) = \text{False}$$$ and $$$dp\left(i + 1, x, y\right) = dp\left(i, x, y\right) \lor \left(x \not\in S_{i + 1} \land y \in S_{i + 1}\right)$$$.
Then, the answer is just the maximum number for any $$$x$$$ of $$$y$$$ values such that $$$dp\left(n, x, y\right)$$$ is true:
That said, I don't understand the point of trying to force this into being a "DP problem". The best technique to use is the simplest one that works, and thinking about this problem in DP terms doesn't seem to be the simplest way to approach it.
The trivial DP of trying all combinations of the said 50 sets will be too slow: O(2^50)
Skill Issue
I hope there is no need to solve a problem in a hard way like using DP. When you can solve this type of problem in an easy way. But trying problem in a new way is such a good thing for progress.