CHEFEXQ - O(NQ) solution in PyPy.

general
, ,
2

The same thing happened to me

3

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
4

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

5

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

6

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

7

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
8

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

9

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

10

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

However with pypy AC in ~1.5 seconds.

Wth!!!

11

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

12

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

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

13

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

14

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

15

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.

16

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

17

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

18

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

19

Unordered map also gives tle

20

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

21

Things like these hurt during a contest!