Accepted solutions to the CSES Problem Set, written in C++ by hikjik.
python3 gen_task.py "Weird Algorithm" --tests 2
# Open in Visual Studio Code
code solutions/weird-algorithm/main.cpp./scripts/grader.sh solutions/weird-algorithm/main.cppIntroductory Problems
| № | Name | Solution | Tags |
|---|---|---|---|
| 1. | Weird Algorithm | C++ | |
| 2. | Missing Number | C++ | |
| 3. | Repetitions | C++ | |
| 4. | Increasing Array | C++ | |
| 5. | Permutations | C++ | |
| 6. | Number Spiral | C++ | |
| 7. | Two Knights | C++ | |
| 8. | Two Sets | C++ | |
| 9. | Bit Strings | C++ | |
| 10. | Trailing Zeros | C++ | |
| 11. | Coin Piles | C++ | |
| 12. | Palindrome Reorder | C++ | |
| 13. | Gray Code | C++ | |
| 14. | Tower of Hanoi | C++ | |
| 15. | Creating Strings | C++ | |
| 16. | Apple Division | C++ | |
| 17. | Chessboard and Queens | C++ | |
| 18. | Digit Queries | C++ | |
| 19. | Grid Paths | C++ |
Sorting and Searching
| № | Name | Solution | Tags |
|---|---|---|---|
| 20. | Distinct Numbers | C++ | |
| 21. | Apartments | C++ | |
| 22. | Ferris Wheel | C++ | |
| 23. | Concert Tickets | C++ | |
| 24. | Restaurant Customers | C++ | |
| 25. | Movie Festival | C++ | |
| 26. | Sum of Two Values | C++ | |
| 27. | Maximum Subarray Sum | C++ | |
| 28. | Stick Lengths | C++ | |
| 29. | Missing Coin Sum | C++ | |
| 30. | Collecting Numbers | C++ | |
| 31. | Collecting Numbers II | C++ | |
| 32. | Playlist | C++ | |
| 33. | Towers | C++ | |
| 34. | Traffic Lights | C++ | |
| 35. | Josephus Problem I | C++ | |
| 36. | Josephus Problem II | C++ | |
| 37. | Nested Ranges Check | C++ | |
| 38. | Nested Ranges Count | C++ | |
| 39. | Room Allocation | C++ | |
| 40. | Factory Machines | C++ | |
| 41. | Tasks and Deadlines | C++ | |
| 42. | Reading Books | C++ | |
| 43. | Sum of Three Values | C++ | |
| 44. | Sum of Four Values | C++ | |
| 45. | Nearest Smaller Values | C++ | |
| 46. | Subarray Sums I | C++ | |
| 47. | Subarray Sums II | C++ | |
| 48. | Subarray Divisibility | C++ | |
| 49. | Subarray Distinct Values | C++ | |
| 50. | Array Division | C++ | |
| 51. | Sliding Median | C++ | |
| 52. | Sliding Cost | C++ | |
| 53. | Movie Festival II | C++ | |
| 54. | Maximum Subarray Sum II | C++ |
Dynamic Programming
| № | Name | Solution | Tags |
|---|---|---|---|
| 55. | Dice Combinations | C++ | |
| 56. | Minimizing Coins | C++ | |
| 57. | Coin Combinations I | C++ | |
| 58. | Coin Combinations II | C++ | |
| 59. | Removing Digits | C++ | |
| 60. | Grid Paths | C++ | |
| 61. | Book Shop | C++ | |
| 62. | Array Description | C++ | |
| 63. | Counting Towers | C++ | |
| 64. | Edit Distance | C++ | |
| 65. | Rectangle Cutting | C++ | |
| 66. | Money Sums | C++ | |
| 67. | Removal Game | C++ | |
| 68. | Two Sets II | C++ | |
| 69. | Increasing Subsequence | C++ | |
| 70. | Projects | C++ | |
| 71. | Elevator Rides | C++ | |
| 72. | Counting Tilings | C++ | |
| 73. | Counting Numbers | C++ |
Graph Algorithms
| № | Name | Solution | Tags |
|---|---|---|---|
| 74. | Counting Rooms | C++ | DFS on a Grid Flood Fill Count Connected Components |
| 75. | Labyrinth | C++ | BFS on a Grid Shortest Path (by number of edges) |
| 76. | Building Roads | C++ | DFS for Undirected Graph Min Number of Edges to Connect Graph |
| 77. | Message Route | C++ | BFS for Undirected Graph Shortest Path (by number of edges) |
| 78. | Building Teams | C++ | BFS for Undirected Graph Bipartite graph |
| 79. | Round Trip | C++ | DFS for Undirected Graph Cycle Retrieval |
| 80. | Monsters | C++ | Multi Source BFS on a Grid |
| 81. | Shortest Routes I | C++ | Shortest Paths in a Directed Graph Dijkstra’s Algorithm |
| 82. | Shortest Routes II | C++ | All-Pairs Shortest Paths in an Undirected Graph Floyd Warshall Algorithm |
| 83. | High Score | C++ | Shortest Paths in a Directed Graph Negative weight edges Bellman Ford Algorithm |
| 84. | Flight Discount | C++ | Shortest Paths in a Directed Graph Modified Dijkstra’s Algorithm |
| 85. | Cycle Finding | C++ | Retrieve Negative Cycle in a Directed Graph Bellman-Ford Algorithm |
| 86. | Flight Routes | C++ | K-Shortest Paths in a Directed Graph Modified Dijkstra’s Algorithm |
| 87. | Round Trip II | C++ | DFS for Directed Graph Cycle Retrieval |
| 88. | Course Schedule | C++ | Topological Sort Kahn's Algorithm |
| 89. | Longest Flight Route | C++ | Topological Sort Kahn's Algorithm Dynamic Programming |
| 90. | Game Routes | C++ | Topological Sort Kahn's Algorithm Dynamic programming |
| 91. | Investigation | C++ | Shortest Paths in a Directed Graph Modified Dijkstra’s Algorithm |
| 92. | Planets Queries I | C++ | Functional Graph |
| 93. | Planets Queries II | C++ | Functional Graph DFS for Directed Graph |
| 94. | Planets Cycles | C++ | Functional Graph DFS for Directed Graph |
| 95. | Road Reparation | C++ | Disjoint Sets Union |
| 96. | Road Construction | C++ | Disjoint Sets Union |
| 97. | Flight Routes Check | C++ | DFS for Directed Graph Check if a Graph is Strongly Connected |
| 98. | Planets and Kingdoms | C++ | Strongly Connected Component Kosaraju's algorithm |
| 99. | Giant Pizza | C++ | 2SAT Strongly Connected Component Kosaraju's algorithm Topological Sort |
| 100. | Coin Collector | C++ | Strongly Connected Component Kosaraju's algorithm Condensation graph |
| 101. | Mail Delivery | C++ | Eulerian Circuit |
| 102. | De Bruijn Sequence | C++ | Eulerian Circuit Bit Manipulation |
| 103. | Teleporters Path | C++ | Eulerian Path |
| 104. | Hamiltonian Flights | C++ | Hamiltonian Path Bitmasking and Dynamic Programming |
| 105. | Knight's Tour | C++ | Hamiltonian Path Backtracking with Warnsdorff's heuristic |
| 106. | Download Speed | C++ | Max Flow Dinic's Algorithm |
| 107. | Police Chase | C++ | Max Flow Minimum Cut Edmonds Karp Algorithm |
| 108. | School Dance | C++ | Max Flow Bipartite Matching Edmonds Karp Algorithm |
| 109. | Distinct Routes | C++ | Max Flow Edge Disjoint Paths Edmonds Karp Algorithm |
Range Queries
| № | Name | Solution | Tags |
|---|---|---|---|
| 110. | Static Range Sum Queries | C++ | Prefix Sum |
| 111. | Static Range Minimum Queries | C++ | Sparse Table |
| 112. | Dynamic Range Sum Queries | C++ | Fenwick Tree |
| 113. | Dynamic Range Minimum Queries | C++ | Segment Tree |
| 114. | Range Xor Queries | C++ | Prefix Sum |
| 115. | Range Update Queries | C++ | Segment Tree |
| 116. | Forest Queries | C++ | Prefix Sum 2D |
| 117. | Hotel Queries | C++ | Segment Tree |
| 118. | List Removals | C++ | Ordered Set |
| 119. | Salary Queries | C++ | Ordered Set |
| 120. | Prefix Sum Queries | ||
| 121. | Pizzeria Queries | ||
| 122. | Subarray Sum Queries | ||
| 123. | Distinct Values Queries | ||
| 124. | Increasing Array Queries | ||
| 125. | Forest Queries II | ||
| 126. | Range Updates and Sums | ||
| 127. | Polynomial Queries | ||
| 128. | Range Queries and Copies |
Tree Algorithms
| № | Name | Solution | Tags |
|---|---|---|---|
| 129. | Subordinates | C++ | DFS Dynamic Programming |
| 130. | Tree Matching | C++ | DFS Greedy |
| 131. | Tree Diameter | ||
| 132. | Tree Distances I | ||
| 133. | Tree Distances II | ||
| 134. | Company Queries I | ||
| 135. | Company Queries II | ||
| 136. | Distance Queries | ||
| 137. | Counting Paths | ||
| 138. | Subtree Queries | ||
| 139. | Path Queries | ||
| 140. | Path Queries II | ||
| 141. | Distinct Colors | ||
| 142. | Finding a Centroid | ||
| 143. | Fixed-Length Paths I | ||
| 144. | Fixed-Length Paths II |
Mathematics
| № | Name | Solution | Tags |
|---|---|---|---|
| 145. | Josephus Queries | ||
| 146. | Exponentiation | C++ | |
| 147. | Exponentiation II | C++ | |
| 148. | Counting Divisors | C++ | |
| 149. | Common Divisors | C++ | |
| 150. | Sum of Divisors | ||
| 151. | Divisor Analysis | ||
| 152. | Prime Multiples | ||
| 153. | Counting Coprime Pairs | ||
| 154. | Binomial Coefficients | ||
| 155. | Creating Strings II | ||
| 156. | Distributing Apples | ||
| 157. | Christmas Party | ||
| 158. | Bracket Sequences I | ||
| 159. | Bracket Sequences II | ||
| 160. | Counting Necklaces | ||
| 161. | Counting Grids | ||
| 162. | Fibonacci Numbers | ||
| 163. | Throwing Dice | ||
| 164. | Graph Paths I | ||
| 165. | Graph Paths II | ||
| 166. | Dice Probability | ||
| 167. | Moving Robots | ||
| 168. | Candy Lottery | ||
| 169. | Inversion Probability | ||
| 170. | Stick Game | ||
| 171. | Nim Game I | ||
| 172. | Nim Game II | ||
| 173. | Stair Game | ||
| 174. | Grundy's Game | ||
| 175. | Another Game |
String Algorithms
| № | Name | Solution | Tags |
|---|---|---|---|
| 176. | Word Combinations | C++ | Trie DP |
| 177. | String Matching | C++ | KMP |
| 178. | Finding Borders | C++ | Z-Function |
| 179. | Finding Periods | C++ | Z-Function |
| 180. | Minimal Rotation | ||
| 181. | Longest Palindrome | C++ | Manacher's Algorithm |
| 182. | Required Substring | ||
| 183. | Palindrome Queries | ||
| 184. | Finding Patterns | ||
| 185. | Counting Patterns | ||
| 186. | Pattern Positions | ||
| 187. | Distinct Substrings | ||
| 188. | Repeating Substring | ||
| 189. | String Functions | C++ | P-function Z-Function |
| 190. | Substring Order I | ||
| 191. | Substring Order II | ||
| 192. | Substring Distribution |
Geometry
| № | Name | Solution | Tags |
|---|---|---|---|
| 193. | Point Location Test | C++ | |
| 194. | Line Segment Intersection | C++ | |
| 195. | Polygon Area | C++ | |
| 196. | Point in Polygon | C++ | |
| 197. | Polygon Lattice Points | C++ | |
| 198. | Minimum Euclidean Distance | ||
| 199. | Convex Hull |
Advanced Techniques
| № | Name | Solution | Tags |
|---|---|---|---|
| 200. | Meet in the Middle | ||
| 201. | Hamming Distance | ||
| 202. | Beautiful Subgrids | ||
| 203. | Reachable Nodes | ||
| 204. | Reachability Queries | ||
| 205. | Cut and Paste | ||
| 206. | Substring Reversals | ||
| 207. | Reversals and Sums | ||
| 208. | Necessary Roads | ||
| 209. | Necessary Cities | ||
| 210. | Eulerian Subgraphs | ||
| 211. | Monster Game I | ||
| 212. | Monster Game II | ||
| 213. | Subarray Squares | ||
| 214. | Houses and Schools | ||
| 215. | Knuth Division | ||
| 216. | Apples and Bananas | ||
| 217. | One Bit Positions | ||
| 218. | Signal Processing | ||
| 219. | New Roads Queries | ||
| 220. | Dynamic Connectivity | ||
| 221. | Parcel Delivery | ||
| 222. | Task Assignment | ||
| 223. | Distinct Routes II |