CHNGSEQ - Editorial

editorial
, , , , , ,
1

PROBLEM LINK

Practice
Contest

CONTEST PANEL

Author: Prateek Gupta
Tester: Praveen Dhinwa
Editorialist: Prateek Gupta

DIFFICULTY

Hard

PRE-REQUISITES

Math, Combinatorics, Bit Manipulation, Meet in the middle

PROBLEM

Given two integers N and B, you need to find the number of sequences of length N such that the beauty values of it’s subsequences is exactly B. (B is actually B modulo 10^9 + 7). Since, the number of such sequences can be fairly large, you have to calculate the answer modulo 10^9 + 7. Beauty of a subsequence is defined as the product of length of the subsequence and the XOR of the numbers contained in it.

EXPLANATION

The brute approach here is pretty much easy to visualize. For any given N, there will be (C - 1)^{N} such subsequences. But, we need to find out which of the have the sum of the beauty values of their subsequence as B (modulo 10^9 + 7). Fixing each such sequence, you calculate the sum of their beauty values of subsequence modulo 10^9 + 7. In case, it equals B, you increment your answer by 1. So, your complexity will be huge in this case. Something like O((C - 1)^{N} * X) where X is the complexity to calculate the sum of beauty values of all subsequence in a particular sequence. This actually leads us no where close to achieving the intended solution.

The other way to think in the problems involving Bitwise operations is to visualize everything in terms of binary. So, in case if you have some fixed sequence, how do you calculate the sum of the beauty values of it’s subsequences? Let us write down each number of the sequence in it’s binary representation. Since, each number will be lt; 2^{20}, we can represent each of them in 20 binary bits to maintain consistency.

Claim 1: We can actually calculate the beauty value for each bit individually and then finally sum up the beauty values of all 20 bits to get the final value.

After representing a given list of numbers in binary, their Bitwise XOR is calculated as the summation of the 2^{i^{th} bit} when the i^{th} column has odd number of ones. What actually matters is the odd number of ones in the column. So, for a particular column which will have some N binary bits, we can calculate the sum of the beauty values of the subsequences just for that column.

Let n = number of ones and m = number of zeros in any particular column such that n + m = N

The column k will contribute value 2^{k} only when it has odd number of ones irrespective of any number of zeros contained in it. Having said that, let us select a subsequence of (2i + 1) ones from the total number of ones and j zeros from the total number of zeros in the k^{th} column. Number of ways to select (2*i + 1) ones from n ones will be \binom{n}{2i+1} and similarly \binom{m}{j} will be the number of ways to select j zeros from m zeros. In this case, total length of the subsequence will be (2*i + j + 1) and the XOR value will obviously be 2^{k}. Here, (2i + 1) ≤ n which means i ≤ (n - 1)/2. Let p = (n - 1)/2 so that i ≤ p

With this, the sum of the beauty values contributed by all subsequence in k^{th} column becomes…

2^{k}* [\sum_{i=0}^{p} \sum_{j=0}^{m}(2i + j + 1) \cdot \binom{n}{2i + 1} \cdot \binom{m}{j}]

Breaking this into two separate parts,

\implies 2^{k}* [\sum_{i=0}^{p} \sum_{j=0}^{m}(2i + 1) \cdot \binom{n}{2i + 1} \cdot \binom{m}{j} +\ \sum_{i=0}^{p} \sum_{j=0}^{m}(j) \cdot \binom{n}{2i + 1} \cdot \binom{m}{j}]
\implies 2^{k}* [\sum_{i=0}^{p} (2i + 1) \cdot \binom{n}{2i + 1} \cdot (2^{m}) +\ \sum_{i=0}^{p} \binom{n}{2i + 1} \cdot (m) \cdot (2^{m-1})]
\implies 2^{k}* [(n) \cdot 2^{n - 2} \cdot (2^{m}) +\ 2^{n-1} \cdot (m) \cdot (2^{m-1})]

If you observe carefully, (n) \cdot 2^{n - 2} becomes undefined when n ≤ 1. So, in case n > 1, the above equation can be simplified further as solved below.

2^{k}* [n \cdot 2^{n + m - 2} +\ m \cdot 2^{n + m - 2}]
2^{k}* 2^{n + m - 2} \cdot (n + m)
2^{k + n + m - 2} \cdot (n + m)

Since, n + m = N, the equation is simplified to …

N \cdot 2^{k + N - 2}

Similarly, for the case when n = 1, the equation is simplified to …

(N + 1)*2^{N + M - 2}

Well, for the case when n = 0, which means the number of ones in the column will be 0, the value contributed will anyway be 0.

Let the value contributed by any bit column k to the sum of beauty of all subsequences be F(k)

F(k) = 0,\ if\ n\ =\ 0
F(k) = (N + 1)*2^{N + k - 2},\ if\ n\ =\ 1
F(k) = N * 2^{N + k - 2}, if\ n\ >\ 1

The sum of the beauty values contributed by all such columns for a particular sequence will be :-

\sum_{k = 0}^{19}F(k)

Each column can have only one of the three possible values.

  • When count of ones = $0$ then the number of such possible columns = $1$
  • When count of ones = $1$, then the number of such possible columns = $\binom{N}{1}$
  • When count of ones $> 1$, then the number of such possible columns = $2^{N} -1 - \binom{N}{1}$

The first thing that comes to our mind is recurring by keeping the function f(idx, beautyValue, sequences). Let us have a look at the pseudo code to understand it better. Let us denote the number of columns calculated above by type[i] where type[i] denotes the number of possible columns when there are i ones.

f(idx, beauty_val, sequences)
{
     if ( idx == 20 ) {
         if ( beauty_val == B ) return sequences;
         return 0;
     }
     ans = 0
     // Number of ones are zero
     ans += f(idx + 1, beauty_val, sequences)
     //Number of ones are 1
     ans += f(idx + 1, (beauty_val + F(idx))%MOD, sequences * type[1])
    //Number of ones are > 1
     ans += f(idx + 1, (beauty_val + F(idx))%MOD, sequences * type[2])
     return ans
}

We are very close to the actual solution now. But, the above implementation still means the complexity of order O(3^{20}).
How can we improvise? Can we apply meet in the middle technique? Yes. That is it. You can divide the columns into two parts.
So, let us say Map(0, B1) will store the number of sequences having sum of beauty values of subsequences for first 10 columns i.e [0.. 9] as B1. Similarly, Map(0, B2) will store the number of sequences having sum of beauty values of subsequences for last 10 columns i.e [10 ... 19]. Now, you can iterate over all distinct beauty values in Map(0) and find the counter beauty values in Map(1) such that beauty values in both sum up to B modulo MOD.

The overall complexity is now reduced to O(3^{10} *log(3^{10}))

For more details on the implementation, have a look at the setter or tester’s solution.

Note

Please notd that above calculations might be done without considering MOD = 10^9 + 7. Please do not forget to consider MOD while actually implementing the above approach.

SOLUTIONS

Author’s solution can be found here.
Tester’s solution can be found here.

1 Like