×

# CHEFEXQ - O(NQ) solution in PyPy.

 3 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. asked 11 Dec '17, 15:43 547●2●11 accept rate: 37%

 1 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. answered 11 Dec '17, 15:54 201●5 accept rate: 0% I faced the same thing and the maximum time taken by my code was 14.97. (11 Dec '17, 16:22)
 1 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? answered 11 Dec '17, 17:58 41●3 accept rate: 66% 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 (11 Dec '17, 18:14) 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 : https://www.codechef.com/viewsolution/16429397 (11 Dec '17, 19:25) 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. (11 Dec '17, 19:32) Can i get the link to that solution (segprod) ? (12 Dec '17, 00:59) Sorry!! I did a large no.of submissions for that sum,so its pretty hard to find it (12 Dec '17, 09:22) This is that guys solution: https://www.codechef.com/viewsolution/16185616 (12 Dec '17, 09:26) Things like these hurt during a contest! (13 Dec '17, 15:18) showing 5 of 7 show all
 0 The same thing happened to me answered 11 Dec '17, 15:47 66●2 accept rate: 20%
 0 I guess we all should consider switching to PyPy in this case. :p answered 11 Dec '17, 16:20 58●5 accept rate: 0%
 0 Even in java O(NQ) solution gave 100 points. answered 11 Dec '17, 16:49 1 accept rate: 0%
 0 This is disappointing for those who used the correct approach(SQRT decomposition) to solve this problem. answered 11 Dec '17, 17:20 11●1 accept rate: 0% Actually sqrt decomposition solution is also getting tle with c++. However with pypy AC in ~1.5 seconds. Wth!!! (11 Dec '17, 17:23) My solution for c++: https://www.codechef.com/viewsolution/16406428 My pypy solution: https://www.codechef.com/viewsolution/16409970 (11 Dec '17, 18:18) 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 (11 Dec '17, 19:36) Unordered map also gives tle (12 Dec '17, 09:25)
 0 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 answered 11 Dec '17, 19:02 1 accept rate: 0% And in python, the brute method will get you 100pts :D (11 Dec '17, 19:27)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,408
×188
×161

question asked: 11 Dec '17, 15:43

question was seen: 1,222 times

last updated: 13 Dec '17, 15:18