competitive-programming/README.md

Solutions in Rust for some competitive programming problems

Created for the "Competitive Programming" course (academic year 23/24) at the Department of Computer Science of the University of Pisa.

Course Page: https://pages.di.unipi.it/rossano/competitive/

Time spent on the project

List of problems

• Kadane's Algorithm

  • Idea: We want to find the maximum subarray sum in an array of integers. It works by iterating through the array and keeping track of the maximum sum seen so far and the maximum sum ending at the current index. At each index, the algorithm compares the current element with the maximum sum ending at the previous index plus the current element. If the current element is greater, then the maximum sum ending at the current index is just the current element. Otherwise, the maximum sum ending at the current index is the sum of the maximum sum ending at the previous index and the current element. The algorithm also keeps track of the maximum sum seen so far, which is the maximum of all the maximum sums ending at each index. The final result is the maximum sum seen so far.

• Trapping Rain Water

  • The strategy used to solve this problem is the two-pointer approach. We use two pointers, one at the beginning and one at the end of the array. We also keep track of the maximum height of the left and right sides. We then move the pointers towards each other, updating the maximum height as we go. If the maximum height of the left side is less than the maximum height of the right side, we know that we can trap water on the left side. Similarly, if the maximum height of the right side is less than the maximum height of the left side, we know that we can trap water on the right side. We keep adding the trapped water to the result until the pointers meet.

• Search for a peak in an (unsorted) array

  • The idea is to use a modified version of the binary search and observe that in there always will be a peak element (the worst case is a monotonically increasing/decreasing sequence, and in that case the peak will be the last/first element). So we just check if nums[mid] is greater than nums[mid+1] or not. If it is, we can discard the right part of the array, otherwise we can discard the left part of the array. We will always move towards the direction of the peak. It's important to note that nums[-1] = nums[n] = -∞ and that nums[i] != nums[i+1] for all i.

• Maximum Path Sum

• Hands-On 1

• Frogs and Mosquitoes

• Check if All the Integers in a Range Are Covered

• Longest k-Good Segment

• Continuous Subarray Sum

• Update the array

• Nested segments

• Powerful array

• Longest Common Subsequence

• Minimum Number of Jumps

• Hands-On 2

• Subset Sum

• Longest increasing subsequence

• Longest bitonic Sequence

• N meetings in one room

• Wilbur and array

• Woodcutters

• IsBipartite

• Hands-On 3

Theory and algorithms

• Binary Search
• Trees: representation, traversals, and Binary Search Tree
• Sweep line algorithm
• Two Pointers Technique
• Prefix Sum
• Fenwick tree
• Range updates
• Segment Trees
• Lazy Propagation
• Mo's Algorithm
• DP
• Min cost path
• Greedy
• Fractional Knapsack
• Boxes and Heros
• Graph algorithms: BFS and DFS
• Graph algorithms: Strongly Connected Components and Single-Source Shortest Path
• Graph algorithms: Minimum Spanning Tree (and Disjoint Sets data structures)