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

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

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 .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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