PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Author: Lokesh Singh
Tester: Takuki Kurokawa
Editorialist: Daanish Mahajan
DIFFICULTY:
Easy - Medium
PREREQUISITES:
None
PROBLEM:
Given N, find the maximum possible value of the permutation of integers from 1 to N where value of a permutation P is defined as:
1 \oplus P_1 + 2 \oplus P_2 + \ldots + N \oplus P_N.
EXPLANATION:
Hint 1
Solve for N as even and odd separately.
Hint 2
Find the upper bound for the answer.
Hint 3
Prove that a construction exists such that we can achieve the upper bound for all N.
Solution
Suppose a number x \in [1, N] has binary representation B_{x, hsb}, B_{x, hsb-1}, \ldots , B_{x,0} where hsb = \lfloor log_2 N \rfloor + 1 and B_{x, i} represents i^{th} bit of x and B_{x, i} \in \{0, 1\}.
- For N even:
\sum_{x=1}^{N} B_{x, i} \leq \frac{N}{2}, \forall i \in [0, hsb]. This means, there’s a possibility of arrangement in which a number having a bit set for some position i, is paired with a number having the bit unset at that position and if we can get this done for all the bits over all numbers, our answer will be maximum since none of the set bits gets canceled.
So upper bound on the answer is 2 \cdot \sum_{i = 1}^{N} i = N \cdot (N + 1).
Construction for the optimal permutation
Start pairing the elements starting from N. Suppose you are at any non paired element x, pair it with the closest non paired value y such that x \oplus y = x + y, i.e, none of the bits are lost and it can be proved that for every x such a y exists.
For example: Optimal permutation for N = 8 is
6 5 4 3 2 1 8 7
- For N odd:
\sum_{x=1}^{N} B_{x, i} \leq \frac{N}{2} + 1, \forall i \in [0, hsb]. For the values of i where \sum_{x=1}^{N} B_{x, i} = \frac{N}{2} + 1, atmost \frac{N}{2} set bits can be paired with \frac{N}{2} unset bits, implying atleast 1 set bit will get canceled. For other bit positions, atmax all the bits can be paired.
So upper bound on the answer is 2 \cdot (\sum_{i = 1}^{N} i - \sum_{i = 0}^{hsb} f(i)), where:
f(i)= \begin{dcases} 2^i,& \text{if } \sum_{x=1}^{N} B_{x, i} = \frac{N}{2} + 1\\ 0, & \text{otherwise} \end{dcases}
Construction for the optimal permutation
Start pairing the elements starting from N. Suppose you are at any non paired element x, pair it with the closest non paired value y such that x \oplus y = x + y, i.e, none of the bits are lost and if such a y doesn’t exist, have P_x = x, i.e, pair the element with itself. It can be proved that there exists only one index where this happens.
For example: Optimal permutation for N = 11 is
2 1 *3* 11 10 9 8 7 6 5 4 3 2 1
Here P_3 = 3.
Hence we are able to find a construction achieving the upper bound, thereby making it our answer.
COMPLEXITY ANALYSIS:
Maximum computation time is taken to calculate \sum_{i = 0}^{hsb} f(i) which can be calculated in two ways:
- Make a frequency array F where F_i represents the number of elements in the range [1, N] having their i^{th} bit set. This can be done in \mathcal {O}(sumN \log_2 maxN) where sumN represents the sum of N overall tests and maxN represents the maximum of N over all tests. This will pass subtask 1.
- The same can also be calculated in (\log_2 N)^2 using combinatorics and even better in \log_2 N with additional use of prefix sums. So the total complexity is \mathcal {O}(T \log_2 N).
Observation that makes the code way simple
Only the first consecutive set bits of N matter. See editorialist code for reference.
SOLUTIONS:
Setter's Solution
/**
* Coded by : lucky_21
* --------Lokesh Singh
**/
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define vi vector<int>
#define all(x) x.begin(),x.end()
#define fix fixed<<setprecision(10)
#define rep(i,a,b) for(int i=int(a);i<=int(b);i++)
#define repb(i,b,a) for(int i=int(b);i>=int(a);i--)
#define FastIO ios_base::sync_with_stdio(0),cin.tie(0)
typedef double db;
typedef long long ll;
const int N=2e5+5;
const int mod=1e9+7;
void solve(){
int n;
cin>>n;
ll ans=1ll*n*(n+1);
for(int b=0;b<30;b++){
int p=(1<<b);
int t=n/2/p*p;
int m=n%(2*p);
t+=max(0,m-p+1);
if(t==n/2+1){
ans-=2*p;
}
}
cout<<ans<<'\n';
}
signed main(){
FastIO;
int t;
cin>>t;
while(t--) solve();
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
long long ans = 0;
for (int i = 0; i < 30; i++) {
int cnt = 0;
if (n >= (1 << i)) {
cnt += max(0, n % (1 << (i + 1)) + 1 - (1 << i));
cnt += n >> (i + 1) << i;
}
if (cnt * 2 <= n) {
cnt = cnt * 2;
} else {
cnt = (n - cnt) * 2;
}
ans += (long long) cnt << i;
}
cout << ans << '\n';
}
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define F first
#define S second
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int t; cin >> t;
int n;
while(t--){
cin >> n;
ll ans = (ll)n * (n + 1);
ll p2 = 1;
while(n != 0){
if(n & 1)ans -= 2 * p2;
else break;
p2 *= 2; n /= 2;
}
cout << ans << endl;
}
return 0;
}