PERMXORSUM-Editorial

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;
}
4 Likes

I tried a DP approach for this problem for N <=1e6 but it was not passing subtask for 60 points.

Can someone tell that does my DP state gives a write / optimal answer or what I thought is wrong?? as the sample test cases given were passing…

#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mod 1000000007

const ll N = 1e8+1;
     ll dp[N];
int main() 
{
FIO;

ll t;cin>>t;

 
     dp[1]=0;
     dp[2]=6;
     dp[3]=6;
     for(int i=4;i<=N;i++)
     {
         if(i%2==0)
         {
              dp[i]= dp[i-1]+(2*((i-1)^(i))); 
         }
         else
         {
             dp[i]= dp[i-1]; 
         }
         
       

     }
while(t--)
{
    ll n;cin>>n;

     cout<<dp[n]<<"\n";

}




}

which one u think is a tougher problem :

  1. finding the maximum ans
    OR
  2. finding the exact permutation which gives maximum ans(ofc. for this n will then be at max in range 10**6)

The thing is i was able to find one of the permutation which gives the maximum ans , but couldn’t do it for higher n thus my solution begin limited to subtask1. Just wondering , how the difficulty would have changed if we were asked to print the required permutation . :thinking: :thinking:

2 Likes

What i did-
I created an array for the numbers which have all the bits set.
Then i am finding, where that number in the array lies.
By observation- There can be at most arr[i-1] pair with all bits as set after XORING, for arr[i], which in my opinion will give maximum answer.

I am not getting answer, I got SIGSTP as error.
I couldn’t find what am i doing wrong…What is wrong in this code?
What’s the flaw in my approach?

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    cin.sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	long long int cases;
	cin>>cases;
	while(cases--){
	    long long int n; cin>>n;
	    long long int arr[31]; arr[0]=1;
	    for(int i=1; i<31; i++){
	        long long int temp=pow(2,i);
	        arr[i]+=arr[i-1]+temp;
	    }
	    long long int sum=0;
	    while(n>1){
	        for(int i=1; i<31; i++){
	            if(n==arr[i]){
	                sum+=arr[i]+(arr[i]*2*arr[i-1]);
	                n=0;
	                break;
	            }
	            else if(n>arr[i] && n<arr[i+1]){
	                sum+=(n-arr[i])*arr[i+1]*2;
	                n=arr[i]-(n-arr[i]);
	                break;
	            }
	        }
	    }
	    if(n==1){
	        sum+=0;
	    }
	    cout<<sum<<endl;
	}
	return 0;
}

Thank you!!

Well, nice thought, but I don’t think the difficulty will rise much, because printing the permutation follows the same logic as finding the max answer, as far as I did. However, the constraint on N will obviously be limited to 10^6.

1 Like

may be bit trie can be used

Yeah ig we can use trie , but i have even a simple approach without trie

Yeah , i think it would have been more fun to construct the exact permutation

this is my solution and it is passing all the test cases but dont know why it is giving tle can someone help me out please

#include <bits/stdc++.h>

using namespace std;

int main()

{

int t;

cin>>t;

while(t--)

{

   long long int n;

    cin>>n;

    if(n==1)

    {

        cout<<0<<endl;

        continue;

    }

    if(n==2)

    {

        cout<<6<<endl;

        continue;

    }

    long long int check=ceil(log2(n));

    if(n==pow(2,check)-1)

    {

        n=n-1;

    }



if(n%2==0)

{

   int s,f;

s=n;

long long int x=ceil(log2(n));

 long long int z=pow(2,x)-1;

 f=z-n;

 long long int ans=0;

while(f!=1)

{

   ans+=z*(s-f+1);

   s=f-1;

   x=ceil(log2(s));

   z=pow(2,x)-1;

   f=z-s;

}

ans+=z*(s-f+1);

cout<<ans<<endl;



}else{

  long long int s,f;

s=n;

 long long int x=ceil(log2(n));

 long long int z=pow(2,x)-1;

 f=z-n;

 long long int ans=0;

while(f!=2)

{

   ans+=z*(s-f+1);

   s=f-1;

   x=ceil(log2(s));

   z=pow(2,x)-1;

   f=z-s;

}

ans+=z*(s-f+1);

cout<<ans<<endl;

}

}

return 0;

}

