MIKE3 - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Constantine Sokol
Tester: Mahbubul Hasan
Editorialist: Jingbo Shang

DIFFICULTY:

Easy

PREREQUISITES:

Search

PROBLEM:

Given N objects and M weighted subsets of them, find a combination of subsets, such that all objects are covered at most once and the sum of the weights are maximized.

Some test cases are added in the practice room.

EXPLANATION:

Although N is large, M is quite small such that 2^M is tolerant. Therefore, we first need to construct the conflicts between different subsets. Two subsets are called conflict if and only if they shares a common object. To get this conflicts table, on each object, we can restore the IDs of subsets who contain the object. And then, mark they are conflicted with each other. This step takes O(N * M^2). Moreover, we can reduce the time complexity using the binary expression as following.

conflict[li] = 0;

[/li] For i = 1 to N do
int mask = 0;
For ID in IDs[i] do
mask |= 1 << ID;
end
For ID in IDs[i] do
conflict[ID] |= mask;
end
end

where, conflict[i] >> j & 1 stands for whether the i-th and j-th subsets are conflicted with each other. This code needs only O(NM) time.

And then, a simple DFS search can be applied to find the maximum weighted valid choice, like following:

int DFS(int i, int mask, int sum)
    if (i == M) {
        return sum;
    }
    int ret = DFS(i + 1, mask, sum); // don't select the i-th subset
    if (mask >> i & 1) {
        // conflicted, can't be chosen.
    } else {
        // try to select the i-th subset
        ret = max( ret, DFS(i + 1, mask | conflict[i], sum + weight[i]);
    }
    return ret;
end

This procedure takes O(2^M) time. Therefore, the overall time complexity is O(NM+2^M).

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

2 Likes
2

I formed a graph in O(N*M2) and then considering one offer as accepted found the maximum clique in its subgraph in O(M4). I have tried to explain my approach here

4 Likes
3

Shouldn’t the overall complexity be O(NM^2 + 2^M) ?

4

O(N * M^2) would lead to TLE, for N = 20.000 and M = 20…

5

I did the same, instead of finding maximum clique, I found maximum independent set.

3 Likes
6

by NM^2 i mean N*(M^2)

1 Like
7

@betlista No, it won’t.

1 Like
8

sorry, I missed 2^M and M^2 difference O:-) …

9

How can you say that your complexity is O(M^4)?.

10 

for(every node in graph) //O(M*O(clique()))
{
  clique()      //O(M<sup>3</sup>)
}
clique()
{
  while( a node exists in sub-graph)
   {
     for(every node in subgraph)
     {
       for( evry node its connected to)
       {
       }
     }
   }
}

Hence overall complexity is O(M4)

11

As the problem is NP complete and you are giving a polynomial time solution of this problem. You have managed to prove P = NP :stuck_out_tongue:

7 Likes
12

No, the hack here was that the original problem required all the 2^M combinations. But for this problem we will always form a subgraph such that we can solve it in M^4.

13

cant we use dp here ?
If we able to encode a set into binary number(hence decimal number ) .

1 Like
14

can this problem solved by using sorting with respect to size of each subset ? pls reply
my code is

15

Using the binary representation, we can do it in O(NM) rather than O(NM^2).

16

Oh yes, I got it !!!

17

I highly doubt your O(M^4) for a NP complete problem :slight_smile:
Created a dependency graph for all the offers. This graph has atmost 20 nodes. then calculated the maximum independent set using max cliques. Complexity is around NM^2 + 1.3^M

18

On getting AC even I thought of weak test cases but couldn’t find a test case in which this approach fails. It would be great if you could tell one :slight_smile:
The main reason behind it getting AC was the property of subgraph, it contains a permanent node such that every other node in the subgraph is connected to it. In the removal process I never touch this permanent node. So when I remove a node from subgraph it doesn’t affect the graph in the same way as it does for the Clique Problem

19

yes , we can solve it using it dp . We can solve it by initially getting the maximum number of non overalapping sets . Then we can use binary number to generate sets like 1100 means i took offer 1,offer 2 and rejected offer 3 and 4 . I solved it this way because i dont know much about graph
http://www.codechef.com/viewsolution/3539147

20

@shangjingbo :diamonds::diamonds:
can you please tell me how DFS is implemented here. Can you provide any good link to read this.
How to see nodes and edge’s.
Thank you.
PS : i followed author’s solution.