CP leetcode strategy

Context

A month ago I went to a programming competition in Cork, very fun, but very difficult for me, my only experience with that kind of problem solving, was only through leetcode, I'm not even that bad at leetcode. To go straight to the point I found it very intresting and I want to imporve (yes probably it is useless) but it seems to me like a fun game.

I started to do some training on kattis website, is not as serius as code force but is still something (and I like the cat), but I felt like I was just spending too much time tring to come up with a pattern that maybe I just needed to have studied before, so I did the most inteligent thing to do and I asked my Friend LLM (BIG BOSS Gemini) for an algorithmic strategy to apply every time i try to solve a problem.

Strategy

-1) Don't waste your effort: keep track of your work:

I keep track of my solution and pattern used inside a google sheet.
This is my google sheet as example.
I think the most important colum is the Note setcion: where I bully myself when i do some silly errors.

0) Time constrantis (1hr):

30 min max to think about a valid approach.
10 min max to write the code solution.
20 min left ask LLM for a solution (if you did not find it) or for a better solution.

1) Stroy vs Logic

Ignore the story (just skim through it).
Try to understand as fast as possible which is the key question i.e. (is a graph question? is it a array question? etc...).
For god sake read really good the output section to understand how to parse the input (i.e. how many test case are etc...) and what you need to output for each one.

2) Check the limit of N to understand which apporch suits better

The time limit on kattis is usually 1 cpu second but you can check it for each task in the section metadata.
I'm using python because this is a game for me, if you are using C++ you are probably a tryharder and this is not the right article for you.
According to my LLM of trust python3 can do between 10 million or 20 million operation per sec.
That is an interval that looks like this: [10^7,2*10^7].
We can use this information to get for each time complexity the max number of input size computable into a CPU second.
If you want to read out the maths it is in the last section of this post but I will summurazie the info in a simple table here:

Calculated Max Size of \( N \)	Accepted Complexity	Likely Algorithms
\( N \le 10 \)	\( O(N!) \)	Extreme brute force, Permutations (e.g., Traveling Salesperson).
\( N \le 20 \dots 23 \)	\( O(2^N) \)	Backtracking, Searching all subsets (e.g., Subset Sum).
\( N \le 200 \dots 500 \)	\( O(N^3) \)	3-state Dynamic Programming (DP), Dense graphs (Floyd-Warshall).
\( N \le 3000 \dots 5000 \)	\( O(N^2) \)	Nested `for` loops, Basic DP (e.g., Longest Common Subsequence).
\( N \le 10^5 \dots 5 \times 10^5 \)	\( O(N \log N) \)	90% of problems. Sorting, Heaps, Advanced Binary Search, Dijkstra.
\( N \le 10^6 \dots 10^7 \)	\( O(N) \)	Two Pointers, Greedy algorithms, BFS/DFS, Hash Maps, Linear Arrays.
\( N \ge 10^9 \)	\( O(\log N) \) or \( O(1) \)	Pure math formulas, Binary Search on the answer space. You cannot use arrays of this size!

3) Analyze Edge cases

Once we have an idea on the algorithm to use we need to ask ourself were it could break?:
What happens if N = 0 or N = 1?
Is there any negative number (i.e. if yes Dijkstra doesn't work)
What happens if are the elmenet are the same
Can the graph be discontected? etc...

4) Mock run on the Test case

Never start to code before solving the Test case on the whiteboard.
If the input example is too easy try to think of a better one that can include also edge cases.
Some times completing the test case is very time consiuming (i.e. fulltank on kattis) if it is the case once you have to main understading go for it.

Math in details for time complexity and input size limits

Each time complexity is the number of operation our alogrithm does with an input of size N, so we need to lock that to be less then or equal to 10^7 (the number of operation that python does into a CPU second) then solve di disequation to get the range of input size of which our alogithm can run in just a CPU second, the last value is the max input size acceptable.

\( \displaystyle \begin{aligned} (1) \quad &\mathcal{O}(\log N) \implies \log_2 N \le 10^7 \iff N \le 2^{10^7} \implies N_{\max} \to \infty \\ \\ (2) \quad &\mathcal{O}(N) \implies N \le 10^7 \implies N_{\max} = 10^7 \\ \\ (3) \quad &\mathcal{O}(N \log N) \implies N \log_2 N \le 10^7 \implies 10^5 \cdot \log_2(10^5) \approx 1.66 \cdot 10^6 \le 10^7 \implies N_{\max} \approx 10^5 \\ \\ (4) \quad &\mathcal{O}(N^2) \implies N^2 \le 10^7 \iff N \le \sqrt{10^7} = 10^{3.5} \approx 3162 \implies N_{\max} \approx 3000 \\ \\ (5) \quad &\mathcal{O}(N^3) \implies N^3 \le 10^7 \iff N \le \sqrt[3]{10^7} = 10^{\frac{7}{3}} \approx 215 \implies N_{\max} \approx 200 \\ \\ (6) \quad &\mathcal{O}(2^N) \implies 2^N \le 10^7 \iff N \le \log_2(10^7) = 7 \log_2(10) \approx 23.2 \implies N_{\max} \approx 23 \\ \\ (7) \quad &\mathcal{O}(N!) \implies N! \le 10^7 \iff \begin{cases} 10! \approx 3.6 \cdot 10^6 \le 10^7 \\ 11! \approx 3.9 \cdot 10^7 > 10^7 \end{cases} \implies N_{\max} = 10 \end{aligned} \)

You may notice that the limits in the table are a bit larger that because a lot of the times for example an N^3 algorithm dosen't actually run 3 full cylce but a bit less in each cycle. (DEPENDS ON THE ALGORITHM IMPLEMENTATION).

Thanks to

Gemini for the big cool table and latex code.

PS: I did not make it review my grammar so this post grammar is going to be shit but it's late and it's my website so I do whatever i want :)