Solving 977C - Меньшие или равные I stumbled over a TLE:

Submission: 80761653

After digging into this I found out that the code gets accepted if the array is expanded by just one element.

Submission: 80762181

Ok, so when sorting an array the time needed for sorting obviously depends on the size of the array, but I'm really surprised to see that increasing the size by one might make the difference between '218ms' or TLE.

I did some local tests, there are some variations but not that significant.

So maybe a layer 8 problem? Am I missing something?

Edit: Not surprising others have written about this in more detail:

• https://www.geeksforgeeks.org/java-handling-tle-while-using-arrays-sort-function/
• https://www.geeksforgeeks.org/when-does-the-worst-case-of-quicksort-occur/

Even here by Flatfoot

• https://mirror.codeforces.com/blog/entry/7108

I think I knew that sorting algorithms have best- and worst-case behaviors. It's just that I'm still blown away that corner cases are so close to 'average' behavior. And still I don't see a pattern which would have signaled this.

My key takeaways

Other people are smart too. With my current rating of #1271 at least 80% of the active accounts are more efficient in solving contests.

Do I mind? Ask Hulk!

OK, seriously: My key takeaways

Speed is key, get all obstacles out of your way.

In my case of a java developer and IntelliJ user it meant installing Egor Kulikov's CHelper. Be sure to manually install the latest beta version.

Besides this I find Jasper van Merle's Chrome Plugin Competitive Companion very helpful. It's a one click to parse a problemset and start coding in the IDE.

Speed is key, for now solving the easy faster is more important than solving the harder.

The Filter on the Problemset page is great to find the right problems to practice on. Keep an eye on the sorting and use the 'tag' function to search for more specific.

If you get stuck on a problem, like you don't have a clue after half an hour, don't hesitate to read the Tutorial that the contest provides.

Once your submission got accepted might be a good time to check how others approached the problem. The status page of a problem, e.g.: Problem 4A — Watermelon allows to do just that. The link in the first column on that page leads to that specific submission. The filter allows to select for the programming language and the sorting helps to find solutions that were faster or used less memory.

Speed is key, try to get it right in you mind before you run the tests.

I have a tendency just run the tests to find out how far off my current solution is. It might be more efficient to get things right in your head before doing that. Even worse are debugging sessions, so take a step back if you find yourself doing the DebugSteppingDance.

mf

Habit

I'm starting to establish a habit of video streaming when I work on competitive programming problems.

The stream can be found on twitch: https://www.twitch.tv/eigenfunk

What to expect

Look at my rating stats. :-)

I entered code forces as an "specialist" and seriously thought: Piece of cake, couple of weeks and I'll be in the red zone! :sunglasses:

Turns out I'm not (-:

What realy to expect

So it is obvious, that there will be no bleeding edge educational best practice competition deciding content there.

Rather you will see me struggle with the given problems. Sometimes I succeed, sometimes I don't.

Maybe that is closer to your situation, so the biggest benefit for you might be seeing that you are not alone, there are others struggling too.

Or maybe it is relieving to you, that you don't have to embarrass yourself, because somebody is already doing that for you. (-:

See you there.

Next attempt

Codeforces Round 639 (Div. 2) on -- t.b.a. --