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 .
Auto comment: topic has been updated by deepkamal (previous revision, new revision, compare).
Auto comment: topic has been updated by deepkamal (previous revision, new revision, compare).
Auto comment: topic has been updated by deepkamal (previous revision, new revision, compare).
Auto comment: topic has been updated by deepkamal (previous revision, new revision, compare).
Auto comment: topic has been updated by deepkamal (previous revision, new revision, compare).
This is a pretty standard fast Walsh-Hadamard transform problem.
Seems out of my league but thanks for the reply, idk why it got downvoted I felt it was fairly interesting problem .