I used the same idea as Editorialist’s Solution but with different implementation.
my implementation make the complexity O(1) per testcase

res=n*(n+1)
x=n+(n&-n)
if(n&1)res-=2*(n- (x&(x-1)) )

(n&-n) will return least significant bit and adding it to n will clear the first consecutive set bits of n and set the bit after them
then anding this number with (itself -1) will clear the least significant bit again
so now n - (this value) will give the value of the first consecutive set bits

4 Likes

I solved it using recursion and memoizing the results whenever required.

I tried to discover some pattern and what I found is that :

  1. if twos_complement(n) is zero then we have to take xor of it with itself thus reduced the problem of finding answer for (n-1).
  2. Else ,suppose k = complement(n)… Then in the range [k,n] every ith number from starting should be xored with every ith number from ending of this range for maximizing the score.
    Thus ,problem then got reduces to finding the answer for (k-1).

It can be proven using bit manipulation concepts that every recursion calls atmost logn time.So,overall time complexity will be O(T*log(MaxN))

If the problem will be of printing the permutation then also it can easily be printed using this logic.

Here is the code link-> Code

5 Likes

yes ur approcah is wrong as for n==5 ur answer gives 20 . but the maximum answer is 28

Can someone give me the wrong test case for my code? It passed the sample test cases, and one subtask on submission. I think I am missing some corner case. Link

int calc(int n)
{
	if (n == 0ll || n == 1ll)
	{
		return 0ll;
	}
	if (n == 2ll || n == 3ll)
	{
		return 6ll;
	}
	int bits = 0ll;
	int tmp = n;
	while (tmp > 0ll)
	{
		bits++;
		tmp >>= 1ll;
	}
	int c = (1ll << bits);
	c -= 2ll;
	int ans = c * (c + 1ll);
	ans -= ((c + 1ll) * 2ll * (c - n));
	return (ans + calc(c - n));
}

Thanks

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

int main() {
ll t,n,i;
cin>>t;
while(t–) {
cin>>n; ll sum=0;

        if(n==1)
         cout<<0<<"\n";
         
        else {  ll z= n/2; 
                 sum+= (z)*(2*3 + 4*z -4);   // AP  
                   cout<<sum<<"\n";  }    
         
    } 
                return 0; } 

// For which test case , i am getting WA for this problem ? @admin @daanish_adm

// Mitesh Darda
// Work Eveyday Like The Future Self You Desire To Be
#include<bits/stdc++.h>
using namespace std;
vector<int> s;

void fillSquare() {
    long long int elemToBePushed = 0;
    vector<int> twoPower;
    int p = 0;
    twoPower.push_back(1);
    while (elemToBePushed < 1000000000) {
        elemToBePushed += twoPower[p];
        twoPower.push_back(twoPower[p] * 2);
        s.push_back(elemToBePushed);
        p++;
    }
}

void solve() {
    long long n; cin >> n;
    long long ans = 0;
    vector<bool> check(n + 1, true);
    for (int i = n; i >= 1; --i) {
        if (check[i]) {
            auto upper = lower_bound(s.begin(), s.end(), i);
            int num = s[upper - s.begin()] - i;
            if (num == 0)continue;
            ans += (num ^ i) * 2;
            check[num] = false;
        }
    }
    cout << ans << endl;
}

int main()
{
    fillSquare();
    int t; cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

i have done this problem in O(n) still it is giving me TLE(1.010000) for the last 5 test cases can someone explain me what i am doing wrong ?

https://www.codechef.com/viewsolution/57393314

When ever n==2 it forms an infinite loop