Page of the course "Competitive Programming and Contests" at Department of Computer Science, University of Pisa
Clone or download
Latest commit 1edd106 Jan 14, 2019
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
Exams Exam Jan 14, 2019
code final touches on segment trees Oct 25, 2017
notes Fix lecture notes Dec 10, 2018
slides STL style updated Oct 7, 2018
README.md Exam Jan 14, 2019
Solutions.md Lecture 6 Oct 17, 2017

README.md

Competitive Programming and Contests

  • Teacher: Rossano Venturini
  • Teaching assistant: Giulio Ermanno Pibiri
  • CFU: 6
  • Period: First semester
  • Language: English
  • Lectures schedule: Monday 16-18 (C) and Tuesday 14-16 (Lab-I).
  • Question time: After lectures or by appointment
  • Google group to discuss solutions

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 TopcoderCodeforcesHackerRank, 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

The exam consists of two parts: Homeworks 50% - Written/oral test 50%.

Extra points for

  • active participation to our Google group
  • serious participation to online contests, e.g., CodeForces, TopCoder, Hacker Rank, Google Code Jam, ...
  • successful interview with a big company

For full marks in the "Homeworks" part of the exam you must solve all the problems. I'll check your solutions by reading the code and their descriptions and by submitting them to the problems' sites. I should be able to submit any solution without any change. A solution that doesn't pass the tests (for any reason) will be considered wrong!

Please create a github repository to collect all your solutions and their descriptions. The repository can be either private or public. In both cases I should be able to access it. Please send me a link to your repository and keep the repository updated. I should be able to monitor your progresses.

The quality of your code will be evaluated. As your style will improve a lot with practice, I'll evaluate only the quality of the last submitted solutions.

Type Date Room Text
Written/Lab 23/01/2018 9:30 H Text, TestSet, and Solution
Written/Lab 14/02/2018 9:30 M Text, TestSet, and Quadratic solution
Written/Lab 12/06/2018 14:00 H Text, TestSet, and Solution
Written/Lab 06/07/2018 9:30 I Text and TestSet
Written/Lab 14/01/2019 14:30 H Text and TestSet
Written/Lab 04/02/2019 14:30 H

How to solve a problem

  • Read carefully the description of the problem.
  • Make sure you understand the problem by checking the examples.
  • Design a first trivial solution.
  • Think about a more efficient solution. The use of some running examples usually helps a lot in finding a better solution. If your are not able to find such solution, try to find some hints by discussing with other students, by asking questions on the group, by looking at the solution in our Web page, or by searching on internet. This is perfectly fine for the first problems and for most difficult ones. In any case, make sure you really understand the solution and the properties it is exploiting!
  • Write a brief description of your solution in English. Provide an analysis of its time and space complexity.
  • Implement your own solution in C++.
  • Submit your implementation to the problem's site. Fix it until it passes all the tests.
  • Always compare your solution and your implementation with existing ones.

Background

