FloyGun's blog

By FloyGun, history, 4 weeks ago, In English,

I understand that CP can't be described in few notes but I really want to hear from stronger competitive programmers some short ideas, rules and tips that help you while solving and/or coding difficult problems. I'm not talking about training in general but some tips on how to approach or what not to forget while solving and/or coding. Might be generic or specific. Anything. Many thanks.

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

»
4 weeks ago, # |
  Vote: I like it +316 Vote: I do not like it

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I know that by such things people may mean magic pills or universal algorithms that solve all problems but I look for something real like what first do you think when seeing probabilities, where should we be careful in, say, CHT implementation or what are your first steps while constructing greedy, etc. I kinda want to make a list of suggestions and share it with CP amateurs like me.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 4   Vote: I like it +22 Vote: I do not like it

    Questions like "what first do you think when seeing probabilities" are useless before you solve enough of probability problems and meaningless after. Same for everything else you've mentioned. Just solve, upsolve and read editorials, don't look for easy ways.

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

** Cyan says some short ideas
** FloyGun : would it help ?

:'D

»
4 weeks ago, # |
Rev. 2   Vote: I like it +127 Vote: I do not like it

(TL;DR at the end if you're lazy)

It is well-known that, in order to master something, you have to be able to teach it. I think it applies to solved problems too.

When you solve an hard, interesting, many-steps problem (not a random cancer CF problem), try to write a complete document about it (few pages), where you will explain all the thinking process that leads to the solution.

IOI-style problems may be good candidates for that, because the subtasks format will naturally divide your solution into several thinking steps.

Everything should be clear in this document, and the path leading to the solution has to be natural (unlike most editorials which don't explain how to come up with the solution). You may have to make your solution as simple (and elegant) as possible before writing.

While explaining the solution to the specific problem, don't forget that the document also has to give general problemsolving adivces (related to the problem, of course) :

  • When you use some sort of technique/trick/observations, try to write an aside about it (why we should think about it in this case, in what other cases is it useful, try to find corollaries and generalisations).

  • When you're doing greedy things, don't write a formal and obscure proof, instead write an intuitive justification (it may be harder to find).

  • When there is a potential wrong solution that looks attractive, explain why it's false, and how we can find a simple counterexample (e.g. testing resistance to "noise")

  • etc...

In the last part of this document, summarize all useful tricks or "method points" you learned while solving this problem.

This "teaching part" is in my opinion the only way to really fix in your brain all the nice things the problem made you discover. Unless you did it, I don't think you can consider that you completly solved the problem.

TL;DR Solve hard and interesting problem, and write a complete document explaining a natural thinking path that leads to the solution (how to come up with it), with asides about techniques or method points used.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Good point. Many thanks.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    That's a lot of time spent on one problem. Doesn't sound efficient to me.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it +47 Vote: I do not like it

      Well, it's quality over quantity. I tested both, and spending more time on fewer and harder problems personally gave me better results. But it may not suit everyone, there is no universal practice method anyway.

      Actually, if we're solving hard enough problems, writing this document will not be longer than actually solving the problem, so it's at much twice as slow. That means that we will solve 2 times less problems, but they will have a way bigger impact (at least for me), so I think it's worth it.

      That's of course two different spirits of training. The quantity helps in fastsolving and gathering a lot of classical knoweldge quickly, the quality helps to improve thinking ability and extend "comfort zone".

      Both things are important in div1, so one should probably mix these two type of trainings.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        How did you test and compare the two methods?

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 6   Vote: I like it +62 Vote: I do not like it

          For the first method, I was doing during few months a lot of problems that I would solve in like 30-60min (max 90min), mostly on Codeforces, easy OI problems too. I upsolved problems that I could have solve in contest with more time, and read editorials for others.

          • I learned some classical tools (suffix array, HLD, Dinic, ...), it was nice. But now that I know all classical tools, and FloyGun probably do too, it's not an advantage anymore.

          • I was faster on problems I was already able to solve during contest. Being "quite fast" instead of "slow" is nice. But once I was "quite fast", being "very fast" on easy problems didn't matter much, except in Speedforces (as some "quite fast" people would solve harder problems and beat me anyway).

          • I still couldn't solve problems outside my comfort zone (D1C was too hard). If I continued this way, I think I would have reached a peak like FloyGun.

          • Outside focus of this blog, but it was almost totally useless for OI. Almost no progress here.

          For the second method, I looked at harder and more interesting problems (rating+300 on Codeforces, JOI Spring Camp, ICPC World Finals, ...). I usually spent 3 to 5 hours on these problems (eventually asking for hints, avoiding editorial, trying to get my own intuition of the problem). Writing a document was like 1h30.

          • I was really happy to solve these problems, made me feel that I really made an important acheivement (and motivation is very important when practicing and trying to outcome a peak).

          • It forced me to totally change my mindset and my approach of problems (developing a new problemsolving method, more rigourous), while the first method only consolidated my current approach which was quite bad (bad habits like not verifying solution before coding it, trying to guess the solution without using paper, thinking directly of the whole problem instead of thinking about simplifications, ...)

          • It made me really remember important "lessons" and think of other cases it would be useful, thanks to teaching part. Thanks to that, I'm in a sense able to "connect problems together".

          • It made me reach next level of problem difficulties (D1C), even if I'm usually quite slow to solve them.

          Now that I wrote this, I realized how the two methods could eventually be combined:

          • Use second method (solving hard problems) to exit the comfort zone, outcome the peak and reach next level.

          • Once this next level is reached (usually being able to solve them in contest), use the first method to consolidate the comfort zone (always being able to solve them, and quickly enough).

          • Once the new level is mastered, repeat the process.

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

            Writing a document was like 1h30 ... can you share some of these documents with us ? i'm interested in your in your method and i want to see some examples of the explanations. thanks in advance.

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
                Vote: I like it +5 Vote: I do not like it

              I write them in my native language (french) unfortunately, as my english skills are quite bad. You can still see the one I made for Pizza Delivery if you want (complete, even if it's not a problem I totally solved myself): https://www.docdroid.net/evOOt8P/pizza-v2.pdf. For some problems I did handwritten notes instead of LaTeX document.

              And by the way, I'm not sure that this method is actually suited to participants below purple, because I don't really know many-steps problems suited to you and enough interesting to write a document about. Well, I didn't test it when I was cyan, so I don't really know.

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it +17 Vote: I do not like it

            You just explained that it's good to solve hard problems (outside your comfort zone).

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

              Yes, and spending a lot of time on them, answering your first comment. Writing takes only a supplementary hour on these problems solved in 3-5 hours, so it's not a loss of time (in fact, I never felt so efficient), helps taking a global view on the problem and extending the interest of the problem to more general cases. I now perfectly remember the problems I wrote something about (and their solution), and forgot almost all other ones.

              • »
                »
                »
                »
                »
                »
                »
                »
                4 weeks ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                I'm just saying that you don't have a comparison between "solving hard problems" and "solving hard problems and writing solutions down".

                I'm sure that I gain something more when testing problems, discussing them, spending a lot of time, albo setting contests and writing editorials. But I think that just solving hard problems is more efficient, that's it.

                Do consider writing editorials (or blogs). You will get paid (well, that depends on the platform) and the community will get something valuable. A win-win.

                I write them in my native language (french) unfortunately, as my english skills are quite bad.

                Your comments are much better than an average editorial, don't worry about it. But I understand that it could take more time then.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 weeks ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  Oh, sorry for the misunderstanding.

                  I do get that writing solutions down may not be efficient for everyone. As long as one has a clear solution and doesn't forget about the problem as well as the things they learned solving it, it's fine. Writing a document assures you that this goal is reached, but it might not be worth taking the time to do so for those who have an organized mind then (unlike mine). Thank you for your feedback!

                  Do consider writing editorials (or blogs). You will get paid (well, that depends on the platform) and the community will get something valuable. A win-win.

                  I didn't know about that, thanks. I'm currently busy with problemsetting, but I'll probably try it in the future.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks ago, # ^ |
                    Vote: I like it +3 Vote: I do not like it

                  Hi could you please upload the articles you write on your github for people who understand french ? It's often hard to find clear explanations for OI problems.

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            By "D1C", are you referring to Division 1 C Problems?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +106 Vote: I do not like it

    You forgot the most important step: Post it for contribution.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +61 Vote: I do not like it

    I endorse this approach, and this is what I've been actually doing for a long time. I have a Korean blog where I started writing for about 5 years, spanning my whole CP career (my article from 2014 is about finding shortest paths, and maximum subarray algorithm).

    It really takes a lot of time, because I usually use about 2~10 days for writing a single article. While I'm still struggling to make it faster than now, I believe writing makes a better person, which is important than being a better competitive programmer.

    Btw, I always think about making English blogs, but it's quite hard for me for various reasons (not including language barrier). I'm really trying to deliver something in early August or September, stay tuned :)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

try to approach the problem by your own.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Well I have a question in which I hope other's can give me advice on.

When upsolving, is it very important that one always implements the solution, or sometimes should I just "theory solve" the qn, and skip the implementation to instead focus on having more exposure on other questions? Thank you!! :)

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

    I would suggest implementing it as the way to practice coding skills and just spend time with the problem to remember the solution well.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    If you are a beginner -> just implement everything.

    If you are experienced -> If the implementation is simple or you were like a simple observation or 2 away from solving the problem then skip otherwise implement it.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Well, as one wise man once said, just solve more problems.

»
4 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

One CM to another CM: Never ask Red coders...

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +70 Vote: I do not like it

    Yeah man. Never ask a red coder. Have some self respect and pm a nutella.

»
4 weeks ago, # |
  Vote: I like it +83 Vote: I do not like it

I think the most important thing I learnt is that it's always optimal to think carefully and understand a solution completely (maybe on paper) before implementing it.

First of all, in team contests it obviously saves computer time. If you have 15 hours of human time and 5 hours of computer time, it's usually better to optimize computer time which can be spent on implementing and debugging and so on. It's dangerous when the guy who took the computer tries to finish his solution and the computer is not actually involved.

Moreover, I noticed that when I participate in an individual contest, it's still better to think of all details of a solution before starting it. I don't always manage to take everything into account, but the strategy "I start it now, write everything that is definitely needed and then just deal with the rest somehow" usually leads to nothing good, no matter how tempting it seems. I noticed that with the right strategy I have to debug much less my solutions than earlier.