You are not logged in. Please login at www.codechef.com to post your questions!

×

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.

asked 11 Dec '17, 15:43

ashutosh450's gravatar image

6★ashutosh450
547211
accept rate: 37%


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.

link

answered 11 Dec '17, 15:54

bhola_nit's gravatar image

5★bhola_nit
2015
accept rate: 0%

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

(11 Dec '17, 16:22) shivhek254★

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?

link

answered 11 Dec '17, 17:58

dhanush_m's gravatar image

1★dhanush_m
413
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) vivek_19982996★

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) ashutosh4506★

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) vivek_19982996★

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

(12 Dec '17, 00:59) ashutosh4506★

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

(12 Dec '17, 09:22) vivek_19982996★
(12 Dec '17, 09:26) vivek_19982996★

Things like these hurt during a contest!

(13 Dec '17, 15:18) ashutosh4506★
showing 5 of 7 show all

The same thing happened to me

link

answered 11 Dec '17, 15:47

madhav_1999's gravatar image

5★madhav_1999
662
accept rate: 20%

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

link

answered 11 Dec '17, 16:20

shivhek25's gravatar image

4★shivhek25
585
accept rate: 0%

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

link

answered 11 Dec '17, 16:49

tanujyadav997's gravatar image

1★tanujyadav997
1
accept rate: 0%

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

link

answered 11 Dec '17, 17:20

shubhu1596's gravatar image

5★shubhu1596
111
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) vivek_19982996★

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) shubhu15965★

Unordered map also gives tle

(12 Dec '17, 09:25) vivek_19982996★

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

link

answered 11 Dec '17, 19:02

bka_hackman's gravatar image

5★bka_hackman
1
accept rate: 0%

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

(11 Dec '17, 19:27) ashutosh4506★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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