If you wish to refresh your mind on basic Algorithms and Data Structures, I suggest you to look at the well-known book Introduction to Algorithms, 3rd 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,  3rd Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, The MIT Press, 2009 (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 3: The New Lower Bound of Programming Contests, Steven Halim, Felix Halim, (here) [HH]
  • Competitive Programmer's Handbook, Antti Laaksonen (here) [L]
  • The C++ Programming Language, 4th Edition, Bjarne Stroustrup, Addison-Wesley Professional, 2013 (Amazon)
  • The C++ Standard Library: A Tutorial and Reference (2nd Edition), Nicolai M. Josuttis, Addison-Wesley Professional, 2012 (Amazon)

Useful links

Lectures

Date Lecture References Problems
17/09/2018 Introduction Slides Leaders in array (solution), Kadane's algorithm (solution), Missing number in array (solution), Trapping rain water (solution), and Sliding window maximum (solution)
18/09/2018 Solutions of Trapping rain water and Sliding window maximum Rossano's notes* Next larger element (solution), Towers (solution), and Finding Team Member (solution)
24/09/2018 Searching and Sorting: Binary Search, Merge Sort, QuickSort, Counting Sort, and Radix Sort. Rossano's notes*. [CCLR] Chapters 2.3, 7, and 8. Binary search. Exponential search. Interpolation search (optional) Inversion count (solution) and Largest Even Number (solution)
25/09/2018 Trees: representation, traversals, and Binary Search Tree Rossano's notes*. [CCLR] Chapters 10.4 and 12. Tree traversals. Euler Tour. Sieve of Eratosthenes Firing employees (solution), Check for BST (solution), Preorder traversal and BST (solution), and Maximum path sum (solution)
01/10/2018 Prefix sum: Binary Indexed Tree (aka BIT or Fenwick tree) Rossano's notes*. BIT: descriptiontutorialvideo, visualgo, and code. Ilya and Queries (solution), Alice, Bob and chocolate (solution), Number of ways (solution), Little girl and maximum sum (solution), and Update the array (solution)
02/10/2018 No lecture
08/10/2018 Standard Template Library (STL) Slides. Tutorial and STL algorithms Megacity (solution), Find pair (solution), and Two heaps (solution)
09/10/2018 Standard Template Library (STL). Coding Slides
15/10/2018 Segment Trees and Lazy Propagation. Segment Tree: description, tutorial, video, visualgo, slides and code. Lazy propagation: tutorial and video.) Circular RMQ
16/10/2018 Coding: applications of BIT. Range update with BIT. Static RMQ with sparse table. Rossano's notes*. Sparse table: tutorial, paper, and code. Range updates on BIT. Sparse table for static RMQ. Static RMQ in 2n + o(n) bits and constant time(optional). RMQ with BIT (optional) Nested segments (solution) and Pashmak and Parmida's problem (solution)
22/10/2018 Mo's algorithm on sequences and trees Rossano's notes*. Mo's Algorithm: Sequences and Trees Powerful array and Tree and queries
23/10/2018 Exercises Array copy and Triplets
05/11/2018 Graph algorithms: BFS, DFS, and Topological Sort Rossano's notes*. [CCLR] Chapter 22 X total shapes, IsBipartite, and Fox and names
06/11/2018 Graph algorithms: Strongly Connected Components and Single-Source Shortest Path Rossano's notes*. [CCLR] Chapters 22 and 23 Learning languages and Checkposts
12/11/2018 Heavy-light Decomposition and Centroid Decomposition of trees Heavy-light Decomposition of trees: here, here, and here. Centroid Decomposition of trees: here, here, here, and here Xenia and Tree (optional problem)
13/11/2018 Graph algorithms: Minimum Spanning Tree (and Disjoint Sets data structures) Rossano's notes*. [CCLR] Chapters 21 and 23. Kruskal: code, Disjoint Set: tutorial Minimum spanning tree
19/11/2018 Greedy algorithms: Activity Selection, Job sequencing, and Fractional knapsack problem Rossano's notes*. Notes by Jeff Erickson. Job sequencing. Fractional Knapsack Problem N meetings in one room, Magic numbers, Wilbur and array, and Alternative thinking
20/11/2018 Greedy Algorithms: Huffman code and problems. Rossano's notes*. Huffman code: Section 7.4 in Notes by Jeff Erickson. Lexicographically maximum subsequence, Woodcutters, and Queue
26/11/2018 Dynamic Programming: Fibonacci numbers, Rod cutting, Longest common subsequence, and 0/1 Knapsack Rossano's notes*. [CCLR] Chapter 15. 0/1 knapsack problem: tutorial Longest common subsequence, and 0-1 knapsack
27/11/2018 Dynamic Programming: Longest increasing subsequence Rossano's notes* Longest increasing subsequence, Minimum number of jumps, and Edit distance
03/12/2018 Dynamic Programming: Minimum cost path, Longest bitonic subsequence, and Subset sum Rossano's notes* Longest bitonic subsequence and Subset sum
04/12/2018 Dynamic Programming: Coin change, Largest independent set on trees, Longest palindromic subsequence, Edit Distance, and Weighted job scheduling Rossano's notes* Vertex cover and Longest palindromic subsequence
10/12/2018 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
11/12/2018 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.

Last year lectures

Date Lecture References Problems
06/12/2017 Simulation of the exam Misha and forest

* Notes marked with "Rossano's notes" are rough and non-exhaustive notes that I used while lecturing. Please use them just to have a list of the topics of each lecture and use other reported references to study these arguments.

Further (optional) topics