Given n students that are connected by edges. We have to find the maxiumum number of answers that can be passed.
An answer is said to be passed if it reaches every student.
There are 3 constraints:-
- You can give only one answer to a particular student.
- Student who recieved the answer directly from you, can share it with thier immediate neigbours.
- Student who recvied the answer indirectly (not from you) cannot share it with anyone.
So we have to find the maxiumum number of answer that can be passed.
for example:
n = 3
1 — 2
2 — 3
ans1 can be given to student no 2, so he can pass it to student 1 and 3.
ans2 can be given to student 1 and 3 so they can pass it to student 3.
In both of the cases answer reaches all the students and you haven't given more than one answer directly to any student.
So the answer will be 2
Constraints:
n <=15
The easy solution is to try every possible combination of the "on" and "off" vertices, that is, whether we pass an answer to a certain vertex ("on" vertex), or no("off" vertex).
After doing that we are left with a list of all possible bitmasks, which result in a correct "turning on" of an entire graph. Now we just need to find the longest such subset of these masks, where $$$m_i \text{ & } m_j = 0$$$, for all $$$i \neq j$$$ in this subset. You can easily do this using a dp, where $$$dp[a] = max(dp[a \oplus m_i])$$$, where a is any bitmask of size n, and $$$a \text{ & } m_i = m_i$$$. The answer is the maximum value in the dp.
This solution is $$$O(n \times 2^n)$$$, which is good enough for $$$n \le 15$$$
isn't dp part will take O(
n*2^n)Yup you're right. Fixing the mistake right now
Could you please explain why $$$dp[a] = max(a \oplus m_i) + 1$$$? Shouldn't it be $$$dp[a] = max(dp[a \oplus m_i]) + 1$$$? And if so, how to calculate it quickly, because we have $$$2^{15}$$$ possible $$$m_i$$$ values? So far I only understand how to do it in $$$O(2^{2n})$$$. Edit: now I see, we can use trie to discard $$$m_i$$$ which are not submasks of dp index, this will reduce complexity.
Yea you're right that's another mistake I made, it should be $$$dp[a] = max(dp[a \oplus m_i])$$$
It looks like I was tired yesterday and I thought that it was enough, but it is not. After thinking for a minute on how to make the solution work I came up with this solution: What you can do is to generate all possible masks that can be achieved within $$$a$$$. That is if a is 101, then we only check the masks 100, 101, 001. Generating these "matching" masks is 2 ^ (numer of ones in certain mask). It might seem to be too slow at first glance, but if we can prove, that on average only $$$\frac{1}{2}$$$ of a bitmask is ones, and the rest is zeros. This observation makes our solution work in $$$O(2^{\frac{3n}{2}} \times n)$$$, which with the bound $$$n \lt 15$$$, can be approximated from the top by $$$2^{26}$$$ ($$$15$$$ + ceil($$$7.5$$$) + $$$2^4$$$ for the 15). This is less than 100 milion, which should work in well below a second.
Yeah, I just thought about this before I saw this comment, so we can use trie to filter $$$m_i$$$ (as I edited previous comment), or just iterate submasks directly (because in worst case it is the same, even without log factor).
I think this is a standard Grouping problem with bitmask.
Explaination : I am representing the available student whom i can tell answer directly using set bits on mask. For a given mask i am generating all its submask and trying to figure out if this could be a perfect group, means if i tell answer to student present in this group, can it reach to all the students. And then recusrively solving the problem by removing the submask from orignal mask.
Similar Idea in Atcoder Dp Contest: Problem Link