nicksms's blog

How to trick myself into wanting to do implementation problems?
By nicksms, history, 20 months ago, In English

This is gonna sound like a really dumb question, but how should I go about trying to trick myself into wanting to do implementation problems?

I've noticed that for pretty much everything else, how much I want to do something is directly tied to how much enjoyment I get from it after the fact -- solving problems in general, for instance, is something I look forward to since I feel good after doing it. And I do feel quite good after finishing implementation problems, but for some reason I cannot stop dreading them.

One thing I've found (this could be a cause or a symptom) is that debugging implementation problems genuinely takes the soul out of my body, whereas if my math is incorrect and I have to go back and fix it I don't feel bad at all.

Still I feel like I have the potential to enjoy them, as I feel more satisfied with getting them than with almost any other type of problem. Sometimes I even feel like I actually want to do them, but every time that happens I just think back on the few that I've done that have gone horribly wrong. How should I go about getting myself to enjoy them? Should I just try medium ones until I can tell myself that debugging really isn't as bad as I think it is? Should I practice on ICPC problems (even though for ICPC, I'm not usually the one coding)? Should I be looking at failing test cases or trying to debug without them (remember that I'm not exactly trying to get better at implementation so much as I am trying to enjoy it more)?

Please advise. I'll be working on Kattis: keys when I have free time today to try to get my foot in the door, since I remember seeing that the implementation for that was fairly frustrating.

Any practice problems (especially with a math flavor to them) would be appreciated.

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

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

Most of the time wrong solutions for implementation problems happen because you don't think about the code's structure enough before you start writing it.

Try to think about every line of code. Ask yourself questions like:

  • Is this small piece of code working correctly?
  • Is this small piece of code even needed?
  • Can this small piece of code be simplified?

It is also useful to check the whole code as an idea. Why would your code work correctly?

When I write code, I always debug each important step of the code. For example, when you create a convex hull, don't code any further. Check if on all samples the hull is created correctly, and only then you may continue coding. Because if your code contains a lot of unchecked code, each part of it may be wrong, and it might take a lot of time to spot the problematic place.

I highly recommend you adding some debug macros which only print on your local machine. You can take a look on my submission 198933152. I have debug, line, name marcoses that only work on my local machine with ENABLE_DEBUGGER defined. These macroces are extremely useful, you may copy them if you want.

Also, compiling with debug flags may spot some runtime errors. My programming environment has things called modes, which are just compilation commands for g++. Here is a debug mode:

Spoiler

Hope this helped :)

→ Reply
»
20 months ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

This advice has been rescinded in light of recent changes in my working style.

→ Reply
»
20 months ago, # |
  Vote: I like it +16 Vote: I do not like it

I like approaching implementation problems on the mindset of thinking on regular problems but instead of having an idea to solve the problem, you try having an idea on how to code it in a reasonable manner.

I still enjoy other types of problems more but theyre less painful to me now.

→ Reply
»
20 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Challenge yourself, how neatly can I code this thing?

→ Reply
»
20 months ago, # |
  Vote: I like it -19 Vote: I do not like it

my solution: quit CP and play league of legends instead

→ Reply
»
20 months ago, # |
  Vote: I like it +21 Vote: I do not like it

A few excellent approaches are already mentioned above.

I'd like to add another few. But every one of these is a long shot. They won't help overnight. Rather, they will help to broaden and enrich the base of your coding skills.

  • Try different programming languages. You will probably still do contests in C++ in the end. But seeing the different approaches you require in different languages, the strengths of different programming paradigms and standard libraries, you will surely take some of the bits and pieces with you.
    For example, knowing that you can code without variables in a functional language, like Haskell, makes you need less variables in any language. Learning the way Rust treats memory and ownership will leave a trace in your coding style as well. After seeing some particularly strong or useful standard libraries, you may discover neat analogs in your library of choice. Looking at the debugging process in other languages may help you find similar tools for C++.
    As a result, your code will be cleaner, and your debugging will be less painful.

  • Try another, longer contest format, like marathons or heuristic contests or bot fights. Longer programs call for quite different skills. Still, these skills are very useful when it comes down to implementation in short contests.

  • In a similar vein, try writing a project with life span longer than that of a typical contest solution. Maybe attend a hackathon, or a game jam, or just code something you personally like. Maintaining a project helps you think more of how your code is organized. Ultimately, this leads to cleaner code, and to less pain coding.

To sum it up, there's much more about programming than coding small throwaway solutions to hard algorithmic problems in C++. Perhaps you already see how general mathematical skills are reusable in these problems. Well, general programming skills are, too. Acquire more of them. And good luck!

→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    • I've used a lot of different languages in the past, but not much else than C++, Java, and Python for CP specifically -- honestly I've been frustrated at how C++ doesn't quite have the same functional utilities that Python or any LISP would. When you say try different languages, should I actually try to code up problems in them? Or should I just learn them?
    • I'd actually like to try heuristic contests, haha. Are you aware of any team heuristic contests? I remember hearing about a timetabling competition a while back...
    • I've got a little bit of experience with this, but my main issue is that code that I write for maintainable projects usually ends up SUPER object-oriented in nature (this is, I think, an artefact of the fact that I have only really ever used Java for long projects). Should I try to make some less object-oriented project, so that I can get used to maintaining something a little closer to what I would be doing in contest?

    And regarding reusing mathematical insight, I think I in particular might have a bit of an issue with "pulling back" solutions from problems where I've gotten to the solution from a long series of reductions/substitutions. Should I focus on getting better at this, or should I try to change my approach so that I don't really need to think of a problem under so many layers? (watered-down example of this issue: 1497E2 - Square-Free Division (hard version), which I approached like an interval scheduling problem and then realized that that idea was not really necessary for the solution -- my code for this is still messy and does not work)

    → Reply
»
20 months ago, # |
  Vote: I like it +27 Vote: I do not like it

A particularity I'd like to mention about your solutions' code.
Consider the following approach.

Good code is not the most clever code.
It's the most trivial code.

When the code is clever, there's plenty of things that the coder can do wrong.
When the code is trivial, there's much less space for bugs.

The above is of course not the hard rule for every program and every situation.
Still, it is a side of coding to consider, and maybe embrace.

→ Reply