OpenAI has just released a large number of amazing research results in math and computer science. The official post is at https://openai.com/index/sharing-ai-progress-in-mathematics/ and the repository is at https://github.com/openai/math

It will take a long time to digest, but it seems there are over 700 papers of significance in their respective areas, including proof of Unique Games Conjecture, better bounds on the matrix multiplication exponent $$$\omega\le\frac{9}{4}$$$, and L=RL.

One formulation of the 3-SUM problem is determining whether a set of $$$n$$$ integers has a subset of $$$3$$$ integers that add up to zero. With hashing, this takes $$$O(n^2)$$$ time and was conjectured to be optimal.

The all-pairs shortest paths problem (APSP) is determining the shortest path between all pairs of vertices in a graph with $$$n$$$ vertices. Floyd-Warshall uses $$$O(n^3)$$$ time and was conjectured to be optimal.

It seems possible that neither of these conjectures is true, declared by the paper https://arxiv.org/pdf/2610.06783 using an internal model of Claude and verified using Lean.

I'm looking for a data structure or subroutine that takes in a sorted list $$$L$$$ of $$$n$$$ integers and a list $$$Q$$$ of $$$n$$$ integers. For each element $$$q\in Q$$$, we should report the largest remaining element in $$$L$$$ smaller than $$$q$$$ and then remove it (or we can report $$$-1$$$ if no such integer exists). I would like the entire process to take $$$O(n \log n)$$$ time.

My understanding is that this approach is necessary for today's 2254E - Chronostasis, but many user-accepted Python solutions seem to implement Fenwick trees, which I believe might be too complicated for a Div. 3 contest and not the intended solution (though I could be wrong).

Hi there,

Someone much more knowledgeable than me warned about using sets and dictionaries in Python as they can be hacked. I somewhat overlooked this advice as I assumed no one would hack a random pleb, but then I saw a warning in the editorial of 1915E - Romantic Glasses at https://codeforces.me/blog/entry/123952 state "Be careful about using hash tables, as they can be hacked."

One of the responses in that thread linked to https://codeforces.me/blog/entry/62393 which provided some insights and workarounds for C++, but is there such a resource for Python? Is there a general rule of thumb for using such data structures and finding the appropriate problem-specific alternative (such as a list of tuples, which will often do)?

Thanks in advance!