Len's blog

Random problem.
By Len, history, 7 years ago, In English

Given array a of length 1 ≤ n ≤ 44, 0 ≤ ai ≤ 244. Calculate di = number of subsets that their xor has i '1' bits.
I think this is a meet-in-the-middle problem but I couldn't solve it, so I need help.

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

»
7 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

The set of ai generates a vector space. Let D be the dimension of this space.

  • There are 2D elements in this vector space. Brute force works in O(2D * poly(N)).

  • There is a system of N - D equations that defines this space. Bitmask DP works in O(2N - D * poly(N)).

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

    The same solution/approach from a bit different perspective (I think it's different enough to describe it):

    Imagine a grid with 0's and 1's, where the i-th row contains ai. Run Gauss Elimination, to get 1's in say first D cells of the main diagonal, and only 0's above and below those 1's. Also, only first D rows are non-zeros. (We can obtain that, but in Gauss we must swap rows and swap columns).

    Then run brute force if D is small, and otherwise run bitmask DP on last M-D columns, where the score of subset of taken rows should be equal to the numbers of 1's in the xor, increased by the number of rows taken, because each taken row has one 1 on the left, in forgotten main diagonal.

    btw. I think all blogs like this one should give the source of a problem, so others could implement and submit a solution, and to fight (a bit) with cheating and asking about problems from ongoing contests.

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

      Could you please explain why brute force for the first D rows is sufficient?

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

        Other rows contain 0's only. It means that now we want to know the answer for the initial problem with some new values ai (each corresponding to one row) and only first D of them are non-zero — we can check all subsets of those.

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

          Does that mean for every mask among the 2^D elements we will have 2^(N-D) subsets corresponding to it.Please correct me if it is wrong.

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

            2D elements? Do you mean 2D achievable total xors? Then the answer is yes, but your strange question might mean you don't understand something. We are left e.g. with numbers {3, 8, 50, 100, 0, 0, 0}, so we say D = 4. For each of 2D subsets of first D elements, we get some xor, and there are 2N - D = 23 ways to choose which of 0's we always take in the subset.

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

              Thanks for clarification.But,even if D is large wouldn’t choosing i(query parameter) from D elements and multiplying it by 2^(N-D) give the answer within time limit?

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

                I don't understand what you mean with "choosing i from D elements". Do you want to iterate over all subsets of D elements (subsets with size i)? If not, what complexity do you have in your mind?

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

                  No,given that there are D independent non zero row vectors and di(query parameter) NCR(D,di)*pow(2,N-d) would give us number of ways to generate di 1’s.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 years ago, # ^ |
                    Vote: I like it +4 Vote: I do not like it

                  The number of taken numbers isn't equal to the number of 1's in the xor. For example, xor of 2 numbers 101011 and 110100 is 011111. There are 5 1's in the xor.

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

                  But the numbers after gaussian elimination will only have a single 1 and for each vector it should be at different bit position.Maybe I am missing something.

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

                  It isn't true. Let's say you start with two rows: 10111 and 01111. What matrix do you want to get?

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

UPD: I'm so so sorry guys I completely misunderstood the problem please don't take this answer in consideration.

I'm not sure if this is correct but maybe we can do something like this:

DP[pos][bit][ok] which denotes the number of subsets that don't have an element whose index is bigger than pos and that has the bitth bit equal to ok and your moves will be either

DP[pos + 1][bit][ok] or dp[pos + 1][bit][ok ^ bitth bit of a[pos]].

Now I know that this probably isn't a right solution I'm just trying to provide a perspective that someone might use to achieve a correct solution.

→ Reply