Hi there,
Both my python and C++ code for the problem exceeded the time limit 
I don't know how am I to optimize it any further.
Will anyone have a look at it and suggest any optimizations, change in logic, etc ??
Thanks
Python code:
Got AC
Apr '10
Jul '22
cout ,cin is slow.
vector push_back is little slower
map is slow.
Try changing these.Hope you wont get TLE.
I replaced cin,cout with scanf,printf.
also took away the needless vector and replaced it with an integer array.
Not sure what will be a faster replacement for map.
Are you talking about a faster STL container, or should I implement a map using a basic integer array.
The problem is that I will have to take care of negative indexing as well in that case
My TLE code in C++ as it stands now after the modifications:
Got AC
I rarely use maps (so can't comment how fast/slow it can be) but you can use arrays to solve the problem. Sort them and use binary search. It will give you AC.
I didn't want to use sort and then a binary search as it would have made it an O(n^3logn) algorithm, while the one using maps is an O(n^3) algorithm, though compromising on space.
Strange though that an O(n^3logn) algorithm should get AC over an O(n^3) one.
You can just use vectors instead of map.
sort and do binary search.
your 2nd nested loop is unnecessarily increasing the constant factor.
using maps is an O(n^3) algorithm
Wrong.
Insertion takes place in O(lg n)
As dormant said using maps doesn't make it an O(n^3) algo as the insertions take O(lgn) time. Hence essentially its an O(n^3lgn) algo as well.
If you want to avoid binary search you can do that even after using arrays.
Sorry, not being acquainted with STL quite that well. I somehow assumed map is akin to a hash map, but later came to know insertion takes O(logn) as it keeps the objects in sorted order, which is not needed for my code.I also saw somewhere the mention of a hash_map/unordered_map and supposedly it has been included in the TR1, but I wasn't able to use it.
Anyway, this time, I took each side in two arrays, sorted one of them and looked up each element of the other in this, appropriately increasing count as we go.
Also since there might be more than one match in the sorted array for any particular element, I had to use while loops to count all the matches on either side of the match returned by a binary search.
Things did not go well though, as it successfully TLE'd this time as well
Is it because I used STL's implementation of sort and bsearch ?
Here is the code
Ok, I think I am unnecessarily taking the evaluated RHS in an array and then looking up each element of it in the LHS.
Instead, as and when I generate the RHS in my second loop, I can bsearch it in the LHS, and increment count.
I think this will save significant amount of time.
Hello:
This problem has a very strict Time Limit. So, what to change in your code?
Right now, you're trying to do one binary search and then finding where the sequence ends in O(m) (where m is the numbers of equals elements). Nevertheless, this m could be big enough to make your algorithm really slow. So, what to do? In the first place, do a binary search for looking an appearance of the number W. Then, find a number W+1, witch should be next to W (if it doesn't exist, then fix your binary search to make the function return the index even if the number W+1 doesn't exist). Then you have both indexes, the starting index and the finish index of the sequence of W.Warm Regards
According to your python-solution:
It is nearly impossible to get a python solution AC. So far my python solution is the only one and it needed a lot of optimizations.
You are doing the same thing as I did except that :
1) I removed all repeats from the LHS array and kept a count of the repeats in a separate array.
2) I used one binary search.
I used qsort in C and it got accepted. qsort is slower than STL sort (I came to know about it while solving SUMFOUR).
Hence you should be able to solve it using sort. Try the above changes. It may get you AC.
Finally got AC 
Two optimizations used -
1) a*b+c is same as b*a+c, optimized 2nd nested for loop to start from a instead 0 and counted twice, similar for d*(e+f) = d*(f+e)
2) skipped process for d = 0
Got AC after a LOT of submissions, sure feels good 
