ECPC10A - Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest
Practice

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

Difficulty:

BEGINNER

Prerequisites:

Basic looping, Bitwise-XOR.

Problem:

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.

Explanation:

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.

Solution:

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++)
        {
           if((v[i]^v[j])>v[i]&&(v[i]^v[j])>v[j])
            count++;
          
        }
    }
    
    return count;
}



int main() {
    int t;
    cin>>t;
    while(t--)
    {
      int n;
      cin>>n;
      vector<int>v(n);
      for(int i=0;i<n;i++)
      cin>>v[i];
      cout<<solve(v)<<"\n";
     }
    return 0;
    
}

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

2 Likes
2

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

4 Likes
3

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

4 Likes
4

Was O(n2) time complexity get accepted??

5

BUMP

6

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): CodeChef: Practical coding for everyone

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 - CodeChef: Practical coding for everyone

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!

7

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

8

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() {
ios::sync_with_stdio(false);
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;

}

9

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

5 Likes
10

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

Thanks anyway.

1 Like
11

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 : CodeChef: Practical coding for everyone
:neutral_face:

12

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

13

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

14

Your AC code
https://www.codechef.com/viewsolution/39287506

15

Can we do it in O(n) ?

16

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

17

maybe not in O(N), but we can do in O(Nlog(1e9)).
my solution :
https://www.codechef.com/viewsolution/39280532

18

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,
python 3.x - what's the differences python3 and pypy3 - Stack Overflow.

1 Like
19

can someone tell me what’s wrong in my solution:
solution link => CodeChef: Practical coding for everyone

20

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