You are given an array A of N non negative integers. There are K empty slots from 1 to K. You have to arrange these N numbers into K slots( 2*K> =N). Each slot can contain at most two numbers filled into it. After all the integers have been placed into these slots, find the sum of bitwise AND of all the numbers with their respective slot numbers
Task: Determine the maximum possible sum
Note: Some slots may remain empty
Example A = [1,3,10,20,7,1] N = 5 K = 10 answer = 25
I did brute force and some test case passed.
How to do this question?
Lets make bipartite graph where we have N nodes on one side and 2*K nodes on other side here , and make edges between all nodes from left to all right, now you can apply maximal bipartite matching with max total weight(Hungarian algorithm). Here edge weight denotes bitwise AND value of connected node.
You can also apply dp bitmask to not getting into complex implementation just that dp bitmasking will be exponential in complexity while above can be solved in polynomial time.
if possible could you suggest some resources or problems which use this?
EDIT1 — Thank you my guy:)
EDIT2 -> ahh, a reminding lesson that I should upsolve, the problem you gave has a WA submission by me 3 weeks ago.
I guess there is one classic question on leetcode with maximum bitwise xor sum between pairs so you can search that, question is classic but appeared on lc contest two or three months ago I guess.
Link to question
Also on cses there is one question named as task assignment which is classic Hungarian.
In the dp in bitmask soln you're suggesting, it'll be N*K*(3^K) right?
https://ideone.com/hJ2KS3 I tried to implement it like this, keeping a mask for K slots(with each digit being 0/1/2). This was O(N*K*(3^K)), I couldn't understand how to remove that O(K) complexity per state. Any ideas?
Can you explain the bitmasking solution ?
Simply append 2*K — N zeros in the array, and the question will get converted to leetcode xor question, you can refer solution of that.complexity will 2*K *2^(2K)
The constraint in the problem was 2*K >= N.
Take an array avail and for i=1 to i=K avail[i]=2 Now start recursion, for index i=0 to i=N-1. Put A[i] to any index from j=1 to j=K if avail[j]>0 and similarly recurse for the next state by reducing avail by 1. So a state is given by a vector i.e., vector avail and push index to it. So you can store the maximum value of a state in a map<vector,int>m so as to prevent repeated calculation.
We can use a simple bitmasking dp, where dp(start,mask) will give the maximum sum, when all elements before start are used and bits which are '0' in mask are currently available.
Time complexity: O(N*2K*2^(2K))
But how to you maintain that how many elements are filled in the slot. At most 2 elements can be filled in a slot and I think you code handles only 1 element in a slot
We can use any slot atmost one time, so the available slots are [1,1,2,2,………,K,K], and i have made masks for 2k bits, so all slots are handled.
I hope my solution is correct . Can anyone verify ?
Thanks in advance
This problem came in my test too, I used normal dp bitmask, with a catch! I used $$$3$$$-base system to represent my mask (instead of usual $$$2$$$ base system). $$$dp[mask]$$$ denotes the max value, such that the $$$i^{th}$$$ bit in the mask denotes no. of integers filled in $$$i^{th}$$$ slot (It can be $$$0,1,2$$$). $$$dp[0]=0$$$.
Time complexity: $$$O(K*3^K)$$$