Блог пользователя FifthThread

Автор FifthThread, история, 3 года назад, По-английски

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?

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 4   Проголосовать: нравится +4 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 4   Проголосовать: нравится +2 Проголосовать: не нравится

      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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you explain the bitmasking solution ?

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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)

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

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.

»
3 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I hope my solution is correct . Can anyone verify ?

Thanks in advance

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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