I've been preparing for the 2017 Google HashCode World Championship Final. This is the largest algorithmic challenge contest organized by Google.
I started learning C++ from scratch in ninth grade. I knew nothing about programming, algorithms and data structures. At some point, I wrote my first line of code. Seven months later, a programming competition loomed on the horizon. I wanted to know how well my style of learning programming worked. It was the perfect opportunity.
After two days of competition, the results came: I won the gold medal.
I was shocked. I got ahead of the competition 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 I want to share it with you.
The article was translated with the support of EDISON Software, which and .
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++ because of the STL. If you know C, you will also be able to program in C++.
- Java is a slow programming language. It has a Big Integer class, but it won't help you much. If the competition has a time limit, with Java you will definitely exceed it. Java is not accepted in all competitions.
Where can you practice
I recommend . It is an efficient resource in terms of quantity and quality. Editors and solutions are available online if you get stuck in the troubleshooting process. In addition to this site, I recommend и .
First, you need to hone your knowledge of the basics
After 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 lots of spaces, maybe you don't. You may be putting parentheses on the same line as "if", or you may be putting them on separate lines.
You have to find your programming style because it is YOUR style.
As you search for it, keep two basic principles in mind:
- Your code should be easy to implement. You should feel comfortable implementing the solution you came up with. Why? Because during a competition, the last thing you want is to get lost in your code. It's always better to spend an extra 5 minutes thinking about how to simplify the implementation of the code than to spend 10 minutes trying to figure it out.
- Your code should be easy to read. When code is easy to read, it's easy to debug. Let's face it - mistakes happen all the time. You know that feeling when there are 10 minutes left and you can't find the damn mistake? Of course you do. To avoid this situation, write legible code. Once you start debugging it, the code will feel natural and easy to understand.
programming style.
How to improve your development skills
Practice, practice and more practice. I recommend that you work through the first 250 most solvable problems on . Solve them in order. Spend at least an hour thinking about the solution to each of them.
Don't say, "This problem is too hard for me, I'll try the next one." This is how losers think.
Take a piece of paper and a pencil. Think. Maybe you can find a solution, 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 classical problems and algorithms.
Second, you must master algorithms and data structures
Follow a hierarchical approach. Did you start running without being able to walk? No. Can you build a skyscraper without a solid foundation? Again no.
You cannot ignore the stages on the learning path. If you ignore them, you will be left with knowledge gaps. As time goes by, they will only get worse.
Start with fundamental algorithms and data structures
It's hard to start. Perhaps because you don't know what to study first. That's why . In creating this course, I relied on how I would like to be taught. The response was incredible! Over 3000 students from over 100 countries signed up for the course in the first month.
If you work on solving easy problems, you will never get better.
The most effective way to figure out what you don't know is to face it in practice. That's how I learned. I learned many new techniques that I had never heard of before by choosing a difficult problem.
Every third problem you work on should teach you something new. Be careful with the selection of problems. Choose the harder problems!
Once you have completed these 250 problems from SPOJ, you will have a general understanding of the main topics of sports programming. With a deep understanding of the logic behind basic algorithms, high-level algorithms will not seem so complicated. Thus, you can use your knowledge to the maximum.
Dig deeper into each of the main themes
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 you will also stumble upon a lot that you have never heard of before. So 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 a new algorithm, put it into practice. Work it out on 2-3 tasks. Look for the algorithm tag in SPOJ. There you will find problems for which this algorithm is needed. Deal with these issues first.
Understand dynamic programming because it will lead you to victory
In my experience, every contest has at least one problem . Many people get headaches 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, it's my favorite topic. The secret of dynamic programming is to make globally optimal choices, not just local ones. You should break the problem down into simpler subtasks. Solve each of these subproblems only once. Then create a solution that combines the solved subproblems. is the opposite of dynamic programming. In it, one has to make a locally optimal choice at each step. And a locally optimal choice can lead to a poor global solution.
As you explore new concepts, check out . They are very detailed and understandable. Thanks to them I was able to understand .
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 learning a new algorithm that needed to be known to solve this problem.
If you want to win, you must do the same. Pick a problem and stick with it. Think about it while walking down the road to the supermarket or while driving.
Did you know that during sleep, your brain defragments the information collected that day? He seems to be stacking books in alphabetical order on a bookshelf. Essentially, your brain is thinking about the various problems you are facing.
This can be skillfully used. Before going to bed, read a difficult problem and remember what it takes to solve it. At this stage, you do not need to look for the solution itself. Go to bed. Your brain will begin to process this problem. When you wake up, you will be surprised to realize that you found the solution while you were sleeping.
Try it yourself. It's like magic.
I created a vlog
This short paragraph is not related to sports programming. If you're in your twenties and you're wondering how I see the world, then you can watch . I speak in it about the world, life and informatics.
Work smart
This is the secret of success. You need goals.
We are human and we like . We always want to put off what needs to be done right now. Watching Netflix is always more enjoyable than dealing with dynamic programming problems. You know it and you need to fix it.
How to beat procrastination
Set yourself goals. You will always find interesting problems from which you can learn something new (check out the resources I mentioned above). But these problems need to be addressed, not just read about them.
So, here's how I overcame procrastination. I started a paper calendar and filled each day with the problems I wanted to solve. I always filled out problems in advance, two days early. So I knew how to manage my time in the following days.
So I have always been motivated. I needed to solve some problems and find new ones to fill the next days on the calendar. Crossing out solved problems is very nice. I know you like it too.
Get your own paper calendar. Don't create another to-do list on your phone that you'll forget tomorrow.
How to debug effectively
Do you want to become a professional? If yes, then you need to “debug in your mind”.
This is by far the most efficient debugging technique I know because it doesn't require a debugger at all. Your brain explores multiple branches of code at the same time and gives you a much broader view of the code than .
You can compare yourself to a grandmaster who plays chess and thinks 3 moves ahead.
I use this technique exclusively as my initial line of defense. Then I use a real debugger.
To learn how to “debage in your mind”, you need to practice. When you approve a solution to a problem and get a "wrong answer", don't go straight to the debugger button. Reread the code and think: “What is happening in this line?”, “How does “if” affect the program here?”, “When we exit the loop, what is the value of the iterator?”.
So you think for yourself. Over time, you will learn how to write code and debug it on the go.
About the Developer
Andrei Margeloiu is an avid programmer with an interest in entrepreneurship, startups and nature. You can contact him .
Translation: Diana Sheremyova
Source: habr.com