It’s python
Time limit will be 10s I think 
Anyways still if it’s TLE you can try C++ with Fast IO
@admin the practice links for every problem in this contest are invalid. The page exists but says “Problem is not visible now. Please try again later.”
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.
2 Likes
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 : https://ideone.com/UJbC9p
2 Likes
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.
2 Likes
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.
1 Like
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.
2 Likes
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.
1 Like
In contrast to the claim in the tutorial I think that there is a greedy solution.
Maybe I am wrong, but at least my solution passes all test cases and my random case generator does not find a case where my output and the output of setter solution differs.
My solution runs in O(N \log(N))
Idea:
- Sort the times (Here is N\log(N) needed - remaining steps are linear)
- while there are more than 3 people on the left side Ship the slowest two people to the right by
- either the fastest person and the slowest person go to the right, the fastest goes to the left (two times)
- or the fastest TWO persons ride to the right, the fastest goes back, the slowest two people go right, the second fastest goes left
- Now only 1, 2 or 3 persons are left
- The fastest person rides to the right (with one of the remaining persons if there is any)
- if there is still a person on the left side the fastest goes back to the left and then goes right with the remaining person.
4 Likes
@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.
2 Likes