MIKE3 - Editorial

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

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

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

1 Like

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

@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.

Can anyone explain why my solution is wrong ?.I too used DFS.
http://www.codechef.com/viewsolution/3612467

I guess my solution worked in O(N*(M^2) + (2^M) * M) … Am I wrong in my Time Complexity Analysis?

Link: CodeChef: Practical coding for everyone

u have posted “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.”

plz correct me if i’m wrong, but i think the question asks to maximize the number of subsets in the chosen combination (not the sum of weights).

when nothing come into your mind apply broutforce as i did in this problem find all possible ways and got AC My solution is Here

1 Like

Can someone pls tell me what conflict and ID arrays are storing? Also what is mask variable doing?

i used a greedy strategy for this problem, pick that offer first which has minimum no. of conflicts and if there is a tie then select that offer which has less number of stamps in it. On submitting this gives wrong answer.
Can anyone plzz give a counter example. For reference this my


[1].


  [1]: http://www.codechef.com/viewsolution/4176818

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

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

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

3 Likes

@betlista No, it won’t.

1 Like

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

1 Like

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

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


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)

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