Understanding the Competitive Programming problems

Before starting this article, I thought: This would be easy! everything is on my head.

Actually, that's true at least for the basic part and from my perspective based on my experience. Nevertheless, I realized the complexity when I started to write it 🤡. Then, I google what is a competitive problem and the I'm feeling lucky got me the following definition on Wikipedia:

"Competitive programming is a mind sport usually held over the Internet or a local network..."

What? mind sport? 🙀 it's true but I have been never realized that fact. Then, I clicked on each link inside the Wikipedia page and, after a couple of hours of procrastination on Wikipedia, I decided to continue with the writing.

A long time ago, and sometimes using a diskette at my University, I started in the world of competitive programming. Why? Because it represented a huge challenge in a healthy competition with colleague classmates. The name of my team was root?destroy:0; 🦾

Maybe it is possible to classify the competitions in short-term (1-5 hours) and long-term (2 days to few months). Here I will describe the short-term.

The notable ones are the International Collegiate Programming Contest (ICPC), the International Olympiad in Informatics (IOI), IEEE Extreme, Google CodeJam, and many others. Different tech companies run their own programming contest to discover new talents also to contribute to the community. Back to the ICPC, according to its official site:

The International Collegiate Programming Contest is an algorithmic programming contest for college students. Teams of three, representing their university, work to solve the most real-world problems, fostering collaboration, creativity, innovation, and the ability to perform under pressure. Through training and competition, teams challenge each other to raise the bar on the possible. Quite simply, it is the oldest, largest, and most prestigious programming contest in the world.

Well, this was the kind of competition where I participate (besides the online ones). As a foundation you need to know several well-known algorithms and how to combine them to solve a problem...Uh-huh, but how do you achieve that? practice, practice, and practice. My first problem was the classic problem # 100 - The 3n + 1 problem in the site of Valladolid University, Spain called UVa Online Judge, which is referring to the Collatz conjecture.

Do not hesitate about it! The classic structure of this kind of problems is composed of:

• Description of the problem: what do you have to solve?, sometimes described as a story or explaining an hypothetical initial setup 👽 👾 🤖
• Input: description of how will be the expected input for the problem, specifying the range values or not (e.g. 32-bits integers, alphanumeric string)
• Output: the expected output for the problem, a number, a phrase, or just a True/False. Also, it could be something complex as an ASCII image!
• Limitations: whether memory and time limitations are limited to avoid brute-force approaches or classic ones 😧

Generally, each competition has its own rules about who is the winner. Most of them consider the winner who solves more problems in less time. Of course, everyone receives a problemset each one has to submit its solution to be evaluated. The solution is marked as accepted (AC), wrong answer (WA), time limit exceed (TLE), among others. As I mentioned, this depends on each competition 👩🏻‍💻 👨🏻‍💻

During the competition, it is possible that you need to define:

• Strategy to use: cooperative strategy with your team
• Identification of the problem: the problem fits in any previous problem that I solved? can I classify it as easy/medium/hard? can I describe some techniques to solve the problem?
• Analysis of the solution: time complexity vs. memory complexity
• Check the extremes cases: verify carefully the border problems according to the input/output.

By experience, many problems will fit into a knowing solution for you/your team in different categories: math, dynamic programming, graphs, sorting, searching, string processing, ad-hoc. Then, after writing your code, just try to break your code! Remember that your code will be evaluated by an automatic system that compares an input (several cases including which push the limits) with the expected output, then your code has to run properly and get the right answer 🐵 🙈 🙉

There are several websites where you can practice such as HackerRank, CodeChef, Codeforces, TopCoder, Coderbyte, Project Euler, Exercism.io, Codewars, SPOJ, CodinGame, and others. Eventually, you will evolve into a master of coding with skills as abstraction, faster typing, addiction to munchies (snack food), work under pressure, and others.

Now, in my opinion, this could be risky for the (probably) lack of knowledge in frameworks used in real-life projects. However, why so many companies used this kind of approach in interviews? I am wrong on my thought? Not totally, a profile of this kind of software has several characteristics very useful into the industry. There are several tech companies that use competitive problems to select possible candidates. We are clear that coding skill is only one skill besides team-working, creativity, resilience, and more. Well, this might be a long discussion about it.

In any case, you will learn practical skills that become you into an excellent candidate for your dream job into the baptized as GAFAM / FAANG / BigFour or any other dream company for you.

Finally, let me share a video that I recorded this year in how I attack the first problem that appears in LeetCode for starters/beginners.

There is a way to face the problem by myself into an explanatory perspective. Do not expect to be a master coder with that (?) 🖖 It is a long video (~30 minutes).

Well, this post is a long reading to be a short story. Oh, btw, I did not become in a ninja master saiyajin coder, just a regular one who enjoys the challenges and loves the competitive programming problems 🤓. Thanks for reading.

From a geek to geeks

--
✍️ Originally published at https://www.ecode.dev on July 19, 2020. Check out my blog

🦖 If you want to help me to buy my own dinosaur, you can do that in buymeacoffee