Competitive Programming and Contests
This the Web page of "Competitive Programming and Contests" course at University of Pisa.
 Teacher: Rossano Venturini
 CFU: 6
 Period: First semester
 Language: English
 Classroom: here. Code is y7q4c5w
 Lectures schedule: Monday 911 Room C1 and Thursday 911 Room C1 – (Google Meet, link on our classroom)
 Question time: After lectures or by appointment
Goals and opportunities
The goal of the course is to improve programming and problem solving skills of the students by facing them with difficult problems and by presenting the techniques that help their reasoning in the implementation of correct and efficient solutions. The importance of these skills has been recognized by the most important software companies worldwide, which evaluate candidates in their job interviews mostly by the ability in addressing such difficult problems (e.g., see here).
A natural goal is to involve the students in the intellectual pleasure of programming and problem solving, also preparing them for the most important international online contests, such as Topcoder, Codeforces, LeetCode, HackerRank, CodeChef, Facebook Hacker Cup, Google Code Jam and so on, for internships in most important companies and their interviews. A desirable sideeffect of the course could be to organize and prepare teams of students for online contests.
The course will provide the opportunity of:
 facing with challenging algorithmic problems;
 improving problem solving and programming skills;
 getting in touch with some big companies for internships, scholarships, or thesis proposals.
Exam
You have two choices for the exam:

Option 1: Submit your solutions for the three handson assignments within the specified deadlines for each assignment.

Option 2: Submit your solutions for the three handson assignments, along with all the mandatory exercises, at a time that suits you. You can find the mandatory exercises highlighted in bold within the lecture materials provided below.
In either case, you will be required to participate in an oral examination covering all the topics covered in our course. You can schedule this oral exam by appointment.
Please note that all solutions must be written in Rust.
You have the opportunity to earn additional points through:

Active Participation: Actively engage in class discussions and activities.

Serious Participation in Online Contests: Engage seriously in online programming contests such as CodeForces, TopCoder, HackerRank, Google Code Jam, and more.

Successful Interviews with Major Companies: Achieving success in interviews with prominent companies.
It is highly recommended that you implement solutions for the problems presented in each lecture. This practice not only enhances your problemsolving skills but also provides valuable Rust programming experience.
I recommend creating a Github repository to centralize all your solutions and their corresponding descriptions. This repository can be set to either private or public visibility, ensuring that I can access it in either case. Please share the repository link with me, and make sure to keep it regularly updated so that I can monitor your progress effectively.
How to solve a problem
Here’s a stepbystep guide on how to effectively solve a problem:
 Read the Problem Description: Begin by carefully reading the problem statement. Ensure that you have a clear understanding of what the problem is asking you to solve.
 Understand with Examples: Examine any provided examples. Use these examples to validate your understanding of the problem’s requirements and constraints.
 Design a Trivial Solution: Start by designing a straightforward and naive solution to the problem. This is often referred to as a bruteforce approach. It may not be the most efficient solution, but it helps you get started and ensures that you have a working solution.
 Brainstorm for Efficiency: Once you have a working solution, think about how you can optimize it. Consider different algorithms, data structures, and strategies that might lead to a more efficient solution. Use running examples to help you visualize and refine your approach.
 Seek Help and Hints: If you’re stuck and unable to find a more efficient solution, don’t hesitate to seek help. Discuss the problem with other students, ask questions in the group, or consult resources like your course materials, relevant websites, or textbooks. Gathering hints and insights from others is a valuable part of the learning process.
 Document Your Solution: Write a brief description of your chosen solution in English. Explain the logic behind it and provide an analysis of its time and space complexity. This documentation helps you clarify your thought process and is valuable for future reference.
 Implement Your Solution: Write the code for your solution in Rust. Ensure that your code follows the algorithm you’ve designed and documented.
 Test and Debug: Submit your implementation to the problem’s platform or testing environment. Work on debugging and refining your code until it passes all the tests and produces correct results.
 Compare Solutions: Always compare your solution and implementation with existing ones if available. This can help you learn different approaches and best practices for solving similar problems.
 Iterate and Learn: Solving problems is a learning process. Don’t be discouraged if you encounter difficulties. Keep practicing, learning from your mistakes, and applying new techniques to improve your problemsolving skills.
