TanVir17's blog

By TanVir17, history, 14 months ago, In English

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?

Tags dp
  • Vote: I like it
  • +1
  • Vote: I do not like it

| Write comment?
»
14 months ago, # |
Rev. 5   Vote: I like it +25 Vote: I do not like it

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 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Skill Issue

»
14 months ago, # |
  Vote: I like it +18 Vote: I do not like it

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.