< Back to forum

Xxor March long

I've tried a method for 18 points which worked , also tried diving xor into bitwise and and or operations and tried to club the array elements somehow to prefalcute but didn't really work, what's the best way to approach it?

codechef xxor march long prefix-sum

Asked by: Liman_Rahman on April 7, 2019, 6:34 p.m. Last updated on April 7, 2019, 6:34 p.m.

Enter your answer details below:


Enter your comment details below:




2 Answer(s)

avatar

Prefix-sum is probably the simplest and the best approach to this problem.

Have a look at this editorial which uses prefix-sum based approach.

Comment here if you face diffucilty understanding any part of the editorial or implementing it.

https://discuss.codechef.com/questions/124102/xxor-editorial

Shubham_Kumar_Gupta last updated on April 7, 2019, 6:34 p.m. 0    Reply    Upvote   

avatar

Find the binary represention of all the numbers given. Then for each position (i.e. from 0 to 30) count number of 0's and 1's in range l to r. If number of 0's is greater than no. of 1's, then at that position, bit of the new number will be 1 otherwise 0. Similarly find it for all 30 positions. By doing this we can find at each position which bit would maximize the sum.

Try to use prefix sum along with this approach.

Shivansh_Agarwal last updated on April 7, 2019, 6:34 p.m. 0    Reply    Upvote   

Instruction to write good question
  1. 1. Write a title that summarizes the specific problem
  2. 2. Pretend you're talking to a busy colleague
  3. 3. Spelling, grammar and punctuation are important!

Bad: C# Math Confusion
Good: Why does using float instead of int give me different results when all of my inputs are integers?
Bad: [php] session doubt
Good: How can I redirect users to different pages based on session data in PHP?
Bad: android if else problems
Good: Why does str == "value" evaluate to false when str is set to "value"?

Refer to Stack Overflow guide on asking a good question.