TheScrasse's blog

By TheScrasse, history, 15 months ago, In English

Hello everyone,

this blog is similar to 90744, but it's specifically about implementation.

Although practicing for around 2 years, I'm still very slow in implementation. For example, during olympiads I usually spend ~ 70% of the time writing the code, so I don't have much time to think.
In fact,

  • during CEOI 2021 Mirror (Day 2) I spent a lot of time writing ~ 220 lines of code for problem C (the logic of that solution was wrong, but that's another story)
  • I've just solved CEOI 2016/1 (submission), but my solution is 239 lines long.
  • I don't perform well on DMOJ (my contests: 1, 2, 3)
  • I spent 1:30 hours implementing 101597A, although my final code is only 81 lines long.

How to improve? Should I learn new C++ features? Should I start implementing something significantly longer than competitive programming problems?

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

»
15 months ago, # |
  Vote: I like it +31 Vote: I do not like it

I also used to face the following problem. To overcome, first, I worked on my typing speed on Keybr. Then whenever I tried to implement a problem, I gave myself some time (depending on the size of implementation) to think how to code from beginning to end, each process (literally everything), how am I going to implement. After that, it was a just a matter of fast-typing as I already know, what I am going to do exactly. I don't know exactly what is causing you this problems, but for me it gave a drastic improvement in case of implementing! Hope it helps!

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

    In terms of typing speed, me and my friends would try to beat each other on the linux game typespeed. It's fun, I recommend to take a few runs :)

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

      Typing speed is important but the more important is the way you think. i recomend do not write a single line of code not even the input or variables. Think of how to solve it organize your idea then see what are you going to use in the code like for example dfs just a loop, backtracking etc. then write the code.

      Spoiler
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +150 Vote: I do not like it

    Typing speed doesn't matter. I type with 4 fingers. I'm doing fine.

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it +120 Vote: I do not like it

      I agree that typing speed doesn't really matter for this, but make sure to take care of your hands! For the long term, just make sure your typing form is ergonomic enough not to give yourself hand problems.

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

      Although I type with one finger and that's another story.

      But how do you type with 4 fingers? I am curious :) Because I think from 1 to 4 would be a good improvement.

      • »
        »
        »
        »
        15 months ago, # ^ |
        Rev. 5   Vote: I like it +21 Vote: I do not like it

        2 fingers from each hand. I also type mostly like this and I get around 70 WPM in those typeracing websites, so it's possible to type quite fast even while using mostly only 4 fingers. I don't know if um_nik counts using thumb for space or right pinky for enter or left pinky for shift/ctrl though (because I don't).

        • »
          »
          »
          »
          »
          15 months ago, # ^ |
            Vote: I like it -70 Vote: I do not like it

          stop misguiding other people. We really just believe whatever red people say

          • »
            »
            »
            »
            »
            »
            15 months ago, # ^ |
              Vote: I like it +12 Vote: I do not like it

            Could you explain how I'm misguiding other people?

            • »
              »
              »
              »
              »
              »
              »
              15 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              so you actually use only 2 fingers from each hand huh ? see yourself type again I guarantee its more than that becoz you have a WPM of 70.

              • »
                »
                »
                »
                »
                »
                »
                »
                15 months ago, # ^ |
                Rev. 3   Vote: I like it +18 Vote: I do not like it

                I saw myself typing and

                I use mostly 4 fingers, but I use the left ring finger for Q and A and the right ring finger for P and sometimes O, so 6 fingers in total.

                And I still get 70 WPM while forcing myself to use only 4 fingers. I count only fingers that I use for typing out LETTERS, so I don't count the spacebar or shift. Actually with 6 fingers I get around 80-95 WPM in typeracer depending on typos, so my point still stands :)

        • »
          »
          »
          »
          »
          15 months ago, # ^ |
            Vote: I like it +24 Vote: I do not like it

          do you guys even type I use voice command to type the code

          Spoiler
        • »
          »
          »
          »
          »
          15 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It looks like I probably have the wierdest typing style.

          I tried writing random text now and realised I only use my 2 middle majorly. I also use my left ring finger to literally only type 'a' and right index just for space.

          Typing tests I somehow average 50-60 which now I feel isnt too bad

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

      You type with more fingers than I have friends

»
15 months ago, # |
  Vote: I like it +158 Vote: I do not like it

I think the most important thing is making sure to think about implementation explicitly. Before implementing, try to plan out what your control flow will look like, what your globals will look like, what helper functions you'll make, how you'll handle edge cases, etc. After the contest, you can go back and look at your code and try to identify which parts were unnecessarily messy and what could be done better; you can even rewrite it from scratch to be cleaner. Just make sure to think about what lessons to learn for next time.

»
15 months ago, # |
  Vote: I like it +26 Vote: I do not like it

This is a tough problem to fix in general, mostly because there are a lot of things that can cause or contribute to it. Are you losing the sense of where you were going when you have to focus on some particularly tricky localized bit of code? Are you too unwilling to admit when you've made a mess of some subproblem and need to mentally start over to get a clean solution? Are you forgetting to make sanity checks at the appropriate times while you're writing the code? Are you wasting too much time trying to improve code or ideas that don't need improving? Are you losing time to poor debugging practices? The list goes on: There are many, many ways to waste time in a contest.

I suffer from a similar problem, which I find to be much more severe when I participate without getting enough sleep. The next time I'm feeling motivated to try to work on my fundamentals instead of just having fun and trying to do OK with the skills I already have, I plan to record myself working on a few contests and then try to assess the key moments at which I make decisions that cost me a lot of contest time. After that, I can pick one or two of the most frequent and costly contributing factors, and just try to passively work on just those in my next contests.

That's perhaps a bit of an extreme measure, but I think the principle behind it is sound: Break up a nebulous, hard task ("get good at implementation") into more concrete and manageable tasks, in a way that relates to the actual difficulties of the former, then work on those one or two at a time.

»
15 months ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

I can't say I'm good at implementing but I'm particularly bad at it when I'm in a rush, in a rated contest, lockout or even in some OI's, so I can suggest you be calm and follow ecnerwala's advice because when I'm in a rush, I think I have to be fast and have no time to lose so I start to code my solution even without proving it and because of that I lose a tremendous amount of time.

TL;DR, before implementing, take a deep breath and think about every aspect of it because if you don't you will lose more time than you would spend on thinking. As Radewoosh said, think once before coding twice (or something like that idk)

»
15 months ago, # |
Rev. 2   Vote: I like it +73 Vote: I do not like it

Should I learn new C++ features? Should I start implementing something significantly longer than competitive programming problems?

No & no. Implementation speed mainly depends on how well you understand the solution. Also, it seems crazy to me to expect to be very efficient after just 2 years. Compared to now, I sucked at implementation speed after 2 years of CP. And it's not about typing speed. What about this:

Although practicing for around 2 years, I'm still very slow in implementation.

->

Because of practicing only for around 2 years, I'm still very slow in implementation.

»
15 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Actually I'm already used to think about the details of the solution, but I think I unnecessarily write long implementations. The solution to CEOI 2016/1 is just

  1. You start from one set: split each set into two subsets, in such a way that there are no two connected nodes in the same subset, until the interactor answers 1.
  2. Binary search the two subsets connected by the new edge, by querying prefixes of subsets.
  3. For each subset, binary search its node in the new edge.

The three subproblems have a similar structure, but they are actually different. Is it possible to write helper functions without making the code worse?

»
15 months ago, # |
  Vote: I like it +33 Vote: I do not like it

Anecdotally, implementing something significantly longer was somewhat helpful to me. It helped me think more about strong/clean abstractions, which become more and more necessary when code gets longer and longer. I mostly stopped competing in 2016, and when I came back in 2019, I think I was a little better at implementation than before (particularly longer code), and I think at least part of it is coding some larger projects in college. Your mileage may vary though, and I doubt this will happen for everyone. (Also, in this time, I learned a lot about C++; that was fun to me, but that's definitely useless for competitive programming almost everyone.)

  • »
    »
    15 months ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    Do you think that you would improve less between 2016 and 2019 if you just did CP?

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it +33 Vote: I do not like it

      Hard to say, but I probably wouldn't have improved as much in this direction. A more meta take is that if I had spent my time doing CP instead of classes/other things the whole time, I might not still enjoy competing today, and I would definitely be a worse software engineer.

»
6 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

I visited DMOJ after seeing the name in the blog and the platform seemed very good.Don't know why it's not very popular

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

I decided to try out 101597A and it took me around 25 minutes to have an idea how to solve it and then 11 minutes to implement the first WA solution, then 4 more minutes (two more attempts) to get AC.

One thing you can try is to record yourself while implementing a solution, then look where you spent the most time being blocked and then think why you were blocked there.

Ultimately I think this comes down to practice and I think it's better to practice by implementing many shorter problems than fewer longer ones. Typing speed is irrelevant, as long as you can type without looking at the keyboard, for the most part.

Also consider using macros, shortcuts and snippets in your editor.