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 9-11 Room C1 and Thursday 9-11 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 side-effect 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 hands-on assignments within the specified deadlines for each assignment.

  • Option 2: Submit your solutions for the three hands-on 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 problem-solving 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 step-by-step 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 brute-force 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 problem-solving skills.

By following these steps, you can systematically approach problem-solving 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.


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, Addison-Wesley Professional, 2011 (Amazon) [RS]
  • Algorithms, Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, McGraw-Hill, 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



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 Hands-On 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 k-Good 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 Hands-On 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 0-1 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 Single-Source 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 Hands-On 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: Knuth-Morris-Pratt and Suffix array Knuth-Morris-Pratt from [CLRS] Chapter 32.3. Knuth-Morris-Pratt. Optional: Rabin-Karp 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 Heavy-light Decomposition of trees. This lecture is not mandatory. Heavy-light 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