deepkamal's blog

Help with problem involving bitmasking and SOS dp .
By deepkamal, history, 4 years ago, In English

I was solving this problem https://www.codechef.com/problems/COVERING and sort of came with a subproblem which I am not sure if it helps to solve the original problem but seems very interesting anyways.

Given an array A and array B with size (2^N) . Compute another array X of size (2^N) such that

X[mask] = sum of (A[i] * B[j]) such that ( (i&j) == mask ) .

How can one solve this for N <= 20 .

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by deepkamal (previous revision, new revision, compare).

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

Auto comment: topic has been updated by deepkamal (previous revision, new revision, compare).

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

Auto comment: topic has been updated by deepkamal (previous revision, new revision, compare).

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

Auto comment: topic has been updated by deepkamal (previous revision, new revision, compare).

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

Auto comment: topic has been updated by deepkamal (previous revision, new revision, compare).

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

This is a pretty standard fast Walsh-Hadamard transform problem.

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

    Seems out of my league but thanks for the reply, idk why it got downvoted I felt it was fairly interesting problem .

    → Reply