shakil's blog

By shakil, 13 years ago, In English

I have some questions in my mind

How to perform better in codeforces & Topcoder.
can anyone give advice , share some tips & tricks , to improve my/our skills
Which way I should proceed?
What should I know/learn ? 
How to increase my knowledge base?

It would be very helpful if someone kindly shared their thoughts<what they do>
so that coders like me can improve our skills & be benefited.

sorry for my bad English.
  • Vote: I like it
  • +22
  • Vote: I do not like it

| Write comment?
13 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

I have only one piece of advise.
Practice makes perfect.
Upsolving is very important. In my opinion there is no point in taking part in contests without upsolving them later if you want to grow.
  • 13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    what does upsolving means?
    • 13 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it
      Same question I've got yesterday while chatting with msg555. It seems that this term is used only in Russia while foreigners don't understand it.

      Upsolving means "solving problems after the contest".
  • 13 years ago, # ^ |
    Rev. 3   Vote: I like it -15 Vote: I do not like it

    Please don't be offended, but, as I can see, you've never been neither red nor green. So you can guarantee the formula "practice makes perfect" works for becoming orange from blue. OK, I believe it works the same way in becoming blue from green, but what about the last subtask? We should listen to opinions of some stable reds who were greens in the beginning of their olympiad career.
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Before having opinions from stable red,you can share your opinion with us because you were red for a while, where you started from green [N.B: Although you were not eligible for green at your starting :P .so you shifted your curve in next contest]:D 
      • 13 years ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        My opinion is that training regime for becoming red from orange is totally different from the one for becoming blue from green. Improving your skills in sports programming, like every studying, should be performed consequently. For example, as you became a blue recently, you can give a piece of advice to the topic starter, but Div-1 participants (including myself) forgot details of this step of training years earlier, so we really can't tell to you guys something cleverer than "practice makes perfect", but telling this is telling nothing at all, yeah?
        Anyway, here is going discussion on this issue in Russian, if you can translate.
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      In TopCoder such method works... Even to become stable yellow/red from grey. =)
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Yeah , I agree with you.
    But sometimes upsolving them becomes really difficult because those exceeds my level of thinking.
    what should I do then?
    Thanks for your kind reply.

    • 13 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      What should you do if you want to become international chessmaster? Or if you want to enter top-ten tennis players list. Do you think there is any "easy trick" which could help you avoid thorough studying, improving your practical and theoretical skills?

      Why do you think that situation here is different? You need to solve a lot of problems and you need to read a lot of theory.

      I myself spend almost no time for any studying of this kind - and behold the wonder - I am not red, I am green! ;-)

      (I also suppose that some people have more patience and attention than others - and we call this "having talent" - it could help or make your learning faster - but it is important when you want to became No.1, I think...)
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Forgive me if I stated it incorrectly.
        I didn't meant to be "easy trick".
        I know if someone wants to be red he must work for 5+ hours a day.
        I just wanted to know which is the right way of doing it.
        I am asking about how to optimize my working time <like the red coders did when they were green>.
        can I ask you what kind of material we should study<there are many things in this world>?
        Thanks for your comment.
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Although my rating is not much higher than you, but still I would like to share something, that practicing one or two div2 500(which usually do not require any specific algorithm) at topcoder daily really helps to increase rating at green level, and will surely make u blue at codeforces and around 1100 at topcoder.
                I am also following this approach, due to which my rating is increasing from last four SRMs.
        • 13 years ago, # ^ |
            Vote: I like it +2 Vote: I do not like it
          I think you should:

          1) Determine, which types of difficulties you have with solving problems:
          - you just can't get the cue for the problem;
          - you could not always read the problem statement properly;
          - your knowledge of your chosen programming language is not sufficient and you spend time on bugs because of it.

          2) In last two cases you must practice reading more problems or writing more programs. The first case we shall regard closer.

          3)  Improve your theoretical knowledge. Find one or more books on algorithms or discrete mathematics, which is suitable for your level (you'd better find them in your native language, so I would not recommend anything) - read them in your free time.

          4) Keep the rule: if you read in the book about algorithm which you do not know, or know but never tried to implement - write its title into your task list.

          5) Spend 1-2 hours a day solving problems from CodeForces, TopCoder, SPOJ etc. If you could not solve or understand something - write its title and number in the end of your task list.

          6) Spend another 1-2 hours a day attempting to implement algorithms or solve problems from your task list. If you could not solve some problem, transfer it to the end of the task list.

          7) In your free time keep either thinking about old problems which you could not solve or want to improve - or reading statements of other problems and thinking about ways to solve them (marking problems which you could not understand how to solve right now).

          This is one of suitable strategy. You can develop your own strategy according to your temperament.

          I could not give advice on what exactly you need to read or learn. Sport programming usually regards narrow class of problems. Here are very few of professional programming, geometry, continuous mathematics, physics etc. You can decide whether you want to improve these skills too.
  • 10 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    By chance I just run into your comment one year later than I first read it. During this year I've followed your adivse and I have upsolved my contests, learning much more than I did before and getting from blue-purple to orange. I even mentioned your advice to my friends and other users on quora.

    So thank you for your advice Fefer_Ivan!

  • 5 years ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    Apart from upsolving, can you tell me Which type of practice I should do? I am green in my second account and I can solve A and B and sometimes C questions during contest...

    • 5 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Here's one piece of advice: don't use multiple accounts

