ECPC10A - Editorial

editorial
, , ,
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

21

x = a ^ b, a < b,
lets k is msb bit of a,
now x > max(a, b) iff kth bit of b is 0.

for each Ai , kth bit of Ai is 0, then we have to count Aj such that k is msb bit of Aj.

2 Likes
22

Line #7 for j in range(x):
you need to use
for j in range(i, x):

If it still doesn’t work then sort the list then use
if (arr[i] ^ arr[j]) > arr[j]: count += 1

23

Got it. Thanks

24

getting wrong answer and no one is successful solution in python.
check here => CodeChef: Practical coding for everyone

25

#include
#include <bits/stdc++.h>
using namespace std;

int main()
{ ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
unsigned int t,n=0,count=0;
unsigned c=0;
cin>>t;
while(t–)
{
cin>>n;
vector v(n,0);
for(int i=0;i<n;i++)
cin>>v[i];
sort(v.begin(),v.end());
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
c=v[i]^v[j];
if(c>v[j])
{
// if(c>v[j])
++count;
}
}
}
cout<<count<<"\n";
count=0;
// c=0;

}
// your code goes here
return 0;

}