Competitive Programming LDN#3
We are Competitive Programming London, we meet once a week to practice on some algorithm problems from Codeforces, Hackerrank, Leetcode and other problems. The general format for our meetings it to work on several problems in pairs and then discuss eachother’s solutions as a whole towards the end.
in this meetup we began to delve into Dynamic Programming problems.
Dynamic programming (DP) is about finding some work (usually recursive) that would repeat multiple times unnecessarily, and so would be better to save these subproblems over time.
DP problems are quite common in competitive contests. DP can often seem magical but with practice it starts to make some more sense. We started watching the first video in Errichto’s series, which consisted of a solid exponential. The following few paragraphs will summarise the video.
What kind of programs are DP problems applicable to?
- Combinatorics (count something, number of ways)
- Minimize or maximize a value
- Yes / No questions
For 2 and 3, it is always a good idea if a greedy approach would work before jumping to DP.
There are 2 techniques to apply DP solutions to a given problem: iterative and recursive. Both of these are quite similar, but let us look at some differences:
Some of the top compeitive programmers including Errichto seem to prefer iterative DP solutions.
Problems solved
Here are the problems we solved during the session:
- Febanocci (from video)
- Staircase problem (from video)
- Staircase problem modified (from video)
- Min grid path problem (from video)
- Intelligent Girl
- Ilya and Queries
We will continue with more advanced. DP problems next time.
If you are in London I hope to see you in the next event :). Interested in joining our slack group to discuss problems like this? Drop me a line on twitter or linkedin to join