By following these steps, you can systematically approach problemsolving tasks and increase your proficiency in tackling a wide range of challenges.
Background
If you’re looking to brush up on your understanding of fundamental algorithms and data structures, I highly recommend delving into the renowned book Introduction to Algorithms, 4th Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.
I strongly suggest you to watch the following video lectures as soon as possible.
 Insertion Sort and Merge Sort
 Heaps and Heap Sort
 Counting Sort, Radix Sort, Lower Bounds for Sorting
 Binary Search Trees
 AVL trees
 Hashing with Chaining
References
 Introduction to Algorithms, 4th Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, The MIT Press, 2022 (Amazon) [CCLR]
 Algorithms, 4th Edition, Robert Sedgewick, Kevin Wayne, AddisonWesley Professional, 2011 (Amazon) [RS]
 Algorithms, Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, McGrawHill, 2006. (Amazon) [DPZ]
 Programming Challenges: The Programming Contest Training Manual, Steven S. Skiena, Miguel A. Revilla, Springer, 2003 (Amazon) [SR]
 Competitive Programming 4: The New Lower Bound of Programming Contests, Steven Halim, Felix Halim, (here) [HH]
Rust References
 The Rust Programming Language
 The Rust Reference
 The Rust Standard Library
 Learning Rust
 Rust users forum
 Rustlings
Useful links
 Erik D Demaine, Srini Devadas, Nancy Ann Lynch, “MIT Design and Analysis of Algorithms”, MIT Algorithm course which includes video lectures
 Tim Roughgarden, “Algorithm specialization”, Coursera
 Visualgo: visualising data structures and algorithms through animation
 Geeks for Geeks: Company interviews preparation
 Interviews common coding questions
 How to: Work at Google — Example Coding/Engineering Interview Video
 Google’s Code Jam
 Topcoder
 Codeforces
 LeetCode
 HackerRank
 Geeks for Geeks
 LeetCode
 CodeChef  Data Structures and Algorithms links
 Geeks for Geeks: Top 10 Algorithms and Data Structures for Competitive Programming
 List of resources for competitive programming
Lectures
Date  Lecture  References  Problems 

