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

×

XORIER - Editorial

1
2

PROBLEM LINK:

Div1
Div2
Practice

Setter- Priyanshi Gupta
Tester- Teja Vardhan Reddy
Editorialist- Abhishek Pandey

DIFFICULTY:

EASY

PRE-REQUISITES:

Goldbach's Conjecture , Frequency array concept, Properties of XOR.

PROBLEM:

Given an array $A$ of $N$ numbers, we need to tell number of pairs of indices $(i,j)$ such that -
- $1 \le i < j \le N$ (1 based indexing)
- $A_i \oplus A_j$ can be written as sum of $2$ prime numbers of same parity.

QUICK-EXPLANATION:

Key to AC- Deducing $2$ facts-
1. XORing numbers of same parity always results in even numbers. And adding prime numbers of same parity results in even numbers as well.
2. Correlating above to Goldbach's conjecture which says any even number $>2$ can be represented as a sum of $2$ primes.

Deducing above $2$ was was the main turning point, and difference between a quick AC and complete cluelessness.

Quick Explanation- Focus on what the question says. It first says that, $A_i \oplus A_j$ must be representable as a sum of prime numbers of same parity. Its basic math that adding two numbers of same parity results in a sum of even parity ($i.e.$ $Odd+Odd=Even.$ $Even+Even=Even$). Also, the same rule holds for XOR.

Appplying Goldbach's conjecture, the question reduces to find how many pairs $(i,j)$ exist such that-
- Their XOR is even.
- Their XOR is greater than $2$.

For XOR being even, we check only among pairs with same parity. For XOR being greater than $2$, we first find number of all possible even XOR values, and then reduce count of XORs with value $2$ and $0$. This can be done easily via frequency array.

EXPLANATION:

The explanation will have a single section explaining editorialist's solution. Some proofs are left as in exercise to reader - their answers can be found in my bonus corner at the end of editorial. Try to read the editorial in a way to capture the thought process going in mind of a coder, because often we all know and are aware of things but fail at application in correct form. I assume you are thorough with basic properties of XOR. Please read them under pre-requisites if its not the case!

Editorialist's Solution-

Lets first discuss the solution of first sub-task for formality. The idea of first subtask is to use $2$ nested loops, and try out all the possible $\frac{N*(N-1)}{2}$ values of $i$ and $j$. If their XOR is even and greater than $2$, add $1$ to answer.

Now, before moving towards the full solution, grasp the $3$ rules I say below. If having trouble, try to prove them or check out proofs in the bonus corner below. Then, proceed once you have proper clarity about those.

1. Only the rightmost bit (i.e. Least-significant bit or LSB) determines whether a number is odd or even.
2. Using above rule, conclude that XOR of numbers of same pairty is always even. (i.e. $Even \oplus Even=Even$ and $Odd \oplus Odd=Even$)
3. Read Goldbach's Conjecture, which says, " that every even integer greater than two is the sum of two prime numbers.". Do NOT try to prove it. This conjecture is still unproven and its proof is one of mysteries, but the results have been verified to hold true for numbers even larger than $4*{10}^9$. Hence, it holds good in the range of input which we have.

With above $3$, we can get a hint of implementation in mind. We need a count of numbers which are $odd$, and which are $even$ (so that their XOR is always even).

After that, we have to check that the equivalent XOR is greater than $2$. If it is, then by Goldbach's conjecture, any even number greater than $2$ satisfies our condition of being a sum of $2$ primes of same parity. Now, this part is where most of contestants face problem - usually because they never did a similar problem before.

Newbies get overwhelmed by "Ok its easy to make sure that XOR is even, but how do I assure that its greater than $2$ and include only proper indices in my answer?!"

The answer is simple, dont! The proper methodology is to, first find the answer including repetitions and pairs with XOR $\le 2$ as well, and later subtract irrelevant ones from answer. (You can find a note about it in point $3.$ of my corner.) Making sure that XOR is $>2$ on the run is difficult. Instead, first just count how many pairs $(i,j)$ are there such that $A_i \oplus A_j$ is even. That is easy, right? Make it easier, for now, forget about restriction of $1 \le i < j \le N$, just find any pair $(i,j)$ such that $1 \le i,j \le N$. Any pair will do, no constraints on $i$ and $j$. Can you do that, if you are given the array $A$ and know how many numbers in it are $odd$ and how many numbers are $even$? (Check out tab below to see how if cannot).

View Content

Now, we have the answer in crude form, what we have to do is to account for repetition of pairs (we counted $(2,1)$ and $(1,2)$ differently, which makes our answer twice the expected one), which can be easily done by halving the answer in the end.

First, we have to take care of cases when XOR comes out to be $2$ or $0$ (i.e. even number $\le 2$). This is also simple! For this, maintain a frequency array, and now count how many times each number occurs.

