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
  • Lectures schedule: Monday 16-18 Room C and Wednesday 14-16 Room C1
  • Telegram Group: here
  • Teams Group: here
  • 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

Loading, please wait
Date
Lecture
References
Problems
16/09/2024IntroductionSlidesLeaders in array, Kadane’s algorithm, and Missing number in array
18/09/2024Introduction to RustSlides 
23/09/2024Solutions of Trapping rain water and Sliding window maximumRossano’s notesTrapping rain water and Sliding window maximum
25/09/2024Binary searchRossano’s notes and USACO GuideFind 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
30/09/2024Trees: representation, traversals, and Binary Search TreeTree traversalsMaximum path sum
02/10/2024Trees: representation, traversals, and Binary Search Tree. Two pointers trick[CCLR] Chapters 10.4 and 12Frogs and Mosquitoes
07/10/2024Hands-On 1. Deadline: 21/10/2024  
09/10/2024Sweep Line AlgorithmRossano’s notes. Two pointers techniqueCheck if All the Integers in a Range Are Covered, Cow Steeplechase II, and Longest k-Good Segment
14/10/2024Prefix SumsRossano’s notesSubarray Sum Equals K, Continuous Subarray Sum, and Good Subarrays
16/10/2024Prefix sum: Fenwick tree (aka Binary Indexed Tree (BIT))Rossano’s notes*. Wikipedia, tutorial, video, and visualgo.Update the array
21/10/2024Applications 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/2024Segment TreesSegment Tree: description, tutorial 1, tutorial 2, tutorial 3, video, and visualgo.Solve Nested segments with Segment trees.
28/10/2024Segment trees: Applications  
30/10/2024Segment Trees: Lazy Propagation and PersistencyLazy propagation: tutorial and video.Circular RMQ
04/11/2024Mo’s algorithm on sequences and treesRossano’s notes*. Optional: Mo’s algorithm on TreesPowerful array and Tree and queries
06/11/2024Dynamic Programming: Fibonacci numbers, Rod cutting, and Shortest path on a DAGRossano’s notes*. [CCLR] Chapter 15. 
06/11/2024Hands-On 2. Deadline: 24/11/2024  
13/11/2024Dynamic Programming: Minimum cost path and Longest common subsequenceRossano’s notes*. Martin Gardner on Minimum cost path.Longest common subsequence and Minimum number of jumps
18/11/2024Dynamic Programming: 0/1 Knapsack, Fractional knapsack, and Subset sum.Rossano’s notes*. 0/1 Knapsack problem: tutorialSubset sum and 0-1 knapsack
20/11/2024Dynamic Programming: Longest increasing subsequence and Coin changeRossano’s notes*Longest increasing subsequence
25/11/2024Greedy algorithms: Activity Selection, Job sequencing, and Fractional knapsack problem. Dynamic Programming: Longest bitonic subsequence, and Largest independent set on treesNotes by Jeff Erickson. Job sequencing. Fractional Knapsack ProblemN meetings in one room, Magic numbers, Wilbur and array, and Alternative thinking
27/11/2024Greedy Algorithms: Boxes and HeroBoxes and Hero. Huffman code: Section 7.4 in Notes by Jeff Erickson (optional).Lexicographically maximum subsequence, Woodcutters, and Queue
02/12/2024Boyer-Moore algorithm for majority element. Misra–Gries heavy hitters algorithm. Finding a duplicated element in a array: Solution with or without destroying the array, ir with log n passes.  
04/12/2024Suffix ArraySuffix Array: Tutorial and implementation: here and here. 
05/12/2024Hands-On 3. Deadline: 10/01/2025  



Last Year Lectures


Topics from past years

Loading, please wait
Date
Lecture
References
Problems
2017Centroid Decomposition of treesCentroid Decomposition of trees: here, here, here, and here 
2017String algorithms: Knuth-Morris-Pratt and Suffix arrayKnuth-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 hereLongest prefix suffix and Shift the string
2017String algorithms: LCP array, trie and ternary search trieComputing LCP array: Kasai et al.’s algorithm and here. Ternary search trie and a video. 
2018Heavy-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.
2021Dynamic Programming: Edit distance, Longest palindromic subsequence, and Weighted job scheduling Edit distance, Vertex cover, and Longest palindromic subsequence
2022Static RMQ with sparse tableRMQ and sparse table: tutorial 1, tutorial 2, paper, and code. Static RMQ in 2n + o(n) bits and constant time(optional). 
2023Graph algorithms: BFS and DFS[CCLR] Chapter 22X total shapes, IsBipartite, and Fox and names
2023Graph algorithms: Strongly Connected Components and Single-Source Shortest Path[CCLR] Chapters 22 and 23Learning languages and Checkposts
2023Graph algorithms: Minimum Spanning Tree (and Disjoint Sets data structures)[CCLR] Chapters 21 and 23. Kruskal: code, Disjoint Set: tutorialMinimum spanning tree


Further (optional) topics