nichke's blog

Poor implementation skills
By nichke, history, 2 years ago, In English

This may sound like a simple question to answer by saying simply solve more problems, but I'm looking for a more productive way, as I've already solved tons of problems.

So long story short, I've been trying to solve IOI 2022 D1P1 in a virtual contest for the last 4 hours on DMOJ and gave up 40 minutes before the ending of my session, as I was pissed by my poor implementation skills.

The plan went smooth — read problem, think about it for a while and implement what you get. I immediately went for finding solution to the N<300 subtask and it took me roughly ~40 minutes to get to it. And that's when hell begins, I've spent ~2.5 hours coding, testing and debugging my 50 line code that keeps producing wrong answer/does not compile. Once I've submitted, I thought cool, now I can try to optimize it down to N<3000.

In about 15-20 minutes of thinking I have a solution I believe should work (keep 3 dp arrays, with appropriate differences assigned to each of them, compress coordinates and use the same DP just instead of doing $$$O(N^3)$$$ keep the states down to roughly $$$O(N+M)$$$. Cool, I go to coding and finally rage quit after my code (in spoiler below) turns into a chaotic garbage that produces no correct answer. BTW I've tried to recreate the code by going line-by-line through my trivial DP and just changing up a bit and it went extremely bad.

Short code, which doesn't work
Naive DP

Now I'm wondering, how can I improve my implementation skill on large OI problems (this is not even close to being 'large', yet I've failed). Usually I don't have much problem doing a 30-40 lines problem, but this one really got me.

Is doing easy problems a better route perhaps than doing hard ones or should I focus on implementation heavy tasks exclusively? Thanks.

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

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This might help.

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

    Thanks, I'll give it a read.

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

    Fun fact: as the author of that blog, I got $$$12$$$ points on IOI 2022/1 for the same reason :(

    → Reply
»
2 years ago, # |
  Vote: I like it -27 Vote: I do not like it

LoL, first thing you MUST do is write: using namespace std;

So, now, just solve a lot of hard problems, and try to think more while coding. For example, stop after every small meaningful block of code, and think “What am I doing right now? Will it work? Does it have any corner cases? Could it catch RTE? Could it overflow? Are there any ways to do this more efficiently?” etc. Also, before trying to implement something, think one more time if anything that you are doing actually makes sense.

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

    I was convinced using namespace std wouldn't work with the IOI checker on that problem, usually I do use it. ;)

    The other tips make perfect sense, as I don't really do it like that. I more often go like — okay let it just flow and I'll figure things out as I'm going, but this obviously isn't the best strategy. Thanks.

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

    jiangly:

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

      what?

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

        He never uses the snippet you've mentioned, always writing std::.

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

    No.

    → Reply
»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Consider doing div3 rounds.

Since they're designed for beginners, they quite often have tasks that focus on implementation. I think that the most recent div3F is a great example of what I mean, because there is tons of ways to do it, however you can set a challenge for yourself to find the most elegant solution.

If my advice doesn't help you, I still think that its great for 1300-1700 rated people who might stumble upon your blog to try it.

Fun fact
→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    code golfer here, I don't think a*b*c&&cout<<"Yes\n"; is more elegant than if(a&&b&&c)cout<<"Yes\n";. There's always a borderline where after crossing your code looks either like literal crap or some obfuscation

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

Not sure how much I can help since I also struggled with this problem, but I feel like for DP problems like this, it really pays off to follow the general implementation advice to think about implementation before coding.

The code is only 50 lines long, and a lot of that is stuff like coordinate compression that is the same every time and shouldn't pose much of an issue. The really troublesome part is getting the DP transitions absolutely correct, which you can do separately, maybe even on paper, and then it will be a lot easier to translate into code. If you have the DP transitions correct, then writing them is a matter of just typing out 8 lines or so, which can be done really quickly, so you lose very little time from doing this.

In the coding side, abstractions can also help: instead of writing a binary search in the middle of the DP transitions, you can make a function that tells you "index of coordinate", and then you can worry about both parts independently instead of having to look at the two at the same time.

→ Reply