PERMXORSUM-Editorial

editorial
, , ,
12

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
13

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
14

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

15

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));
}
16

Thanks

17

#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

18 
// 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 ?

19

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

20

When ever n==2 it forms an infinite loop

21

please explain how u wrote Sigma formula <= n/2

22

I think finding exact permutation is easier as it can be done greedy (and hashing).
mine 60 points sol:-CodeChef: Practical coding for everyone
but coming up with a solution for 10**9 took time!
sol link:-CodeChef: Practical coding for everyone

1 Like
23

bro for last 5 Test cases we req O(logN) or O(1) solution as N<=1e9.
(You are from acropolis right? which year man?)

24

bro, you are creating a 1e8 size of dp array which will surely give you segfault or TLE!

1 Like
25

2019 batch. and you ?

26

2020 :slight_smile:

27

CS4 ?

28

Please provide the Video editorial for this problem. Are they out ??

29

That i fixed with i=0 in the for loop, and i also made mistake while calculating the array, I put += instead of = . Now it’s working. Thank you.

Here is my solution based on normal observation PERMXORSUM

30

This Problem is same as below.
https://codeforces.com/contest/288/problem/C

1 Like
31

Can anyone proof that why construction used works for even and odd? Thanks