FifthThread's blog

Google Online Assesment Question
By FifthThread, history, 3 years ago, In English

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?

  • Vote: I like it
  • +12
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
3 years ago, # |
← Rev. 4   Vote: I like it +4 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 4   Vote: I like it +2 Vote: I do not like it

      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.

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain the bitmasking solution ?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

The constraint in the problem was 2*K >= N.

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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))

dp(0,0) will be answer
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope my solution is correct . Can anyone verify ?

Thanks in advance

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

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)$$$

→ Reply