Now, think to yourself, for every element in array $A_i$, how many choices do I have to choose $j$ such that $1 \le i,j \le N$ and $A_i \oplus A_j=2$ ? Lets use $b$ to represent all numbers such that $b \oplus A_i=2$. We find that $b=A_i \oplus 2$. (Proof given in tab below). Hence, all we have to do is to subtract the count of numbers with value $A_i \oplus 2$ to account for numbers having XOR=$2$!!

View Content

Similarly, to account for numbers with XOR $0$, we think of how many choices do I have to choose pairs $(i,j)$ under same conditions (as above) such that $A_i \oplus A_j=0$. It is very easy to see that, if we use $b$ to represent choices of numbers such $A_i \oplus b=0$, then this will imply that $b= A_i$. Hence, we simply reduce frequency of $A_i$ from our crude answer.

(Check out above proof and try to follow exact guidelines to derive this, if in confusion how we concluded this. The steps to be followed are exact same!).

In the end, as I mentioned above, after accounting for XORS resulting in $2$ and $0$, we simply halve the answer to get the final answer to print :) .

As an exercise, try to write down an implementation of above idea in pen and paper. A code to compare your implementation with is given below as answer-

One warning though, make sure to declare your frequency array larger than size $1000001$ so that you dont get out of bounds when checking for count of $A_i \oplus 2$

View Content

SOLUTION

The respective codes are also pasted in tabs below in case the links do not work. This is for convenience of readers, so that they can copy paste it to whichever IDE or editor they are comfortable reading it in and immediately have access to the codes. :)

Author's solution can be found here.

Tester

View Content

Editorialist

View Content

$Time$ $Complexity=O(N)$
$Space$ $Complexity=O(N)$

CHEF VIJJU'S CORNER :D

1. Proof Only LSB determines pairty.

View Content

2. XOR of same parity is always even.

View Content

3. LoEE-

View Content

4. Related problems - The only reason newbies are not able to solve problems on frequency array topic is because of lack of practice. Practice these problems till the process becomes completely mechanical and intuitive for you. :)

  • AVGPR - Another question on Frequency array. You can find more problems in my editorial of this problem :)

asked 07 Sep '18, 11:25

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

edited 18 Sep '18, 12:55

admin's gravatar image

0★admin ♦♦
19.8k350498541

Minor typo - "Goldbach", not "Goldback" (in the prerequisites)

(17 Sep '18, 23:20) rashomon4★

What I did in this problem is :

-> Split input in two arrays

1) odd
2) even

-> Divide each number by 4 (removing last two bits)

why?
Reason :

View Content

Now for both arrays (odd and even )

Count freq of each element in array of size $10^6/4 +1 $ (range/4 as I have divided each value by 4)

Do : $ans= { n \choose 2 }$ (n is size of each array)

Then: $ans-= \sum_{k=0}^{k=10^6/4} { freq(k) \choose 2}$

That is nothing but,

all possible pairs ${ n \choose 2 }$ - pairs whose xor is 0 or 2 ( $ { freq(k) \choose 2}$ for each k )

Simple Implementation in c++ can be found HERE

link

answered 17 Sep '18, 22:58

l_returns's gravatar image

4★l_returns
1.6k211
accept rate: 23%

edited 17 Sep '18, 23:14

I admire the trick of div by 4. Sneaky.

