Better algorithm for 1351

[yjian012]

Yeah I know it's easy, but I found a possibly more efficient algorithm, especially when m>>n or n>>m.
It's explained here: https://hyper-meta.blogspot.com/2023/06/m1318-description-given-3-positives.html
Let me know what you think!

[yjian012]

BTW I found this repo from your submission of 1792, but I feel like the worst time complexity should be O(n^2), because half of it looks just like quick sort, and if you're really unlucky and each time you choose the minimum, and you can't update the array, you end up sorting the entire array in ~n^2 operations. Or maybe you mean average complexity? I'm not sure how that is computed.

P.S. I thought I was the first one that discovered the O(n^1.5) algorithm for 1269, didn't know that it was found a couple years before! Can't wait to find more cool stuff!

[hqztrue]

You are right. I was sometimes not very careful when the two parameters n and m are not balanced.
Another viewpoint of your algorithm is to perform exponential search on the rows. The running time is \sum_{i=1}^n log d_i where d_i is the difference between the boundary on the i-th row and the (i-1)-th row. We have \sum_i d_i=m, by convexity the running time is O(n log (n/m)).

[hqztrue]

For the question related to 1792, usually we are considering the expected time complexity for quicksort and its related variants (which has formal definitions, and is slightly different from the term "average complexity"). It's true if you consider the worst complexity, it can degrade to n^2.

For 1269 we can do O(sqrt(n) polylog n) (after a series of discussions in my previous articles), but it's quite complicated.
Your algorithm is interesting and is different from the ones I know.