conqueror_of_tourist's blog

By conqueror_of_tourist, history, 9 months ago, In English

In the recent Goodbye 2021 Round on Problem E my code seems to run a lot slower when running on pypy64 as opposed to regular pypy.

The following submissions are identical, with the exception being the language used.

141113239 (pypy3.7 — AC 732ms)

141185703 (pypy3.8 64bit — TLE)

Running on Custom Invocation on one testcase of size $$$10^5$$$ shows that pypy3.7 will take about 250ms whereas pypy3.8-64 will take 5600ms.

Profiling my code it seems like the culprit is my find function

#Finds smallest index of segtree such that seg[ind] <= x
#Only works if func = min
def find(self, x):
    curr = 1
    
    if self.data[curr] > x:
        return -1
    while curr < self._size:
        assert self.data[curr] <= x
        if self.data[2 * curr] <= x:
            curr = 2 * curr
        else:
            curr = 2 * curr + 1
        assert self.data[curr] <= x
    return curr - self._size

Replacing this function with a trivial (but incorrect) function makes the submission run in ~230 ms in both languages. However it seems like this function should run in $$$O(log n)$$$ and not be 20x slower than the rest of my code (and if itis slow, why is it not an issue in 32bit pypy?). If anyone can figure out the issue here (and what I need to avoid to be able to run code in pypy64 quickly) it would be greatly appreciated.

Read more »

 
 
 
 
  • Vote: I like it
  • +82
  • Vote: I do not like it

By conqueror_of_tourist, history, 21 month(s) ago, In English

On January 30th, 2021, CMIMC (based in Carnegie Mellon University) will be hosting our very first programming competition! The contest has been written by our problem writing team, including FlakeLCR, Gilwall, and conqueror_of_tourist. Our website is www.cmimcprogramming.org. Registration is open now to January 16th with no registration fee! If you would like a t-shirt for the competition, fill out the form by January 3rd. Please note: this competition is official for high school students only.

Below is more information on each round. You can find more information and sample problems on the info tab of our site.

In the AI Round, you and your team write programs which play mini games against other teams. Your scores will be updated on a live leaderboard, and you’ll be able to update your strategies accordingly! You will have 3 hours to write and improve your code for 3 different mini games. All code should be written in Python 3.

In the Optimization Round, you and your team will work on 3 optimization-based problems over 3 hours. These problems are not intended to be solved perfectly — instead, you will be competing against other teams to get the closest approximation through any computational tool at your fingertips. Your score will be determined simply by your answer. You can use any programming language for this round, since you will only be submitting a text output.

Stay tuned for further updates! If you have any questions, please reach out to us at contact@cmimc.info.

Note: If you're not a high school student you can still sign up, you just won't be eligible for prizes.

Read more »

 
 
 
 
  • Vote: I like it
  • +59
  • Vote: I do not like it