Comment by eru

I'm not varjag, but I can give you a flavour of the problems I've tried:

---

Here's an algorithmic problem:

You are getting a stream of n unsorted number (say over a network socket, but it doesn't matter). You don't know n upfront. We want to find the k largest numbers in that stream.

You can use O(n) time and O(k) space. We are in the comparison model.

The items arrive one by one, if you want to refer to any earlier item, you need to store it yourself (and it counts against your O(k) budget.)

Is this possible? If yes, please give me the algorithm. If not, please sketch a proof showing that it's not possible.

---

The above is indeed solvable in linear time, it's fairly easy for a human to figure out. Another one (and this on is rather hard, took me a few years and I'm writing up a paper):

---

Here's an algorithmic problem:

You are given a sequence of opening and closing parens. Each item in the sequence has a positive weight. We want to find the _heaviest_ balanced subsequence in linear time in the comparison model, or prove that this task is not possible.

I'm ok with randomised algorithms. In that case, I want expected worst-case linear time, where the expectation is taken over the random bits and the worst-case over the inputs.

---

The above task is really solvable in linear time, and even deterministically. But so far no AI model has beaten it. As far as I can tell, it's a new result, despite looking fairly elementary.