18/09/2023  Introduction  Slides  Leaders in array, Kadane’s algorithm, and Missing number in array 
21/09/2023  Solutions of Trapping rain water and Sliding window maximum  Rossano’s notes  Trapping rain water and Sliding window maximum 
25/09/2023  Binary search  Rossano’s notes and USACO Guide  Find First and Last Position of Element in Sorted Array, Find the minimum in a rotated sorted array, and Search for a peak in an (unsorted) array 
02/10/2023  Trees: representation, traversals, and Binary Search Tree  Tree traversals  Maximum path sum 
05/10/2023  HandsOn 1. Deadline: 19/10/2023  
05/10/2023  Trees: representation, traversals, and Binary Search Tree. Two pointers trick  [CCLR] Chapters 10.4 and 12  Frogs and Mosquitoes 
09/10/2023  Sweep Line Algorithm  Rossano’s notes. Two pointers technique  Check if All the Integers in a Range Are Covered, Cow Steeplechase II, and Longest kGood Segment 
12/10/2023  Prefix Sums  Rossano’s notes  Subarray Sum Equals K, Continuous Subarray Sum, and Good Subarrays 
16/10/2023  Prefix sum: Fenwick tree (aka Binary Indexed Tree (BIT))  Rossano’s notes*. Wikipedia, tutorial, video, and visualgo.  Update the array 
19/10/2023  Applications of Fenwick tree and Range update with Fenwick tree.  Rossano’s notes*. Range updates on BIT. Tutorial. RMQ with BIT (optional)  Nested segments and Pashmak and Parmida’s problem 
23/10/2023  Segment Trees  Segment Tree: description, tutorial 1, tutorial 2, tutorial 3, video, and visualgo.  Solve Nested segments with Segment trees. 
26/10/2023  Segment trees: Applications  
30/10/2023  Segment Trees: Lazy Propagation and Persistency  Lazy propagation: tutorial and video.  Circular RMQ 
02/11/2023  Mo’s algorithm on sequences and trees  Rossano’s notes*. Optional: Mo’s algorithm on Trees  Powerful array and Tree and queries 
06/11/2023  Dynamic Programming: Fibonacci numbers, Rod cutting, and Shortest path on a DAG  Rossano’s notes*. [CCLR] Chapter 15.  
09/11/2023  Dynamic Programming: Minimum cost path and Longest common subsequence  Rossano’s notes*. Martin Gardner on Minimum cost path.  Longest common subsequence and Minimum number of jumps 
13/11/2023  HandsOn 2. Deadline: 27/11/2023  
13/11/2023  Dynamic Programming: 0/1 Knapsack, Fractional knapsack, and Subset sum.  Rossano’s notes*. 0/1 Knapsack problem: tutorial  Subset sum and 01 knapsack 
16/11/2023  Dynamic Programming: Longest increasing subsequence and Coin change  Rossano’s notes*  Longest increasing subsequence 
20/11/2023  Dynamic Programming: Longest increasing subsequence, Longest bitonic subsequence, and Largest independent set on trees  Rossano’s notes*  Longest bitonic subsequence 
23/11/2023  Greedy algorithms: Activity Selection, Job sequencing, and Fractional knapsack problem  Notes by Jeff Erickson. Job sequencing. Fractional Knapsack Problem  N meetings in one room, Magic numbers, Wilbur and array, and Alternative thinking 
27/11/2023  Greedy Algorithms: Boxes and Hero  Boxes and Hero. Huffman code: Section 7.4 in Notes by Jeff Erickson (optional).  Lexicographically maximum subsequence, Woodcutters, and Queue 
30/11/2023  Graph algorithms: BFS and DFS  [CCLR] Chapter 22  X total shapes, IsBipartite, and Fox and names 
4/12/2023  Graph algorithms: Strongly Connected Components and SingleSource Shortest Path  [CCLR] Chapters 22 and 23  Learning languages and Checkposts 
7/12/2023  Graph algorithms: Minimum Spanning Tree (and Disjoint Sets data structures)  [CCLR] Chapters 21 and 23. Kruskal: code, Disjoint Set: tutorial  Minimum spanning tree 
08/12/2023  HandsOn 3. Deadline: 06/01/2024 
Topics from past years
Date  Lecture  References  Problems 

2017  Centroid Decomposition of trees  Centroid Decomposition of trees: here, here, here, and here  
2017  String algorithms: KnuthMorrisPratt and Suffix array  KnuthMorrisPratt from [CLRS] Chapter 32.3. KnuthMorrisPratt. Optional: RabinKarp here from Algorithms on strings, trees, and sequences, D. Gusfield, Cambridge university press, here, and here. Suffix Array: Tutorial and implementation: here and here. Optional: Suffix Array in linear time here  Longest prefix suffix and Shift the string 
2017  String algorithms: LCP array, trie and ternary search trie  Computing LCP array: Kasai et al.’s algorithm and here. Ternary search trie and a video.  
2018  Heavylight Decomposition of trees. This lecture is not mandatory.  Heavylight Decomposition of trees: here, here, and here.  QTREE, QTREE2, QTREE3, GOT, and Chef and the tree. 
2021  Dynamic Programming: Edit distance, Longest palindromic subsequence, and Weighted job scheduling  Edit distance, Vertex cover, and Longest palindromic subsequence  
2022  Static RMQ with sparse table  RMQ and sparse table: tutorial 1, tutorial 2, paper, and code. Static RMQ in 2n + o(n) bits and constant time(optional). 
Further (optional) topics
 AhoCorasick String Matching Algorithm
 Convex Hull
 Interval tree
 Merge Sort Tree
 Manacher’s Algorithm: here and here
 Maximum flow
 Splay trees