You are not logged in. Please login at www.codechef.com to post your questions!

×

XXOR - Editorial

PROBLEM LINK:

Div1, Div2
Practice

Author: Hruday Pabbisetty
Tester: Triveni Mahatha
Editorialist: Adarsh Kumar

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Prefix Sum

PROBLEM:

You are given an array with $N$ elements. You need to answer $Q$ queries. In each query, you are given two parameters $L$ and $R$, and you have to find the smallest integer $X$ such that $0 \le X < 2^{31}$ and the value of $\sum \limits_{i=L}^R (A[i]\text{ xor }X)$ is maximum possible.

EXPLANATION:

Lets focus on the binary representation of each $A[i]'s$ and $X$. You can observe that each bit are independent, i.e. you can solve the same problem by iterating over each bit. Basically, for each bit you can reduce the problem to simpler one.

Given a binary array $P$ of length $N$. And in each query, you need to find minimum $X$ where $0 \le X \le 1$ and the value of $G(L,R) = \sum\limits_{i=L}^R (P[i]\text{ xor }X)$ is maximum possible. Lets see, if we take $X = 0$, value of $G(L,R)$ will be equal to number of occurences of $1$ in range $(L,R)$. If we take $X=1$, value of $G(L,R)$ will be equal to number of occurences of $0$ in range $(L,R)$. Hence, we can conclude that if the number of occurences of $1$ is greater than or equal to number of occurences of $0$ in range we will take $X$ as $0$ else we will take $X$ as $1$.

For each query, we just need to answer number of bits that are $1$ at $j^{th}$ bit in the range $(L,R)$ for all $0 \le j < 31$. For doing the same we will maintain prefix sum for each of the bit position. The pre-processing part can be done in $O(N.log(MAX))$. We can answer each of the query in $O(log(MAX))$ now, i.e. $O(1)$ for each of the bit position. For more implementation details, you can have a look at attached solutions.

Time Complexity:

$O((Q+N).log(MAX))$

AUTHOR'S AND TESTER'S SOLUTIONS

Setter's solution
Tester's solution

This question is marked "community wiki".

asked 09 Mar, 01:29

adkroxx's gravatar image

7★adkroxx
306718
accept rate: 7%

edited 13 Mar, 15:05

admin's gravatar image

0★admin ♦♦
19.0k348495531


12next »

No, you do not need segment tree for preprocessing. Just use a prefix array.

python solution

link

answered 12 Mar, 19:19

kdark884's gravatar image

5★kdark884
531
accept rate: 0%

nice and clean implementation :p

(14 Mar, 17:43) harrypotter02★

@ayushgoyal1703 The link you provided won't work for other people. This is the link to your submission.

link

answered 16 Mar, 18:09

iprakhar22's gravatar image

4★iprakhar22
132
accept rate: 0%

What are the ways in which the pre-processing part can be done? Segment Tree?

link

answered 12 Mar, 17:23

stym_06's gravatar image

2★stym_06
1
accept rate: 0%

You can do it by using 2D arrays @stym_06.

my c++ soln : https://www.codechef.com/viewsolution/17712082

link

answered 12 Mar, 20:00

mehul_dholiya's gravatar image

2★mehul_dholiya
242
accept rate: 0%

link

answered 13 Mar, 01:45

cloudsandrain's gravatar image

4★cloudsandrain
413
accept rate: 0%

Setter's and Tester's solution are not there and I am having trouble in understanding the approach used for this . Can someone explain an overview of what solution has been used in a less mathematical way ? Thanks in advance :)

link

answered 13 Mar, 10:06

harrypotter0's gravatar image

2★harrypotter0
1859
accept rate: 2%

Initially, we have to store set-bits of all numbers in a 2-D vector. Then take prefix sum of the 2-D vector.

Let assume that the query is from l to r index. For any jth bit , the numbers having it set are prefix[r][j] - prefix[l - 1][j]. The sole crux of the logic is to check whether (for any jth bit) numbers having that bit set are more or not. If numbers having jth bit set are more in query(l -> r) , then we have to keep that bit unset in X. And in other way around, if numbers having that bit unset are more , then set that bit in X. If both are equal, keep it unset(question asks for smaller number).

link to my solution: https://www.codechef.com/viewsolution/17598273

hope it helps :)

link

answered 13 Mar, 10:27

nikesh48's gravatar image

4★nikesh48
262
accept rate: 50%

edited 13 Mar, 10:28

thanks buddy got it now :p

(14 Mar, 18:00) harrypotter02★
link

answered 13 Mar, 19:15

storyteller's gravatar image

3★storyteller
1
accept rate: 0%

i used square root decomposition. whoever is interested can see

link

answered 13 Mar, 20:33

ganesh35's gravatar image

1★ganesh35
211
accept rate: 0%

Where is your code's link? :p

(14 Mar, 17:59) vijju123 ♦5★

XXOR this problem can be done with the help of prefix sum of a 2D array into a another matrix of same size of [n][31].This a simple Question based on the basics of dynamic programming as u store the value and use it further by substracting to row let L & R.First you have to on all the 31 bit that is equal 2^31-1.Then you have to decide which bits should off according to maximize the ans as well as minimize the X.If anyone need soln. Then comment pliz.

link

answered 14 Mar, 18:18

souradeep1999's gravatar image

4★souradeep1999
404
accept rate: 0%

edited 14 Mar, 18:20

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×14,365
×1,397
×264
×255
×142
×64

question asked: 09 Mar, 01:29

question was seen: 5,650 times

last updated: 19 Mar, 18:29