(18 Sep '18, 01:33) joffan5★

..Thanks !!

(18 Sep '18, 07:05) l_returns4★

For me, I first created a frequency array, and also split the input array into two arrays:

  1. an array of even numbers
  2. an array of odd numbers.

I then sorted the two arrays(I will latter on apply binary search), and performed the following steps:

  1. calculate number of odd pairs, "oddPairs" using (n(n+1)/2)-n, and add it to number of even Pairs, "evenPairs".
  2. calculate number of pairs whose XOR is 0, "zeros" from the frequency array
  3. calculate number of pairs whose XOR is 2, "nparity", by applying binary search on both even and odd arrays.
  4. And finally subtracting (zeros + nparity) from (oddPairs + evenPairs)

There were a few observations which I made, leading to my decision to apply binary search:

  1. If a is even then a^(a + 2) is 2 only if a/2 is even, and a^(a - 2) is 2 if otherwise.
  2. If a is odd then a^(a + 2) is 2 only if (a+1)/2 is odd, and a^(a - 2) is 2 if otherwise.

So the way I calculated the pairs whose XOR is 2 was by applying binary search separately on each sorted array, starting from the first number a[1] in the array, I would then search for either (a + 2) or (a - 2) depending on the above observations, and then marking all indexes from (a + 2) onwards or (a - 2) onwards as seen, so that those indexes wouldn't be latter on visited. Here's my solution https://www.codechef.com/viewsolution/20133014

link

answered 18 Sep '18, 16:09

anaphase21's gravatar image

3★anaphase21
513
accept rate: 100%

edited 18 Sep '18, 21:13

how can i reduce the time required for this execution..?
https://www.codechef.com/viewsolution/20227441

link

answered 18 Sep '18, 11:12

tushar2899's gravatar image

2★tushar2899
27219
accept rate: 8%

edited 18 Sep '18, 11:16

Firstly, Python has an xor operation: a^b. No need to code your own. Then read the editorial and i_return's answer.

(18 Sep '18, 11:53) joffan5★

Goldbach's conjecture was proved upto 4*10e18 :)

link

answered 18 Sep '18, 11:21

vss96's gravatar image

2★vss96
11
accept rate: 0%

edited 18 Sep '18, 11:22

3)calculate number of pairs whose XOR is 2, "nparity", by applying binary search on both even and odd arrays. it requires 2 for loops right(order of n)

link

answered 19 Sep '18, 09:51

jawa2code's gravatar image

3★jawa2code
24127
accept rate: 0%

No. It requires only 1 for loop. You first take a number a[i]. If it's even, you divide it by two. If the result of the division is even it means that a[i]^(a[i] + 2) is 2. So you search for (a[i] + 2) using binary search. The search will either return -1 if (a[i] + 2) is not found, or the index of where it occurred. And since our arrays are sorted, we can get the number of times (a[i] + 2) is repeated.

(19 Sep '18, 15:12) anaphase213★

We would have searched for (a[i] - 2) if the result of our division was odd. On the other hand, if a[i] is odd, then we divide a[i]+2 by 2. If the result is odd, we search for a[i]+2, and if otherwise, we search for a[i]-2.

NOTE: Binary search is what is being applied here, and not linear search. So in the worst case (when there are no pairs whose XOR is 2), then we will have O(NlogN); in the best case (where the a[0] matches with the rest), then we have approximately O(logN).

(19 Sep '18, 15:25) anaphase213★

https://www.codechef.com/viewsolution/20237335 In my implementation, instead of halving the value at the end. I have decremented the frequency and odd or even before each iteration. So, can anyone point out which case did i miss. Thanks in Advance

link
This answer is marked "community wiki".

answered 19 Sep '18, 16:18

rama_545's gravatar image

3★rama_545
1
accept rate: 0%

wikified 23 Sep '18, 19:13

I got WA for the following code:

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

Can someone please suggest me a testcase for which this code fails?

link

answered 20 Sep '18, 00:34

meetrockstar's gravatar image

4★meetrockstar
14316
accept rate: 10%

for better clarity one can use structures, as i have used. check out thislink text https://www.codechef.com/viewsolution/20240933code and u will understand everything.

link

answered 20 Sep '18, 14:25

deadpool1999's gravatar image

2★deadpool1999
1
accept rate: 0%

int n = scn.nextInt(); long[] arr = new long[n];

        int odds = 0;
        int evens = 0;

        HashMap<Long, Long> map = new HashMap<>();
        for (int j = 0; j < n; j++) {
            arr[j] = scn.nextLong();
            if (arr[j] % 2 == 0) {
                evens++;
            } else {
                odds++;
            }
            if (map.containsKey(arr[j])) {
                map.put(arr[j], map.get(arr[j]) + 1);
            } else {
                map.put(arr[j], 1l);
            }
        }
        long totalPair = ((n) * (n - 1)) / 2;
        long evenOddPairs = evens * odds;

        // these pairs have xor even >  
        long onlyEvenOrOddPair = totalPair - evenOddPairs;

        long sameNoPair = 0;
        // remove pairs with xor zero
        ArrayList<Long> keyset = new ArrayList<Long>(map.keySet());
        for (int i = 0; i < keyset.size(); i++) {
            long aI = keyset.get(i);
            long freqI = map.get(aI);

            if (freqI > 1) {
                sameNoPair += ((freqI) * (freqI - 1)) / 2;
            }
        }

        long pairWithXorEqual2 = 0;
        for (int i = 0; i < keyset.size(); i++) {
            long aI = keyset.get(i);
            long freqI = map.get(aI);

            long aJ = aI ^ 2;

            if (map.containsKey(aJ)) {
                long freqJ = map.get(aJ);
                pairWithXorEqual2 += freqI * freqJ;
            }

        }

        pairWithXorEqual2 = pairWithXorEqual2 / 2;

        long ans = onlyEvenOrOddPair - sameNoPair - pairWithXorEqual2;
        System.out.println(ans);
link
This answer is marked "community wiki".

answered 20 Sep '18, 19:00

ayush3890's gravatar image

3★ayush3890
0
accept rate: 0%

please help with this code

(20 Sep '18, 19:02) ayush38903★

https://ide.codingblocks.com/#/s/28157

this fails for the last test case.can anyone help

link

answered 25 Sep '18, 00:49

aayush_b1999's gravatar image

3★aayush_b1999
1
accept rate: 0%

IN RESPONSE TO:https://discuss.codechef.com/questions/134985/xorier-editorial/135714

@ayush3890 Hi , I think we both have used similar approach , you can have a look at my code. If it helps. https://www.codechef.com/viewsolution/20337606

link

answered 26 Sep '18, 16:12

johnson_admin's gravatar image

1★johnson_admin
1
accept rate: 0%

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:

×3,828
×304
×268
×241

question asked: 07 Sep '18, 11:25

question was seen: 3,531 times

last updated: 26 Sep '18, 16:12