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

Автор vamaddur, история, 7 лет назад, По-английски

Given a positive integer N, calculate the sum of inversions in every bitmask of length N.

For example, if N = 2, our masks are 00 (0 inversions), 01 (0 inversions), 10 (1 inversion), and 11 (0 inversions). We output 1.

For example, if N = 3, our masks are 000 (0 inversions), 001 (0 inversions), 010 (1 inversion), 011 (0 inversions), 100 (2 inversions), 101 (1 inversion), 110 (2 inversions), and 111 (0 inversions). We output 0+0+1+0+2+1+2+0 = 6.

How can I do this efficiently?

Please help, and thanks in advance!

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

»
7 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится
  1. Brute force solution
    You can solve it with brute force. There are 2N ways to express N bits. And you can calculate the number of inversions of N bits binary integer in O(N2). Just count the number of pair that a[i] = 1 and a[j] = 0 (i < j). So the complexity is O(2NN2).

  2. Let's think about average inversions.
    The answer will be (average inversions) * (The number of ways).
    For each pair (i,  j) (i < j), if a[i] = 1 and a[j] = 0, there is an inversion in pair (i,  j). So the probability is 0.52 = 0.25. There are N(N - 1) / 2 pairs, so the average value is N(N - 1) / 8.
    So the answer is 2N*N(N - 1) / 8.
»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +32 Проголосовать: не нравится

For each pair of indexes i < j let's calculate how many masks of length N have an inversion in this pair. It's quite easy: maski should be 1, maskj should be 0 and every other bit (there are N - 2 such bits) can be either 0 or 1. So there are 2N - 2 such masks (with an inversion on positions i, j). So each pair i < j increases the answer by 2N - 2. There are such pairs, so the total answer is