Suppose there are n animals from 1 to n+1 kinds and you are given m pairs of animals such that they can't put in the same pair of cages as they are hostile towards each other.
Suppose n = 4 and m = 2 and m pair are {1,3},{2,4} . So possible number of cages are 7 as {1},{2},{3},{4},{1,2},{1,4},{2,3}. sets such as {1,3},{2,4},{1,2,3,4} are not possible as 1,3 are hostile and 2,4 are hostile so they can't be put together in same cage or set. So you need to tell the number of cages that are possible
Can someone help me to solve this question?
You can do it with inclusion-exclusion principle in O(2 ^ M * N), by storing for each mask of pairs the set of animals which you have to have with bitset so you have a good constant
What kind of country is asking you these questions just to get a visa?
Berland
I think he meant VISA company.
I solved this question using Priority Queue PQ. Construct an adjacency list that stores all the kinds of animals that have their kind greater than that animal kind and have clash with that animal. E.g:- If there is a clash between animals 3 and 5, then store 5 in the list of 3 but NOT 3 in the list of 5. Then, maintain a Priority Queue and add n in it.
Now start iterating from the last index(i.e. n — 1) and if adj[i].size() == 0(i.e no enemy) then add PQ.pop (minimum element from Priority Queue) to ans , else if adj[i].size() != 0, then find the kind of enemy with the smallest number (lets say its k) that has clash with it. Now add min(k, PQ.pop()) to ans and add k to PQ. Hope this helps.
Can you tell me in priority_queue what are you storing and how do you get that idea as not to store 3 in the list of 5 as suppose in example 4 is ad[4].size is 0 so ans added will be 4 then again in 3 priority_queue is empty right?
Sorry, I forgot to mention that even when the adj[i].size() == 0 & you extract the min from the PQ, add the extracted number back to the PQ.
So again when the adj[3].size() is 0 so again then the answer would become 8 right ? Isn't that wrong.
Let n = 4. Clash is between animals no. 3 and 4. This is the adjacency list after processing:
1-> NULL 2-> NULL 3-> 4 4-> NULL
PQ stores 5 initially(coz now its 1 indexed). ans = 0;
Now, i = 4, min = PQ.pop() = 5. Thus, ans += (5 — 4) = 1. Put 5 back in PQ. i = 3, k = 4, min = Math.min(PQ.pop(), k) = 4. Thus, ans += (4 — 3). ans is 2. Put 5 and k both back in PQ. i = 2, min = PQ.pop() = 4. Thus, ans becomes 2 + 2 = 4. Put back 5 in PQ. i = 1, min = PQ.pop() = 4. Thus, final ans becomes 4 + 3 = 7.
This seems wrong. Consider this case:
If no animals are hostile to each other then the answer is 2^n — 1, which is exponential in terms of N. Your algorithm only uses addition, hence it wont work in most cases.
Also this problem can be reduced to finding the number of subgraphs which are cliques in a graph, which is a NP problem.
The question here is not correctly specified by the author.