Given 3 integers N, P and X, you have to determine if a sequence [S1, S2, …., SN] can be constructed such that any pair of the sequence satisfying the constraint Si XOR Sj = X are exactly P in number.
- (1 <= i =< j <= N)
- 1 <= N, P, X <= 2 * 1e4
Example :
Input : N = 4, P = 3 , X = 3 Output : Possible Explanation : A possible sequence S = [2,2,1,2] satisfies the given condition, as there are exactly P = 3 pairs (i,j) such that Si ⊕ Sj = 3 = X. Input : N = 10, P = 8 , X = 2 Output : Possible Explanation : A possible sequence S = [8,12,3,14,8,15,10,10,8,14] satisfies the given condition, as there are exactly P = 8 pairs with XOR equal to X = 2. Input : N = 19, P = 100 , X = 34 Output : Impossible Explanation : No such sequence is possible satisfying the constraint
Approach :
- The first observation is that we do not need to explicitly find the sequence. We just have to say whether such a sequence is possible or not.
- Note that if any two numbers say A ⊕ B = X, there can be many such pairs (A,B) that give the xor = X. We can simply change appropriate bits and get their xor to be equal to X
- If we find a suitable sequence of length L < N, then we can easily append some dummy Large Numbers > 2*1e4 in that sequence to make the length to be N while still satisfying all the conditions. This is because the max value of Xor we need is limited by 2* 1e4.
- SO we will focus on finding the minimum length of the sequence S.
Construction of the sequence :
- Consider two integers a and b such that a XOR b = X, where frequency of occurrence of a is f1 and that of b is f2. If simply we have f1 * f2 = P, then we can say that we have got a valid sequence.
S = [aaaaaaa........., bbbbbb........]
<---f1---------> <----f2----->
In this sequence S, no of pairs having xor X = f1C1 * f2C1 = f1 * f2 = P. Note, all same pairs a XOR a and b XOR b = 0 and nullified.
length of this sequence = f1 + f2
SO, we want to minimise(f1 + f2) such that f1 * f2 = P. We can use Dynamic Programming to solve this.
- Since we considered only 1 such pair , there can be many such pairs (a,b) which satisfy the constraint. They might give a lesser value of (f1 + f2). Hence, our sequence can be a concatenation of many such smaller sequences.
- We can say P is composed of
\[P = \sum (f_i1 * f_i2) \space, \text{and} \sum(f_i1 + f_i2) <= N\]
We can say dp[i] = min(x + y) where x * y = i
- After we have precalculated that, we again use DP to find the minimum possible length that can be composed of many sequences.
dp[i] = min(dp[i], dp[j] + dp[i - j]) for each i in 1 to N, for each j in 1 to i
Implementation :
#include <bits/stdc++.h>
using namespace std;
#define int long long int
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
// Function to check if sequence construction is possible
void isSeqPossible(int n, int p, int x)
{
const int N = 2 * 1e4 + 7;
vi dp(N, INT_MAX);
// first dp
for (int i = 1; i < N; i++) {
for (int j = i; j < N; j += i)
dp[j] = min(dp[j], i + j / i); // dp[p] = min length of sequence i.e, x + y
// such that (x * y = p)
}
// since P is the length, dp[a] = min(dp[a], dp[b] +
// dp[c]) if b + c = P
for (int i = 1; i < N; i++) {
for (int j = 0; j < i; j++)
dp[i] = min(dp[i], dp[j] + dp[i - j]);
}
if (dp[p] <= n)
cout << "Possible" << endl;
else
cout << "Impossible" << endl;
}
// Driver code
signed main()
{
int n = 10, p = 8, x = 2;
isSeqPossible(n, p, x);
return 0;
}
Time Complexity : O(N * N), for the i-j loop of the DP.