Lecture 1 : Persistence segment tree with its applications and merge sort tree. By Sergey Kulik.
- The model problem: http://www.spoj.com/problems/COT/
- Polish Camp CHT problem: http://main.edu.pl/en/archive/ontak/2010/wyc
- Count the number of comparisons in a QuickSort http://codechef.com/problems/SORTING
- Problem SEGSUMQ from SnackDown elimination (about the fractions): https://www.codechef.com/problems/SEGSUMQ
- Problem Cat-Cation Rentals (greedy cover with segments of length >= P): https://www.hackerrank.com/contests/w20/challenges/catcation-rental
Lecture 2: Fast Fourier Transform and its applications. By Kevin Charles Atienza.
Lecture 3: Max flow with its applications. By Anudeep Nekkanti
List of Problems:
- Spoj – coconuts
- Topcoder 633 – 600 ptr
- Topcoder 632 – 500 ptr
- Topcoder 594 – 500 ptr
General tip from Anudeep : Please try solving ACM ICPC Jakarta 2013 problem set. It is very nice.
Lecture 4: Zeta Function and its applications to optimizations in dynamic programming. By Arjun Arul.
References for Yate’s DP, Fast Zeta and Mobius transforms
- The theory done in the lecture was taken from this book: https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf Chapter 10.2 and for further reading: Chapter 10.3
- https://cryptoragbag.wordpress.com/2011/04/23/yates-algorithm-for-the-zeta-transform (Note that there is a small typo in this. In the definition of g_i(Y), the term inside the summation should be f(X), and not f(Y).)
- https://apps.topcoder.com/forums/%3bjsessionid=FE9F68013A73A33EF002E7DFEE2F3210?module=Thread&threadID=729990&start=0&mc=7#1465064 (Don’t get confused by the last comment in this. It’s wrong)
For further reading:
- A great recent tutorial on this: http://codeforces.com/blog/entry/45223
Lecture 5: Centroid decomposition and use of reflections in some combinatorial problems. By Akashdeep Nain
Please check the following link for an amazing reference about the concept and related problems on Centroid Decomposition https://threads-iiith.quora.com/Centroid-Decomposition-of-a-Tree