Snackdown Training Camp, Day 1

Lecture 1 : Persistence segment tree with its applications and merge sort tree. By Sergey Kulik.

Lecture Video
Slides

Problems:

• 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 Video
Slides

Lecture 3: Max flow with its applications. By Anudeep Nekkanti

Lecture Video
List of Problems:

• Spoj – coconuts
• Topcoder 633 – 600 ptr
• Topcoder 632 – 500 ptr
• Topcoder 594 – 500 ptr
• Code Marshal ICPC warm-up 2014 problem E

• 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.

Lecture Video
Sample problems:

• http://codeforces.com/contest/449/problem/D
• https://www.codechef.com/COOK52/problems/COVERING
• https://www.codechef.com/IPC15P2B/problems/STR_FUNC
• https://www.codechef.com/AMR14ROS/problems/AMR14F

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).)
• http://people.seas.harvard.edu/~minilek/cs224/fall14/lec/lec25.pdf
• https://www.youtube.com/watch?v=M42rQM0vC4g
• http://www.usaco.org/index.php?page=viewproblem2&cpid=129
• http://www.usaco.org/current/data/sol_skyscraper.html
• 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)
• http://codeforces.com/group/qcIqFPYhVr/contest/203881/problem/K
• http://codeforces.com/blog/entry/19989?#comment-248208

For further reading:

• http://blog.jiaweigao.com/notes/2015/11/21/Zeta-Transform-and-Mobius-Transform/
• http://arxiv.org/pdf/1105.2942v2.pdf
• http://www-sop.inria.fr/mascotte/seminaires/AGAPE/lecture_notes/Agape%2009%20-%20Petteri%20Kaski%20-%20Linear%20and%20bilinear%20transformations%20for%20moderately%20exponential%20algorithms.pdf
• http://fileadmin.cs.lth.se/cs/Personal/Thore_Husfeldt/slides/GDR-IM-2012.pdf
• http://web.stanford.edu/~rrwill/presentations/subset-conv.pdf
• 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

Lecture Video
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