ntk7643's blog

How to improve implementation skills?
By ntk7643, history, 5 hours ago, In English

I just wasted 4 hours of my life this afternoon for a problem.

Basically, I saw the idea of the problem for about 10-15 minutes after reading, but the implementation was hell for me. After quickly wrote the code about 15 minutes later, I sank in a bunch of WAs and lots of debugging codes. I even had to write the checker myself, when bugs kept going until AC after a total of 4 hours.

I saw other people did the problem in just under 1 hour, which I estimate I could do if I (almost) got the code right from first try and didn't fall into that debugging loophole.

This made me questioned, how could I improve my skills at implementation? Can you guys share some tips for me?

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
5 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ntk7643 (previous revision, new revision, compare).

→ Reply
»
5 hours ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

If anyone wonder about the problem I mentioned, I can't share the link since it's private. However, I can give a simplified version of the problem here:

Given $$$n$$$ segments $$$[l_1, r_1], [l_2, r_2],..., [l_n, r_n]$$$ and a positive integer $$$d$$$, find $$${a_1, a_2,..., a_n}$$$ such that:

  • For every $$$1 \le i \le n, l_i \le a_i \le r_i$$$;

  • $$$max(a_1, a_2,..., a_n) - min(a_1, a_2,..., a_n)$$$ is minimized;

  • $$$\Sigma_{i=1}^{n} x_i = d$$$.

→ Reply
»
4 hours ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

  1. solve more

  2. solve more

  3. if you're not practicing for OI, use templates for common algorithms and data structures instead of coding them from scratch

→ Reply
»
4 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

For debugging, most of these are obvious but:

  • Compile with warning flags (i.e. in C++ -Wall -Wshadow -O2)
  • Spam print statements to find at what point the code goes wrong
  • Think about the parts of the code you were most and least comfortable with
  • Make sure you didn’t mix up two variables or index and array[index]
  • How exactly is your code wrong? Is it overcounting or undercounting? Giving an invalid construction or suboptimal construction?
  • Edge cases? (be careful with this one, an edge case could actually only be because your solution is wrong)
  • Don’t be scared of implementing implementation heavy problems, you won’t get better by not doing them, and oftentimes you’ll find they’re not as bad as you thought
→ Reply