ECPC10A - Editorial



Author: Gourav Rathor
Tester: Pankaj Sharma
Editorialist: Gourav Rathor




Basic looping, Bitwise-XOR.


You have given N numbers A_1 to A_N.
You have to find number of pairs for which XOR of pairs is greater than paired numbers.


This is a simple bruteforce problem.
Run a program for each pair and whenever you find XOR of pair greater than both pair
integer increase the count element by one.


Setter's Solution
#include <bits/stdc++.h>

using namespace std;

int solve(vector<int>&v)
    int count=0,n=v.size();
    for(int i=0;i<n-1;i++)
        for(int j=i+1;j<n;j++)
    return count;

int main() {
    int t;
      int n;
      for(int i=0;i<n;i++)
    return 0;

Please give me suggestions if anything is unclear so that I can improve. Thanks :slight_smile:


How did O(N^2) get accepted? I was thinking an efficient approach throughout the time. Am I missing something?


You might have missed this
sum of N over all test cases does not exceed 10^4


Was O(n2) time complexity get accepted??


Excited with the name Brute Force, I have just coded the brute solution in one go. But, I’m not sure why, but the Python 3 (submitted under PYTH 3.6 instead of PYPY3 based on Python 3.5) code got Runtime Error! Then, I was looking for corner cases, tried running it to the limit constraints, but it didn’t work. I was unable to find the reason for a Runtime Error, here’s the brute force code in O(n^2):

Then, I just tried to handle it with try and except, but then I have got a TLE (Time Limit Exceeded). Here’s the same code, with minor changes compared to my previous submission -

I’m not sure why this implementation didn’t work for Python 3.6, while the same brute approach is given here in the editorial.

P.S.: Using sys.stdin.readline() instead of input() worked, and the O(n^2) code now gets AC. Not sure if input() is slower or not, but I guess I’ve found a new alternative to work with, in my future solutions with Python 3. :smile:

The only problem now left is that the same code which works for PYPY3 fails for PYTH 3.6 language selection from dropdown in CodeChef IDE. If anyone has a working Python 3 solution (submitted under PYTH 3.6 and not PYPY3), please let me know.

Any help and suggestions on the same are appreciated!

what should condition of n for -->" sum of N over all test cases does not exceed 10^4" if t<1e3 and n<1e4;

What did I do wrong in my solution, it is the same solution, it is still not accepted please tell my my mistakes, I am new to CP.

I got WA with this.

#include <bits/stdc++.h>

using namespace std;

define ll long long

int main() {
int t;
cin >> t;

while (t--) {
    int len;
    cin >> len;
    int arr[len];
    for (int i = 0; i < len; i++) {
        cin >> arr[i];
    sort(arr, arr + len);
    int count = 0;
    for (int i = 0; i < len - 1; i++) {
        for (int j = i + 1; j < len; j++) {
            if ((arr[j] ^ arr[i]) > max(arr[j], arr[i])) count++;
    cout << count;
return 0;


I think you are supposed to write cout << count << endl, instead you wrote cout << count.


Well crap, that was a very dumb mistake, Just executed it after adding endl , works fine.

Thanks anyway.

1 Like

i have applied same logic but i got tle :frowning:
your solution is also have o(n) time complexity as i have , can you explain why
here is my code link :

please have a look buddy , you may save me from frustating

i have same doubt , i got TLE error :woozy_face:

Your AC code

Can we do it in O(n) ?

Can you please share the code here, I am getting invalid code I’d for that link.

maybe not in O(N), but we can do in O(Nlog(1e9)).
my solution :

ECPC10A works for python3 but is exceeding the time limit. I’m not sure it is right or wrong. :sweat_smile: but someone told me if you want your code work faster so, use pypy3.
also i found this stuff on google,,run%20on%20the%20Java%20platform.

1 Like

can someone tell me what’s wrong in my solution:
solution link =>

Can anyone explain the O(N logN) approach? One of the solutions.