I was preparing for the Google HashCode 2017 World Cup Final. This is the largest contest with algorithmic problems organized by Google.
I started learning C ++ from scratch in ninth grade. I did not know anything about programming, algorithms, and data structures. At some point, I wrote my first line of code. Seven months later, a programming Olympiad loomed on the horizon. I wanted to know how well my style of learning programming worked. It was an ideal opportunity.
After two days of competition, the results came: I won a gold medal.
I was shocked. I got ahead of competitors with 5 years of experience. I knew that I worked hard, but this achievement exceeded all my expectations. I realized that sports programming is my topic and went into it with my head.
I know what led me to success and want to share this with you.
This article was translated with the support of EDISON Software, which takes care of the health of programmers and their breakfast , and also develops custom software .
Which programming language to choose
- C ++ - Highly Recommended! He is very fast. The implementation of the algorithms takes little time due to the STL. C ++ is accepted in all competitions. I wrote my first line of code in C ++.
- C - learn C ++ due to STL. If you know C, you can also program in C ++.
- Java is a slow programming language. It has a Big Integer class, but it doesn't really help you. If the competition has a time limit, you will probably exceed it with Java. Java is not accepted at all competitions.
Where you can practice
I recommend Sphere Online Judge (SPOJ) . It is an effective resource in terms of quantity and quality. Editors and solutions are available online if you are stuck in the process of solving problems. In addition to this site, I recommend the SPOJ Toolkit and the problem classifier for SPOJ.pl.
First, you need to hone the basics
Once you get used to the syntax of the language, you will have to solve some problems. Start with simple problems that require practice. At this stage, the main thing is to determine your programming style. Maybe you like to write code with a lot of spaces, or maybe not. Perhaps you put the brackets on the same line as the “if,” or you can put them on separate lines.
You have to find your programming style because it is YOUR style.
When you look for him, do not forget two basic principles:
- Your code should be easy to implement. You should feel comfortable implementing the solution you came up with. Why? Because during the competition, the last thing you want is to get lost in your code. It is always better to think about how to simplify the implementation of the code, than spend 10 minutes to figure it out.
- Your code should be easy to read. When code is easy to read, it is easy to debug. Let's face it - errors appear constantly. Do you know the very feeling when 10 minutes are left until the end and you cannot find the damn mistake? Of course you know. To avoid this situation, write legible code. When you start debugging it, the code will seem natural and easy to understand.
Here is an example of my programming style.
How to enhance your development skills
Practice, practice and practice again. I recommend that you work through the first 250 of the most solved tasks on SPOJ . Solve them in order. Take at least an hour to ponder the solutions to each of them.
Do not say: "This problem is too complicated for me, I will try to solve the following." So losers think.
Take a piece of paper and a pencil. Think about it. Maybe you can find a solution, or maybe not. At a minimum, you will develop algorithmic thinking. If you can’t come up with a solution within an hour, look for a ready-made solution on the forum or in the articles.
What will you achieve with this approach? Learn how to quickly implement your ideas with code. And learn classic problems and algorithms.
Secondly, you must master the algorithms and data structures
Follow a hierarchical approach. You started to run, not knowing how to walk? Not. Can you build a skyscraper without a solid foundation? Not again.
You cannot ignore the steps in the learning path. If you ignore them, you will still have knowledge gaps. Over time, they will only worsen.
Start with fundamental algorithms and data structures
It's hard to get started. Perhaps because you do not know what to study first. Therefore, I created a video course "Algorithms and data structures." In creating this course, I relied on how I would like to be taught. The reaction was incredible! Over 3,000 students from over 100 countries signed up for the course in the first month.
If you work to solve easy problems, you will never get better.
The most effective way to figure out what you don't know is to run into this in practice. So I studied. I learned many new techniques that I had never heard of before, choosing a difficult task.
Every third problem that you are working on should teach you something new. Be careful when choosing a problem. Choose problems more difficult!
After you finish these 250 tasks from SPOJ, you will have a common understanding of the main topics of sports programming. Thanks to a deep understanding of the logic underlying basic algorithms, high-level algorithms will seem less complicated. Thus, you can use your knowledge to the maximum.
Dig deeper into each of the main topics.
Here is a valuable resource with lots of information. There you will find the top 10 algorithms and data structures for each topic. After 250 problems from SPOJ you will know a lot from this list. But also stumble upon many things that have never been heard of before. Therefore, start exploring these topics in ascending order.
If you do not strengthen your knowledge after you learn something new, you will quickly forget everything.
I recommend that after you learn the new algorithm, use it in practice. Work it on 2-3 tasks. Look for the algorithm tag in SPOJ. There you will find problems for the solution of which this algorithm is needed. Disassemble these issues first.
Deal with dynamic programming because it will lead you to victory
Based on my experience, in every competition there is at least one problem of dynamic programming . Many people have a headache when they hear the phrase “dynamic programming” because they don’t understand it at all.
And this is good. Because if you understand dynamic programming, then you will win.
I like dynamic programming, this is my favorite topic. The secret to dynamic programming is to make globally optimal choices, not just local ones. You must break the problem down into simpler subtasks. Solve each of these subtasks only once. Then create a solution that combines the solved subtasks. A greedy algorithm is the opposite of dynamic programming. In it, you need to make a locally optimal choice at every step. A locally optimal choice can lead to a poor global solution.
As you explore new concepts, check out the TopCoder tutorials . They are very detailed and understandable. Thanks to them, I was able to understand binary indexed trees .
Work hard
Have you ever heard of athletes who win the Olympics without years of practice? Me not.
Every year, preparations for the computer olympiad began in September and ended in April.
Every day during these 8 months I practiced for 5 hours.
And yes, I spent these 5 hours only on solving algorithmic problems. I remember the days when I practiced for 8 and even 10 hours. Why? Because I liked it. Every day, returning home from school, I went straight to the bedroom, sat down at the computer and began to sort out a new problem. Or studied a new algorithm that you needed to know to solve this problem.
If you want to win, you must do the same. Choose a problem and stick to it. Think about it while walking along the road to the supermarket or while driving.
Do you know that during sleep your brain defragments the information collected on this day? He seems to be stacking books in alphabetical order on a bookshelf. Essentially, your brain thinks about the various problems you have encountered.
This can be skillfully used. Before going to bed, read the difficult problem and remember what you need to solve it. At this point you do not need to look for the solution itself. Go to bed. Your brain will begin to handle this problem. When you wake up, you will be surprised to realize that you have found a solution while you are sleeping.
Try it yourself. It looks like magic.
I created a video blog
This short paragraph is not related to sports programming. If you are over twenty, and you are interested in how I see the world, then you can watch my video blog on Youtube . I speak in it about the world, life and computer science.
Work wisely
This is the secret to success. You need goals.
We are people and we like to procrastinate . We always want to put off what needs to be done right now. Watching Netflix is ​​always nicer than dealing with issues of dynamic programming. You know that, and you need to fix it.
How to beat procrastination
Set goals for yourself. You will always find interesting problems from which you can learn something new (check out the resources that I mentioned above). But these problems need to be solved, not just read about them.
So, this is how I overcame procrastination. I started a paper calendar and filled every day with the problems I wanted to solve. I always filled in the problems in advance, two days earlier. Therefore, I knew how to manage my time in the following days.
Thus, I always had motivation. I needed to solve some problems and find new ones to fill in the following days on the calendar. Crossing out the solved problems is very nice. I know you like it too.
Get your own paper calendar. Do not create another to-do list on your phone that you will forget about tomorrow.
How to effectively debut
Want to become a professional? If so, then you need to debase in the mind.
This is by far the most effective debugging technique I know, because it does not require a debugger at all. Your brain examines several branches of code at the same time and gives you a much wider overview of the code compared to the classic debugger .
You can compare yourself with a grandmaster who plays chess and thinks 3 moves ahead.
I use this technique solely as my starting line of defense. Then I use a real debugger.
To learn how to “debase in the mind”, one needs to practice. When you approve a solution to a problem and get a “wrong answer”, do not go directly to the debugger button. Reread the code and think: “What happens on this line?”, “How does“ if ”affect the program?”, “When we exit the loop, what is the value of the iterator?”.
So you are thinking on your own. Over time, you will learn how to write code and debut it on the go.
about the author
Andrei Margeloiu is an avid programmer who is interested in entrepreneurship, startups and nature. You can contact him on LinkedIn .
Translation: Diana Sheremyeva