- Counting : You are going to see a lot of problems like "Count the number of ways to do X". In most of the cases, enumerating all possible ways is simply not going to work, and you are expected to use some kind of . To be able to solve counting problems properly, you need to have a good understanding of certain topics such as:
- : Ubiquitous in counting problems. In particular, learn to come up with recurrences for counting. Also, learn to convert recurrences of high complexity to lower complexity
- Matrix exponentiation : In the case of recurrences that have constant coefficients, it is possible to express the final state vector as the product of the power of a matrix and the initial state vector. A good example is . This trick helps to reduce the complexity of finding Nth term of some recurrences from O(N) to O(Log N)
- : Many counting problems with symmetries can be reduced to finding a few cases and multiplying them with some binomial coefficients. So learn to calculate these efficiently depending on the type of problem. There are different kinds of precomputations one does. Also, try to learn the properties of binomial coefficients modulo primes.
- : More of a proof-aid technique rather than something that you directly apply. But I have used this in cases where I was required to find two cases which share some property. can be thought of as the probabilistic variant of pigeonhole principle, but it is not that commonly used.
- : How to formalise dealing with double counting. It is sometimes so much easier to double count in the beginning and use inclusion-exclusion later than to try some double counting avoiding recurrence
- Subsets and Permutations : Learn to generate subsets of a set and permutations of a sequence. There are some counting problems where you are expected to sum up quantities over permutations or subsets. DP over subsets is something that you should learn too in this regard.
- Indistinguishable and distinguishable objects : Learn the difference, and learn how counting changes between the two cases.
- Lattice problems : Counting the number of ways to go between two points on a lattice with various kinds of restrictions is a very common problem. Learn the basic method, and how things like binomial coefficients and appear in the solutions.
- Counting on graphs : The questions of this type that I have seen commonly include tree DPs. Counting problems on non-tree graphs are usually hard. You see problems coming up based on once in a while too.
- : I have seen this coming up in contests only a couple of times. But learn this and if something comes up, it should be easy for you.
- Learn to work with moduli : Most of the times, you are asked to do the counting mod some big prime (most favourite is 10^9 +7). Learn to do the calculations without overflow, and learn some basic properties of primes from group theory which help solve some problems.
- Probability and : Here are the basic things you should know:
- Calculating probabilities as ratios of counting problems : Do this and you can calculate things to very good accuracy
- Recurrences for probabilities and expectation values : In a lot of cases, even when you can count and take ratios to get probabilities, it is much easier to find a recurrence directly in terms of probabilities. Taking care of double counting can be a pain though
- Linearity of expectation value : Learn to use it right (I can't) and many expectation value problems should be cakewalks for you
- : Modified random walk problems come up very often as probability/expectation value problems, so learn the basic results
- Coin toss problems : Another set of practically overused problems
Saturday, July 1, 2017
Beginner's Guide: Discrete Mathematics And Programming Contests
As a student of CSE, one must complete a course on Discrete mathematics. Many then become confused why they should even learn this mathematical subject. Discrete mathematics is a vast topic, but here are some essential things that you should know to be able to solve programming contest problems:
In Part 2 , I have discussed 3 coding problems out of 6. Here we will talk about the next 3 coding problems. Problem 4: Write a function...
Problem link from hackerrank The solution is given below with the introduction of DFS. Introduction: Algorithm: DFS (Depth Firs...
I have been away for quite some time now. The reason is I was quite busy with my academic thesis and general academic pressure. Now I do fe...