You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('') and can be up to 35 characters long.
92681d39e9  4 weeks ago  

2023_09_18  4 weeks ago  
2023_09_21  4 weeks ago  
2023_09_25  4 weeks ago  
2023_10_02  3 months ago  
2023_10_05/frogsandmosquitos  4 weeks ago  
2023_10_09  7 months ago  
2023_10_12  7 months ago  
2023_10_16/updatethearray  7 months ago  
2023_11_09  6 months ago  
2023_11_13/subsetsum  6 months ago  
2023_11_16/longestincreasingsubsequence  6 months ago  
2023_11_30  3 months ago  
.gitignore  6 months ago  
README.md  4 weeks ago 
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

 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.

 The strategy used to solve this problem is the twopointer 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 thannums[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 thatnums[1] = nums[n] = ∞
and thatnums[i] != nums[i+1]
for alli
.
 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
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 SingleSource Shortest Path
 Graph algorithms: Minimum Spanning Tree (and Disjoint Sets data structures)