 # 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. 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).

And in python, the brute method will get you 100pts 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