python bisort

[Sai Teja Pratap]

I was solving this challenge in hackerrank. https://www.hackerrank.com/challenges/triplets . I tried an  N*log(N)*log(INT_MAX) solution in c++. It timed out. But my python code [ O(n^2) ] was accepted. (An O(n^2) in python beats NlogN in C++ ! , n=10^5)

My Algo:

For each element in the input array, find the number of elements to its left which are smaller and the number if elements to its right which are bigger (using insort,bisect_left). 

Summation of product of the two values for each element in the array will be the answer. [This works assuming there are no duplicates; But duplicates can be easily handled]

If anybody  wants the actual code, drop me a mail. 

I used a python module called bisect. The relevant functions are 

insort(arr,ele) : adds ele into arr (has to be sorted) and makes sure that the arr is sorted

bisect_left(arr,ele) : similar to c++ lowerbound (binary search). 

I've gone through the source code of bisect and found nothing amazing. Simple and plain implementation of the obvious. 

Am I missing anything?

Attachments : 

bisect.py,_bisectmodule.c : source code of bisect.

--

Sai Teja Pratap,

about.me/stp

[Mayank Meghwanshi]

https://www.hackerrank.com/environment

May be because they have different time limits for different languages.

--
--
The website for the club is http://stab-iitb.org/wncc
To post to this group, send email to wncc...@googlegroups.com
 
---
You received this message because you are subscribed to the Google Groups "Web and Coding Club IIT Bombay" group.
To unsubscribe from this group and stop receiving emails from it, send an email to wncc_iitb+...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

--

Regards,

Mayank Meghwanshi

3rd year B.Tech. Student

Computer Science and Engineering Department

IIT Bombay

[Dilawar Singh]

>be the answer. [This works assuming there are no duplicates; But duplicates
>can be easily handled]

Nice algo and good effort. But how will you handle duplicates "easily" (By
'easy', do you mean in linear time?). My understanding is that you can't do it
in linear time.

--
Dilawar
NCBS Bangalore
EE IIT Bombay

[Sai Teja Pratap]

@mayank : The longest test case took 3 secs.

@Dilawar: 

Each element can occur atmost two times .

___x__x___

Let s1,s2 be the number of elements smaller than x in red,yellow regions

     b1,b2 be the number of elements bigger than x in yellow,pink regions

If we follow the algo I mentioned naively, we get a sum of s1(b1+b2) + b2(s1+s2) for these 2 positions of x.

s1*b2 is counted twice. So for each element that appears twice subtract from the sum the value of s1*b2. 

For this we need to maintain the array positions of each value. I used a dict (defaultdict to be more precise) for that. That is not O(n) exaclty. But somewhere close (python uses hash for dicts).

--
--
The website for the club is http://stab-iitb.org/wncc
To post to this group, send email to wncc...@googlegroups.com

--- You received this message because you are subscribed to the Google Groups "Web and Coding Club IIT Bombay" group.

To unsubscribe from this group and stop receiving emails from it, send an email to wncc_iitb+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.

[Manish Goregaokar]

Haven't yet looked at the algo, but this might be a combination of the different environment constraints AND python being awesome at certain types of computations. In general, python is supposed to be slower, because it is interpreted, but that need not always be the case. Try calculating 1000! in both python and C++.

-Manish Goregaokar

To unsubscribe from this group and stop receiving emails from it, send an email to wncc_iitb+...@googlegroups.com.