I hope this will work now.Also above logic is incorrect if row is not sorted before calling recurse I think.
The reason for this is that while calculating RIGHTMASK from LEFTMASK we assume that all elements not in LEFT are at right but for cases much smaller than (1<<n) we have not included that element and if not sorted this may use an element which was not at all considered
Your solution is working fine but i don’t know why it’s getting more time which will definitely time out in 2 sec.
It’s python
Time limit will be 10s I think 
Anyways still if it’s TLE you can try C++ with Fast IO
I didn’t get any reply from the question setter till now. This is the reason why i call certain people dumb.
@hruday968, calling another person dumb for not replying makes no sense. It was harsh on your part. I did not visit codechef for some days now and also the question appear on the first page, so that I could come to know about it. About your anger, I saw your code and see the editorial carefully, it uses bitmasks and bitwise operations, which are O(1) everywhere. Refer to my code for it.
Regarding your code, I saw it too and ran it locally and on online judge regarding the last test cases, it is very slow due to the O(n) operations which you do every time, instead of the O(1) bitwise operations. Also, every call of the recursive call you make has a O(n logn) factor due to the power function call you make (along with the costly mod operations, which is not needed anyway). This just makes the case worse, I tried atleast that part and it passes the second las test cases now. Here is your optimsed code : UJbC9p - Online C++0x Compiler & Debugging Tool - Ideone.com
Last few things, if you don’t know them. First of all increasing memory sizes just makes things worse, especially in recursive written codes as there are almost all cache misses. A code written with all bitwise operations only works amost 3-4 times faster, allowing even 2-3*{10}^{8} operations to work even in 1 sec.
The reason is simple, the processor has frequency in Gigahertz, meaning ideally it can perform {10}^{9} operations, but doesn’t operation so much due to absence of perfect pipeline models, all operations having different executions times, false prediction of some instructions etc. The case becomes worse with costly operations like multiplication, division and modulo. It is easy for bitwise operations to work faster as all the computers are built on bits only, meaning all operations nearlly take same time and pipelining is effective.
Lastly, my own code runs with 0.53 sec on all test cases. Setting time limit to 4 times my code is the best I could have done to allow even some slow code with less bitwise operations written to pass. I hope you get your mistake and atleast check the setters code next time before you put blame on anyone next time.
One last thing I missed about the constant factor in your code it that you make unnecessary calls to same function, like using “i and j” and “j and i”. This is also changed int he ideone link which i gave you. Actually, the time complexity will be O(2^n * n * (n-1) / 2), which I think clearly explain why the above constraints eailly fit into time.
Regarding solutions which work in 0.00 sec, have all find the problem online which gives a greedy and optimal approach for all cases. I understand that it was my fault to not check whether this problem already exists or not. But it is still ok as the contest was meant for school children and meant to teach them some tricks like dynamic programming which is clearly stated in the editorial too.
@alexander86, your solution is correct it seems. One of my friend who solved this question in the contest using similar approach, gave a link to this paper for reference.