Solution for the 2nd question: Integer Distribution
For the 2^{nd} Question: Integer Distribution.
Here is the solution
Brute Force Approach
We first create 2 variables mx and mn to store the maximum and minimum values.
The brute force approach would be to generate all possible sequences/permutations and then loop over them, then updating the variable mx and mn accordingly depending on whether the Sum of the Xor values of the pairs in this sequence is greater than mx or lesser than mn.
Given a permutation, we group the adjacent elements into a pair and then xor that pair and then add them to the ans. The we update mx and mn.
In general for an array size of n, there are n! sequences. This translates to O(n!*n) time complexity, which wouldnt meet the time constraints, as n can be as large as 20
I have to admit that this brute force method is very bad, because there would be a lot of overcounting, for example in the array [1,2,3,4]
The sequences [2,3,1,4] and [2,3,4,1] correspond to the same pairs (2,3) and (1,4). But we end up recalculating them, leading to higher time complexity.
In fact for an array of size 4 [1,2,3,4], there are only 3 sequences that we need to check, but in this approach we end up checking 4!=24 sequences. Maybe using some sort of backtracking, we can generate just the right amount of distinct sequences, but I havent been able to figure that out yet. But I still believe that the solution I have discussed below would still be faster than any backtracking solution.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long int
vector<int> solve(vector<int>& nums){
int n = nums.size();
vector<int> result;
int mx = 0, mn = 1e9 + 7;
sort(nums.begin(), nums.end());
do{
int ans = 0;
for (int i = 0; i < n;i+=2){
ans += (nums[i] ^ nums[i + 1]);
}
mx = max(mx, ans);
mn = min(mn, ans);
} while (next_permutation(nums.begin(), nums.end()));
result.push_back(mx);
result.push_back(mn);
return result;
}
signed main(){
int n;
cin>>n;
vector<int> nums(n);
for (int i = 0; i < n;i++)
cin >> nums[i];
vector<int> ans = solve(nums);
cout << "Largest : " << ans[0] << endl;
cout << "Smallest : " << ans[1] << endl;
return 0;
}
DP Solution
I will first explain how we can get the maximum value.
Hint 1
This is a problem of bitmasking. The idea is to find the answer of some mask i where the positions where the bits are set represent that the number at the position of the array is considered and vice versa for the unset bits
Hint 2
Dp with bitmasking is a category of problems where we try to find the answer for a certain mask with x bits sets using the answers of the masks which have less than x bits set(also called submasks). Here a mask represents the array of numbers under consideration and the submasks would be the mask with any 2 bits unset(Think why?).
Solution
lets say we have the mask 1111. This means that arr[0],arr[1],arr[2] and arr[3] have been taken into consideration. So this is our subproblem that we need to solve, now. This can be done by first unsetting 2 bits and getting a new submask. The possible submasks that we can get are.
- 1100
- 1010
- 1001
- 0011
- 0110
- 0101
dp[mask] is the maximum sum of the xors that we can get when we consider only those elements that our mask represents
The reason we are unsetting 2 bits, is because these 2 bits that we unset now are the new pair that we are making right now. So we are basically checking all possible pairs that we can form in this mask and then the remaining bits that are set form our submask.
We loop over the submasks and then maximise our dp[mask]
Now our dp[mask]=max(dp[mask],arr[i]^arr[j]+dp[submask]);
Here our i and j are the indices where we unset the bits in our mask.
So we just have to loop over all masks(preferrably only those masks that have even number of bits set) and then find the dp[mask].
Our final answer would then be dp[2^n-1].
Code
#include<iostream>
#include<vector>
using namespace std;
#define int long long int
int inf = 1000 * 1000 * 1000 + 7;
int power(int a,int b){
int ans = 1;
while(b>0){
if(b&1)
ans = ans * a;
a = a * a;
b /= 2;
}
return ans;
}
vector<int> solve(int n,vector<int> nums){
int max_masks = power(2, n);
vector<int> dp_mx(max_masks,0);
vector<int> dp_mn(max_masks, inf);
dp_mx[0] = 0;
dp_mn[0] = 0;
vector<int> setbits;
for (int mask = 3; mask < max_masks;mask++){
setbits.clear();
for (int i = 0; i < n;i++){
if(mask&(1<<i))
setbits.push_back(i);
}
if(setbits.size()%2)
continue;
for (int idx1 = 0; idx1 < setbits.size();idx1++){
for (int idx2 = idx1 + 1; idx2 < setbits.size();idx2++){
int index1 = setbits[idx1];
int index2 = setbits[idx2];
dp_mn[mask] = min(dp_mn[mask], (nums[index1] ^ nums[index2]) + dp_mn[mask ^ (1 << index1) ^ (1 << index2)]);
dp_mx[mask] = max(dp_mx[mask], (nums[index1] ^ nums[index2]) + dp_mx[mask ^ (1 << index1) ^ (1 << index2)]);
}
}
}
vector<int> result;
result.push_back(dp_mn.back());
result.push_back(dp_mx.back());
return result;
}
signed main(){
int n;
cin>>n;
vector<int> nums(n);
for (int i = 0; i < n;i++)
cin >> nums[i];
vector<int> result = solve(n, nums);
int ans_mn = result[0];
int ans_mx = result[1];
cout << "Smallest : " << ans_mn << endl;
cout<<"Largest: " <<ans_mx<< endl;
return 0;
}
The time complexity of this approach is O(n^22^n). This is actually an upperbound, because we dont evaluate all masks, as I am skipping the masks with odd number of bits set. Also the actual complexity would be as follows:
\sum\limits_{i=2,i=even}^{n} (^{n}C_{i}) (^{i}C_{2}).
This is my 1^{st} time posting a solution on codechef. So feel free to make suggestions regarding the clarity in my explanation and my approach.
Thank you 
Also I would love to see, if there are any other much optimised solutions.