lnzva's blog

Should I invest my time more in practising problems, or in reading theory, if I don't have enough theoritical knowledge yet?
By lnzva, history, 9 years ago, In English

Being a beginner in competitive programming, I want to know which way will make me improve more. Should I focus on reading theory more(seeing that I haven't studied algorithms or data structures) or would my time be better spent in solving problems right from beginning, without focusing on theory?

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I think that solving problems is very important because you are learning to debug while writing code (and that increases your spead and attention). It seems good for you to combine both theory and practising, for example you can stude dfs/bfs and find problems on codeforces.com ny hashtags. Or, for example, you can check out latest Code Monk on HackerEarth.com — it was about graphs. Some tutorial (quite useful in my opinion) was provided and there were 4 simple problems.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How are you supposed to solve anything without theory?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    it sometimes good. when we can't solve a problem, then after seeing the editorial that there's something we must know first. it really helped us for understanding what algorithm can do and what it can't do IMHO.

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +18 Vote: I do not like it

    A lot of things are solvable without advanced theory and a lot of theory can be "rediscovered", rather than learnt from a textbook. Theory was developed from practice in the first place, it's only natural that the process can be reconstructed and I think it's always considerably better to do so, although few people actually have the patience.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Well, I guess you are right. But you do need a lot of time to "rediscover" a lot of algorithms that are known when you can simply just learn them. I feel that is a waste of valuable time to reinvent the wheel whenever you need it.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 3   Vote: I like it +16 Vote: I do not like it

        Not really, because you have a much tighter grasp on things that you try to solve on your own. Even if you don't succeed, you'll have a much better understanding of how the classical algorithm overcomes the difficulty of the problem and why it's better than your solution. Consider these methods of introducing somebody to DP via a problem that asks for the shortest "down-and-right" path from (1, 1) to (N, M) in a matrix.

        1. Tell them something like "This is a classical DP problem. The state is DP[i][j] = best way to reach the cell (i, j), etc. It's clear that it works."
        2. Let them think of a few solutions on their own. Shoot down the wrong greedy solutions by counterexamples and ask them to formulate clearly why they don't work. Sooner or later somebody will realize that choosing optimally locally doesn't imply global optimum. Maybe then somebody will come up with the correct DP solution, but even if they don't they'll have some intuition on what type of tasks work with DP, because they know how it helped them in this particular case.

        It may seem that the first option lets you cover more theory and more types of problems, but in the long run it will do more harm than good, because if you want to tackle more difficult problems that can't be taught from a textbook, you'll need intuition that you can only develop by recreating a solution for yourself.

        → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +4 Vote: I do not like it

When you search for problems — you constantly encounter new theory to study. Try solving harder problems related to some papers or algorithms. It will give you both — debug knowledge and algorithm understanding.

→ Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it +4 Vote: I do not like it

I think that you can improve too much in programming contest without spending much time reading theory. Instead, try to master your programming language. How? This is what I did some years ago:

  1. Sort the problems in the problem set from decreasing order of number of people that solve them.

  2. Solve them in this order. At beginning you will get surprised seeing that there are some of these problem that were solved in real contests in less that 5 minutes by Div.2 contestants, I you will not be able to solve them in less than an hour. At least I experienced it.

  3. After solve a problem, don't move to the next one. Instead, check the smallest solutions for this problem (in this way you can learn some programming tricks) and check the solutions of the coders that firstly solve them during the contest (in this way you can learn some standard ideas for approaching this kind of easy problems). In this way you will learn a lot.

Remember this, after solving a problem by yourself, you will get the fruit of your own creativity. After seeing a solution by other coders, you will get the fruit of the creativity of other people. I think that this is a great way of improve your thinking skills.

If you train in this way, in no much time you will be able to be a blue/purple (maybe yellow) coder. After that, consider that it is time to change your training strategy.

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

let me explain why I think you should not study too much with the help of an analogy. Suppose you decided to pick up mountain biking, but you never rode a bike before. You start browsing the web, watching YouTube videos and you even buy a 150-page book about MOUNTAIN biking. After 2 months of studying you decide it's time to try it out. You try to remember everything you read and saw in the videos and it's overwhelming. You get mad at yourself, because you fell so many times from the bike even after studying so hard. You might actually give up biking in the end.

Does this sound ridiculous to you? Now substitute biking above with programming. Of course biking and programming are not the same, but trying to absorb all the information available often does more harm than good. Instead, you should just start solving problems and learn algorithms on the way. You'll also see when and how algorithms are actually used.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can combine.

Skiena, Revilla. Programming Challenges. The Programming Contest Training Manual.

Chapter with theory, then UVA judge tasks

→ Reply