PERMXORSUM-Editorial

editorial
, , ,
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

32

Can anyone please what should I do to reduce time limit.

#include<bits/stdc++.h>

using namespace std;

int main() {

int test;
cin >> test;

while(test--) {
    long long n;
    cin >> n;

    stack<long long> a;
    long long res=0;
    a.push(0);
    while(n) {
        long long bits = floor(log2(n)) + 1;
        long long n_ = (((1<<bits)-1)^n);
        
        if(((a.top() != n) and (n_))) {
            res += 2*(n^n_);
            a.push(n_);
        } else if(a.top() == n) a.pop();
        n--; 
    }
    cout << res << "\n";
}

}
Please guide me.

33

eg: n=22, 10110, XOR will be max if bits dont cancel. so 01001 i.e. 9 will counter it best for max sum. Similarly, 22 will be best counter for 9. Then 7(111) is for 8(1000) and vise-versa. Try yourself for in between 9 and 22. For 6, ‘110’, best is ‘001’, and vice-versa.
[6, 5, 4, 3, 2, 1, 8, 7, …22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9 ]
so, sum+=(22-9)*(31)(11111’s bit value)
21
[1, 5, 4, 3, 2, 9, 8, 7, 6, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10]

y=int(input())
for _ in range(y):
N=int(input())
s=0
i=N
d={}
while i>0:
bit=format(i,‘b’)
l=len(bit)
for j in range(l):
if bit[j]==‘0’:
c=[‘1’ for x in range(l)]
break
else:
c=[‘1’ for x in range(l+1)]
c=’’.join(c)
p=int(c,2) # max bit after xor is ‘p’, with all 1’s
t=i^p # counter part of ‘i’ is ‘t’
if t>N:
i-=1
continue
if t in d:
i-=1
continue
else:
d[t]=1
s+=(i-t+1)*p
i=t-1
#print(i,end=’,’)
print(s)