PROBLEM LINK:
Author: Vitaliy Herasymiv
Tester: Istvan Nagy
Editorialist: Amit Pandey
DIFFICULTY:
Medium.
PREREQUISITES:
Dynamic Programming
PROBLEM:
Given a set of integers \{0, 1, 2, ..., n\}, find the number of ways of choosing a subset of k integers such that the xor of all chosen integers has exactly B set bits(in the binary representation).
EXPLANATION:
In this problem, our approach will be to generate(smartly) all possible k integers bit by bit from MSB in a particular order. At any step i we will assume that we have generated k integers upto ith bit following a order and extend it to i+1th bit( taking care of the ordering as well) and in the process, counting all possible ways of extension of k integer. Now to smartly count all the ways we will use dynamic programming approach.
Define a 3-D dp matrix \text{dp[i][b][mask]} which stores the number of ways of choosing k integers of i bits such that their xor has b set bits and the k integers follow a specific order according to the mask. Important idea to note here is that the k integers chosen follow a specific order defined by mask as follows :-
0th bit of mask is 1/0 iff 1st chosen integer is strictly less/equal than n upto i bits from MSB.
1st bit of mask is 1/0 iff 2nd chosen integer is strictly less/equal than 1st chosen integer upto i bits from MSB.
2nd bit of mask is 1/0 iff 3rd chosen integer is strictly less/equal than 2nd chosen integer upto i bits from MSB.
.
.
.
k-1 th bit of mask is 1/0 iff kth chosen integer is strictly less/equal than k-1 th chosen integer upto i bits from MSB.
This means that the k integers are considered in decreasing order. Since the ordering doesn’t matter in set, there is no harm in generating k integer in decreasing order. Lets say the first i bits of k integers are already generated according to mask. Now these k integers can be extended to $i+1$th bit(from MSB) in 2^k - 1 ways, that is the value of pred( it is a k bit number such that j th bit of pred is $i+1$th bit of j th chosen number, refer to the figure below for more detail) can take 2^k - 1 value. And for each value of pred and old mask the ordering of k integer ( also the mask ) will change. Note that the newmask (which denotes the ordering among k chosen number) may be invalid because there may be some pair(s) of numbers which are not in decreasing order, in that case the newmask will be invalid. Now lets consider each possible scenario case by case.
First initalize newmask with mask. The first condition involves the number n and the 1st chosen number.
If 0th bit of mask is 0 which implies 1st number is equal to n upto i bits from MSB then
Case 1.1: If i+1th bit of n is 1 and i+1th bit of 1st number is 0 then 0th bit of newmask will be 1 as 1st number is now smaller than n.
Case 1.2: If i+1th bit of n is 1 and i+1th bit of 1st number is 1 then no change in newmask.
Case 1.3: If i+1th bit of n is 0 and i+1th bit of 1st number is 0 then no change in newmask.
Case 1.4: If i+1th bit of n is 0 and i+1th bit of 1st number is 1 then in this case newmask will be invalid.
The following condition involves j+1th and jth chosen number where j varies from 1 to k-1.
If jth bit of mask is 1 that means j+1th number is strictly smaller than jth number upto ith bit and even if i+1st bit is 0 or 1 this order will not change hence in this case newmask will not change.
Else If jth bit of mask is 0, this means j+1th number is equal to jth number and depending upon the i+1th bit of those two number newmask will change.
Case 2.1: If i+1th bit of jth number is 1 and j+1th bit of 1st number is 0 then jth bit of newmask will be 1 as j+1th number is now smaller than jth number.
Case 2.2: If i+1th bit of jth number is 1 and j+1th bit of 1st number is 1 then no change in newmask.
Case 2.3: If i+1th bit of jth number is 0 and j+1th bit of 1st number is 0 then no change in newmask.
Case 2.4: If i+1th bit of jth number is 0 and j+1th bit of 1st number is 1 then in this case newmask will be invalid.
After the computation of newmask and it validity update the dp state dp[i+1][b+setBits(pred)%2][newmask] += dp[i][b][mask] if newmask is valid. Base case will be dp[0][0][0] = 1. Below is basic structure of the code for more clarity.
for(i = 0 to 31) for(b = 0 to B) for(mask = 0 to 2^k - 1) :
for(pred = 0 to 2^k - 1) :
(newmask, validity) = generateNewMask(mask, pred);
//this function generates newmask according to the above rules
if(validity) dp[i+1][b+setBits(pred)%2][newmask] += dp[i][b][mask];
//setBits(x) return number of set bits in x
Now the final answer will be dp[31][B][2^k - 1] + dp[31][B][2^k - 2] corresponding to the case when 1st number is equal to n and when 1st number is strictly less than n. Refer to the tester’s code for more details. The time complexity of the algorithm is \mathcal{O}(B\log n2^k).
Solution:
Setter’s solution can be found here
Tester’s solution can be found here