CSES Discussion

General

• Beware of integer overflows

Searching and Sorting

• Binary Search
  • binary_search(vector.begin(), vector.end(), val)
  • set.find(val) , multiset.find(val)
  • set.upper_bound(val): iterator > val
  • set.lower_bound(val): iterator >= val
  • upper_bound(vector.begin(), vector.end(), val)
  • unordered_set
  • Policy Based Data Structure
  • Search on the answer
  • multiset.erase(multiset.find(val)): erase just one instance of val from multiset

• Ternary Search

• Sort
  • sort(vector.begin(), vector.end())
  • sort(vector.rbegin(), vector.rend())

Dynamic Programming

Very Detailed Editorial: Part1, Part2

• CSES - Removal Game: Constand factors become important.
  • Also, the lambda recursive functions are slower than regular recursive function, Might be due to the lack of compiler optimisation for lambdas.
• CSES - Projects: Nice Question
• CSES - Elevator Rides : Bitmask DP.
  • It called as Bin packing problem, a standard variation on Knapsack problem.
  • Solution to this is on CPH P103.
• CSES - Counting Tilings: Broken Profile DP
  • This is similar to FloorBoards problem discussed in Bitmask Dynamic Programming.
  • Useful to read the editorial and related links in the editorial above.
  • You can do other problems from USACO Guide Article

Graph

• CSES - High Score: Good practice
• CSES - Flight Discount: Modified Dijkstra
• CSES - Flight Routes: Modified Dijkstra