Блог пользователя TanVir17

Автор TanVir17, история, 14 месяцев назад, По-английски

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?

Теги dp
  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
14 месяцев назад, # |
Rev. 5   Проголосовать: нравится +25 Проголосовать: не нравится

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:

$$$max _x \left|\left\{y : dp\left( n, x, y \right)\right\}\right|$$$

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.

»
14 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

The trivial DP of trying all combinations of the said 50 sets will be too slow: O(2^50)

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Skill Issue

»
14 месяцев назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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.