CHEFEXQ - O(NQ) solution in PyPy.

With a bit of optimization, my O(NQ) solution (which got TLE in C++ for the second sub task of CHEFEXQ) in PyPy (python) fetched me 100 pts. Can anyone explain the plausible reason behind this ? Were the test cases weak or the TL in PyPy was exceptionally high ?

Here is the LINK to my solution.

3 Likes

The same thing happened to me

Generally the time limit given in pypy is 5 times what they gave in c++.

In C++ it was 3 seconds. For pypy it was 15 seconds. The maximum time taken by any subtask was around 14.75 sec. Little bit more would cost TLE.

I dont know the exact answer why it happened. 15 sec allowed might be the reason, which is much for pypy atleast for this question.

1 Like

I guess we all should consider switching to PyPy in this case. :stuck_out_tongue:

Even in java O(NQ) solution gave 100 points.

This is disappointing for those who used the correct approach(SQRT decomposition) to solve this problem.

I solved the problem in C++ itself. Didn’t get any TLE.
Here’s my solution
CHEFEXQ solution

I solved it through square root decomposition method.
Could you share your C++ code?

1 Like

If you use sqrt decomposition in C++ using Map , you will get TLE .
Instead , use sqrt decomposition in C++ using normal array with enough space , it will pass . No memory limit exceeded occurs in this case .

My Solution in C++ :Soln

I faced the same thing and the maximum time taken by my code was 14.97.

Actually sqrt decomposition solution is also getting tle with c++.

However with pypy AC in ~1.5 seconds.

Wth!!!

Thanks!!
Most of the part is same.
Except i used map.
Plz if u could see what more optimisation could be done to this code.
I tried faast input also.

My solution:
https://www.codechef.com/viewsolution/16406428

My solution for c++:
https://www.codechef.com/viewsolution/16406428

My pypy solution:
https://www.codechef.com/viewsolution/16409970

Square root decomposition is the proper method to solve this question. So you will get AC with 100pts. I was talking about the O(NQ) solution which gave TLE in C++ but passed all test cases in PyPy (python).
Link : CodeChef: Practical coding for everyone

And in python, the brute method will get you 100pts :smiley:

The same thing happened in previous challenge(NOV Challenge) in question segprod where simple sparse table in pypy got AC ,whereas in C++ that code could not pass a single subtask.

Thats because you are using map (amortized O(logn) insertion and O(logn) look up ) a simple 2d array (O(1) lookup)or unordered_map would give perfect ac …my solution took only 0.57 sec

https://www.codechef.com/viewsolution/16471550

Can i get the link to that solution (segprod) ?

Sorry!! I did a large no.of submissions for that sum,so its pretty hard to find it

Unordered map also gives tle

This is that guys solution:
https://www.codechef.com/viewsolution/16185616