dunpeal's blog

By dunpeal, 5 months ago, ,

pllk in the Dynamic Programming chapter of his book describes a 3 step approach to DP problems:

1. Find a recursive solution to the problem.
2. Use memoization to improve the time complexity of this top-down recursive solution.
3. Transform to a bottom-up iterative solution.

(Step 3 is practically optional since the time complexity should be the same as the memoized top-down recursive solution, but the constants will be better and the logic will often be more straightforward.)

pllk demonstrates this 3 step process with the Coin Change problem, and for this first example, the method works nicely.

However, the very next example is Longest Increasing Subsequence, in which it's not at all obvious how to complete the first step of writing a recursive solution.

So the 3 step method above works for many problems in which you can actually take the first step and identify the recursive solution. In fact it seems like the critical, most important and difficult step: if you can get past step 1, steps 2 and 3 are rarely a problem.

But what do you do when step 1 isn't obvious, and you get stuck not being able to make progress with this method?

• +22

By dunpeal, history, 5 months ago, ,

It seems crucial to practice on problems of the right difficulty level. Too easy, and you waste your valuable practice time and energy solving problems you already mastered and gaining nothing new in skills or knowledge. Too hard, and you just get stuck and demotivated, banging your head against a solid wall without making any progress or improvement.

Seems like the best are problems that are difficult enough to challenge your current skill level, but not so difficult that you'll just hopelessly crash against them. How do you identify such problems?

One method I tried was relying on the new "difficulty rating". Unfortunately it seems to be very inaccurate, with many problems having unreasonably high or low difficulty score.

• +12

By dunpeal, history, 15 months ago, ,

Typically upon reading a problem, I either see the solution immediately, or get stuck with no idea how to proceed. Getting stuck usually means spending hours just thinking about it slowly, getting distracted, and failing to make any progress.

What is the optimal amount of time to keep thinking about a tough problem before reading the editorial solution?

For example, if I spend 5-6 hours in "stuck" mode, not working on anything else, and often still failing to solve the problem in the end — it seems like an inefficient waste of valuable practice time.

Of course, just giving up and solving easy problems doesn't improve my skills either.

• +6

By dunpeal, history, 19 months ago, ,

I live in New York City and I would like to meet other competitive programmers who are into algorithmic contests like Codeforces, AtCoder, CS Academy, etc.

How do I make that happen?

Ideally, there would be a club with some real-world meetings, but I have no idea how to find such a club here.

• +15

By dunpeal, 20 months ago, ,

I recall Codeforces having MathML / MathJax support a few months ago. With this support, mathematical notation in problem descriptions and analysis / editorials was rendered beautifully in clear fonts on the screen, such that it was a pleasure to read.

Recently, however, mathematical notation in Codeforces on both Chrome and Firefox is rendered as bitmap images of much inferior quality.

Was MathJax turned off for some reason? Is there a way to turn it back on?

• +16

By dunpeal, history, 22 months ago, ,

I'm trying to improve my competitive programming skills here on Codeforces, but I often lack the basic knowledge of algorithms and data structures required to solve problems on competitions, even the easier ones.

I need an online course that will teach me the basic algorithms, data structures, and competitive programming techniques necessary for competitions.

What is the best such course available online?

• +6

By dunpeal, 4 years ago, ,

I'm new to competitive programming, and looking for every opportunity to learn and practice. So far I found two websites featuring consistently high-quality problemsets and editorials: Codeforces and TopCoder. All the problems I found on these two sites were interesting and well-tested, though editorials on TopCoder were sometimes hard to find or missing altogether.

I checked the 3 other large websites: HackerRank, CodeChef, HackerEarth. Unfortunately their quality was much less consistent. Several problemsets suffered from vague statements, and their test suites were often too small to catch my mistakes. Moreover, many problems could be solved by coding up ad-hoc solutions or standard algorithms, which is more of a coding exercise than what I'm looking for: puzzles requiring creative problem-solving skills, like those I found here and in TopCoder.

I've been looking for ways to identify good problemsets. One method I found is checking their setters and testers. Some contests on the above sites are set and tested by orange/red Codeforces members, and these seem to be of very high quality. For instance, this October contest on HackerEarth set by Errichto and tested by akulsareen which was very interesting, well-tested, and followed by excellent editorials.

So now I sometimes search for blogs posts on Codeforces featuring the tags for the other 3 big sites. If I find a contest set and tested by orange or red members, then I use it for practice. On the other hand, if I come across contests on these websites for which the setter and tester are not known to be high-rated competitive programmers, then I just skip it. Indeed all the really low-quality contests I encountered belonged to this last category.

What are your thoughts? Do you have other recommended methods to find high-quality problemsets?