»
11 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Dude, I'm not red or the master in programming competitions, but I can give you some advices. A couple of years ago someone told me about these competitions. I was still very young, 12 years old and dreaming about someday participate at the IOI. I didn't even know where to start and what I should learn, so I started asking people that were good at it some advice and what I should learn. They gave me some basics stuffs just for me to start, and then I spent most of time studying everything they gave me and trying to solve as much problems as I could. So when I was 15 I took part in the Brazilian Olympiads in Informatics ( a.k.a OBI ) and got a really bad result, I couldn't even get to the selections to the IOI. So I started studying even more, solving more problems, and when I turned 16 I tried one more time and got the same result. I kept studying and this year I decided to do something different, instead of solving problems that I already knew how to solve just for quantity, I decided to go for the hard problems, the ones that usually I couldn't solve in the first 5 hours of a competition, and during 6 months I think I may have solved not more than 20 problems, that was way lower than I used to solve, but those problems were really difficult problems. So this year I competed again and got the first place in the Brazilian Selections to the IOI. After almost 5 years of training I finally achieved my dream of getting to the IOI. Well, I couldn't get a medal, I made some really bad mistakes during the first day, but what I learnt from it is that besides training hard you should get out of your comfort zone and start solving problems that you don't feel so comfortable with. That's the only way of getting better and better.

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    When you get out your comfort zone it becomes the learning zone, I am completely in agreement with you, I think that getting out of the comfort zone, upsolving , and trying always to solve harder problems is the key to success in programming competitions.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am currently doing upsolving,I try to solve the hard problems of the contest and if I am unable to solve them,then I go for editorial and read other people codes.I want to know what will be better, reading the algorithms in advance from the books or trying to solve hard problems and then read the required algorithm?

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks...

»
10 years ago, # |
Rev. 4   Vote: I like it +41 Vote: I do not like it

Solve 1000 problems, then solve 1000 more and bam, you're red!

Actually, the most important thing is to solve problems you can't usually solve. To think hard about the solution and make everything clear in your mind. If you just solve the problem, but some details are not really clear to you, then it doesn't mean anything. Next time you see a similar problem you won't solve it, you won't be able to use what you should've learned while solving the problem. And of course, after every contest solve the problems you didn't solve during the contest (well, not necessarily problems far above your level), with or without the editorial, it doesn't matter.

When having to just practice and solve bunch of problems I found out that the best way to do it is to find a friend or colleague who's willing to do the same. For example I did that on SPOJ with stjepan when we started competing. We did several hundreds of problems in a few months and learned all the basic algorithms and tricks one should know to qualify for IOI.

»
10 years ago, # |
Rev. 2   Vote: I like it +31 Vote: I do not like it

Like this.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    and this way you don't even need to be purple in the way! that's efficient D:

»
10 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Hi shakil

Even though we are the same codeforces color >.<, i still have valuable advice to provide. My red friends on codeforces have stuck to this method. I have used this also to make the gold division in USACO.

Step 1: Learn and Practice Algorithms

Start from some simple and basic algorithms and practice them thoroughly:

-Sorting

-Scanline (Sweep line)

-traversals

-binary search

-MST/shortest paths

-DP

-Simple data structures:

-dsu, sets, map, heap, queue, stack, deque

Then proceed on to more devious and complex algorithms:

-Greedy

-DAGs, SSCs, Bi-connected compnents

-DP + caching previous results

-compression

-Convex Hull

-Complex Data structures:

-segment trees, linked list, BIT, Trie, Splay, Suffix Trees

-KMP/String hashing/string algorithms

-mincut/maxflow/maxmatching

Step 2: Look at Problems, Know what type of problem it is

I suggest you turn off the tags for unsolved problems so you can try to decide what type of problem you are solving.

At this step, you should try to: -know how to turn this problem into something familiar, into a graph? How will you handle updates? queries?

-know how to handle constraints of the problem. Do you need to add more states?

-Make observations about the problem, if the problem gives huge constraints like 10^6 and then suddenly gives a small constraint of 10, you should take advantage of that. Of course there are many different observations that you can make to help you solve problems.

Note at this step you do not need to necessarily code up the solution, you just need to form a clear approach in your mind.

Step 3: Implementation

Here is when you need to not only recognize the type of problem, but also know how to implement it. This is what I am bad at. My suggestions are:

  1. order the codeforces problemset by solved and burn through the first 4~5 pages. I have finished the first 3 already.

  2. Practice problems that require more than a direct approach. These problems can combine algorithms like dp with complex data structures, here is an example: http://www.usaco.org/index.php?page=viewproblem2&cpid=365

Other Tips:

When doing codeforces problems, if you get a wrong answer during practice, try not to scroll through the test data to see what you got wrong. Try to test your code again and see if you can fix your bug, this really helps during a contest. This is how I can recover from hacks. Do not only do codeforces (although I think codeforces's problemset is the best), do other sites that have even more archive of problems like POJ, SPOJ, USACO / USACO Training Gateway, etc.

Hope this helps! Trust me, this is how I got into USACO Gold! Just follow this list!

Best, acho163

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    USACO gold sounds very competitive. If so, how come you do so well in USACO and remain blue on codeforces? (You were even a green coder a few months ago.)

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am actually quite novice to code forces contests, I am still getting used to them. :)

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      TBH USACO system has a flaw compared to serious contest sites: you can't move down. In order to reach the gold division, you need to do really well just once (silver -> gold, if you do that then bronze -> silver should be trivial), not often. Also, USACO has partial scoring and doesn't depend on time or number of WAs, which makes it even easier to get 1 successful contest. So ratings on CF and USACO division placement are almost completely unrelated things.

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I completely agree, in competitive yes, USACO is easier than code forces, despite the same difficulty of problems.

        I am still a blue coder as I have mentioned above, I am really bad at knowing how to implement a problem fast. USACO allows more than 1 hour to think per problem, which is a huge advantage.

        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I see. I don't really know anyone working for USACO in person, so was just wondering.

          Anyway, thanks for sharing great advice!

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Step 1: Learn and Practice Algorithms

    • DFS and BFS.
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Step 1: Learn and Practice Algorithms

      -traversals

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice one, I think some of the algorithms/data structures you mentioned are not sorted in a good order, also about the steps, i think you should do all the 3 steps together, for example one may think that its better to first learn all that tough data structures then try implementing 800 difficulty problems(at least i thought you meant that).

    About the last step, in my opinion 5-6 pages is too much to get used to simple implementations, its probable better to not to get stuck in 800-1200 difficulty problems for long time.

    If you think you don't spend any time to solve the problems but you cant implement them fast enough, then you probable need to practice implementing hard problems(not just simple if-else problems but some heavy ones), if you think you are solving the problems slowly but you easily go through the coding/debugging/optimizing part, then you should probable practice more on solving hard problems, and then go through the implementing part as fast as you can(it doesn't work for all the peoples, and its not true for all the problems, some of them are more implementation problems and some more think-forces). In short, try to be balanced, otherwise you cant do your best.(it also depends on what you want, do you want to be able to code/solve as fast as hell?, for example in some jobs, its more important to implement than to solve)

    Also take virtual contests frequently, solve up the contests you take, you may solve some problems with +300 difficulty higher than you rating, also don't burn the problems, but boil them, it means to not to go straight into the editorial, spend some time on the problem, don't check the editorial as long as you are able to approach the solution, then if you were stuck and you've spent enough time(not less than half an hour, it depends on lots of things, specially your feelings), then its fine, read the first phrases of the editorial, until you found something new that may help you, then again spend more time trying to solve the problem, knowing the new thing will help you think more focused, and so, you may solve the problem with that little help, do the process until nothing else remains or you have solved it. (in that point you actually boiled the problem, now you can eat/solve it whatever you feel better (╹ڡ╹) )

    Don't be mad if you couldn't eat/solve the problem even after boiling it, the important part is to walk through that boiling process, not to solve the problem(usually).

    Also if you couldn't solve a problem or it took too long, then try to find out what was your weak point(s), if you solved it and you found something interesting(an idea, a trick, an algorithm, whatever you didn't know before), then first make sure you understand them, spend some time just thinking about "What the heck just happened?", then if you can, try solving some problems using that thing(probable you wont find any ^_^), you may also write them in a book for next times or try explaining them loudly or find some applications for it(find somewhere to use it, don't make it a useless trash in your packet), just, i don't know, learn to use them later, simple !

    I hope it would help, probable it will, correct me if iv'e made any mistakes.

    I respectfully don't guaranty anything $$$'_'$$$.

»
10 years ago, # |
  Vote: I like it +46 Vote: I do not like it

Another option.

»
10 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Use the magic in codeforces.......

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Red to become, patient you must be.

Some of us will never become red. And some of us will take a while to reach red.

Anyway, I think we(greens and cyans) must focus on two things-
1. If you know a certain trick/method/DS/algo, then increase the probability of getting AC for the problems which use it. Hence, practice.
2. If you don't even know enough trick/method/DS/algo, then you should learn them. Hence, upsolve(because there are so many things we don't know, that it may get overwhelming to even choose something to start learning.).

»
7 years ago, # |
  Vote: I like it +21 Vote: I do not like it

To become red from green, turn yourself into a working traffic light and when you become red, break yourself! :)