CSES Solutions

My own solutions to the CSES Problem Set

My account on CSES: https://cses.fi/user/15196

Feel free to ask (by creating issues) if you don't understand my solutions.

Introductory Problems

Name	Solution
Weird Algorithm	1068.cpp
Missing Number	1083.cpp
Repetitions	1069.cpp
Increasing Array	1094.cpp
Permutations	1070.cpp
Number Spiral	1071.cpp
Two Knights	1072.cpp
Two Sets	1092.cpp
Bit Strings	1617.cpp
Trailing Zeros	1618.cpp
Coin Piles	1754.cpp
Palindrome Reorder	1755.cpp
Gray Code	2205.cpp
Tower of Hanoi	2165.cpp
Creating Strings	1622.cpp
Apple Division	1623.cpp
Chessboard and Queens	1624.cpp
Digit Queries	2431.cpp
Grid Paths	1625.cpp

Sorting and Searching

Name	Solution
Distinct Numbers	1621.cpp
Apartments	1084.cpp
Ferris Wheel	1090.cpp
Concert Tickets	1091.cpp
Restaurant Customers	1619.cpp
Movie Festival	1629.cpp
Sum of Two Values	1640.cpp
Maximum Subarray Sum	1643.cpp
Stick Lengths	1074.cpp
Missing Coin Sum	2183.cpp
Collecting Numbers	2216.cpp
Collecting Numbers II	2217.cpp
Playlist	1141.cpp
Towers	1073.cpp
Traffic Lights	1163.cpp
Josephus Problem I	2162.cpp
Josephus Problem II	2163.cpp
Nested Ranges Check	2168.cpp
Nested Ranges Count	2169.cpp
Room Allocation	1164.cpp
Factory Machines	1620.cpp
Tasks and Deadlines	1630.cpp
Reading Books	1631.cpp
Sum of Three Values	1641.cpp
Sum of Four Values	1642.cpp
Nearest Smaller Values	1645.cpp
Subarray Sums I	1660.cpp
Subarray Sums II	1661.cpp
Subarray Divisibility	1662.cpp
Subarray Distinct Values	2428.cpp
Array Division	1085.cpp
Sliding Median	1076.cpp
Sliding Cost	1077.cpp
Movie Festival II	1632.cpp
Maximum Subarray Sum II	1644.cpp

Dynamic Programming

Name	Solution
Dice Combinations	1633.cpp
Minimizing Coins	1634.cpp
Coin Combinations I	1635.cpp
Coin Combinations II	1636.cpp
Removing Digits	1637.cpp
Grid Paths	1638.cpp
Book Shop	1158.cpp
Array Description	1746.cpp
Counting Towers	2413.cpp
Edit Distance	1639.cpp
Rectangle Cutting	1744.cpp
Money Sums	1745.cpp
Removal Game	1097.cpp
Two Sets II	1093.cpp
Increasing Subsequence	1145.cpp
Projects	1140.cpp
Elevator Rides	1653.cpp
Counting Tilings	2181.cpp
Counting Numbers	2220.cpp

Graph Algorithms

Name	Solution
Counting Rooms	1192.cpp
Labyrinth	1193.cpp
Building Roads	1666.cpp
Message Route	1667.cpp
Building Teams	1668.cpp
Round Trip	1669.cpp
Monsters	1194.cpp
Shortest Routes I	1671.cpp
Shortest Routes II	1672.cpp
High Score	1673.cpp
Flight Discount	1195.cpp
Cycle Finding	1197.cpp
Flight Routes	1196.cpp
Round Trip II	1678.cpp
Course Schedule	1679.cpp
Longest Flight Route	1680.cpp
Game Routes	1681.cpp
Investigation	1202.cpp
Planets Queries I	1750.cpp
Planets Queries II	1160.cpp
Planets Cycles	1751.cpp
Road Reparation	1675.cpp
Road Construction	1676.cpp
Flight Routes Check	1682.cpp
Planets and Kingdoms	1683.cpp
Giant Pizza	1684.cpp
Coin Collector	1686.cpp
Mail Delivery	1691.cpp
De Bruijn Sequence	1692.cpp
Teleporters Path	1693.cpp
Hamiltonian Flights	1690.cpp
Knight's Tour	1689.cpp
Download Speed	1694.cpp
Police Chase	1695.cpp
School Dance	1696.cpp
Distinct Routes	1711.cpp

Range Queries

Name	Solution
Static Range Sum Queries	1646.cpp
Static Range Minimum Queries	1647.cpp
Dynamic Range Sum Queries	1648.cpp
Dynamic Range Minimum Queries	1649.cpp
Range Xor Queries	1650.cpp
Range Update Queries	1651.cpp
Forest Queries	1652.cpp
Hotel Queries	1143.cpp
List Removals	1749.cpp
Salary Queries	1144.cpp
Prefix Sum Queries	2166.cpp
Pizzeria Queries	2206.cpp
Subarray Sum Queries	1190.cpp
Distinct Values Queries	1734.cpp
Increasing Array Queries	2416.cpp
Forest Queries II	1739.cpp
Range Updates and Sums	1735.cpp
Polynomial Queries	1736.cpp
Range Queries and Copies	1737.cpp

Tree Algorithms

Name	Solution
Subordinates	1674.cpp
Tree Matching	1130.cpp
Tree Diameter	1131.cpp
Tree Distances I	1132.cpp
Tree Distances II	1133.cpp
Company Queries I	1687.cpp
Company Queries II	1688.cpp
Distance Queries	1135.cpp
Counting Paths	1136.cpp
Subtree Queries	1137.cpp
Path Queries	1138.cpp
Path Queries II	2134.cpp
Distinct Colors	1139.cpp
Finding a Centroid	2079.cpp
Fixed-Length Paths I	2080.cpp
Fixed-Length Paths II	2081.cpp

Mathematics

Name	Solution
Josephus Queries	2164.cpp
Exponentiation	1095.cpp
Exponentiation II	1712.cpp
Counting Divisors	1713.cpp
Common Divisors	1081.cpp
Sum of Divisors	1082.cpp
Divisor Analysis	2182.cpp
Prime Multiples	2185.cpp
Counting Coprime Pairs	2417.cpp
Binomial Coefficients	1079.cpp
Creating Strings II	1715.cpp
Distributing Apples	1716.cpp
Christmas Party	1717.cpp
Bracket Sequences I	2064.cpp
Bracket Sequences II	2187.cpp
Counting Necklaces	2209.cpp
Counting Grids	2210.cpp
Fibonacci Numbers	1722.cpp
Throwing Dice	1096.cpp
Graph Paths I	1723.cpp
Graph Paths II	1724.cpp
Dice Probability	1725.cpp
Moving Robots	1726.cpp
Candy Lottery	1727.cpp
Inversion Probability	1728.cpp
Stick Game	1729.cpp
Nim Game I	1730.cpp
Nim Game II	1098.cpp
Stair Game	1099.cpp
Grundy's Game	2207.cpp
Another Game	2208.cpp

String Algorithms

Name	Solution
Word Combinations	1731.cpp
String Matching	1753.cpp
Finding Borders	1732.cpp
Finding Periods	1733.cpp
Minimal Rotation	1110.cpp
Longest Palindrome	1111.cpp
Required Substring	1112.cpp
Palindrome Queries	2420.cpp
Finding Patterns	2102.cpp
Counting Patterns	2103.cpp
Pattern Positions	2104.cpp
Distinct Substrings	2105.cpp
Repeating Substring	2106.cpp
String Functions	2107.cpp
Substring Order I	2108.cpp
Substring Order II	2109.cpp
Substring Distribution	2110.cpp

Geometry

Name	Solution
Point Location Test	2189.cpp
Line Segment Intersection	2190.cpp
Polygon Area	2191.cpp
Point in Polygon	2192.cpp
Polygon Lattice Points	2193.cpp
Minimum Euclidean Distance	2194.cpp
Convex Hull	2195.cpp

Advanced Techniques

Name	Solution
Meet in the Middle	1628.cpp
Hamming Distance	2136.cpp
Beautiful Subgrids	2137.cpp
Reachable Nodes	2138.cpp
Reachability Queries	2143.cpp
Cut and Paste
Substring Reversals
Reversals and Sums
Necessary Roads	2076.cpp
Necessary Cities	2077.cpp
Eulerian Subgraphs	2078.cpp
Monster Game I	2084.cpp
Monster Game II	2085.cpp
Subarray Squares	2086.cpp
Houses and Schools	2087.cpp
Knuth Division	2088.cpp
Apples and Bananas	2111.cpp
One Bit Positions	2112.cpp
Signal Processing	2113.cpp
New Roads Queries	2101.cpp
Dynamic Connectivity	2133.cpp
Parcel Delivery	2121.cpp
Task Assignment	2129.cpp
Distinct Routes II	2130.cpp

Additional Problems

Name	Solution
Shortest Subsequence	1087.cpp
Counting Bits	1146.cpp
Swap Game	1670.cpp
Prüfer Code	1134.cpp
Acyclic Graph Edges	1756.cpp
Strongly Connected Edges	2177.cpp
Even Outdegree Edges	2179.cpp
Multiplication Table	2422.cpp
Advertisement	1142.cpp
Special Substrings	2186.cpp
Permutation Inversions	2229.cpp
Maximum Xor Subarray	1655.cpp
Movie Festival Queries	1664.cpp
Chess Tournament	1697.cpp
Tree Traversals	1702.cpp
Network Renovation
Graph Girth
Intersection Points	1740.cpp
Inverse Inversions	2214.cpp
Monotone Subsequences
String Reorder	1743.cpp
Stack Weights	2425.cpp
Pyramid Array	1747.cpp
Increasing Subsequence II	1748.cpp
String Removals	1149.cpp
Bit Inversions	1188.cpp
Xor Pyramid	2419.cpp
Writing Numbers	1086.cpp
String Transform	1113.cpp
Letter Pair Move Game
Maximum Building I	1147.cpp
Sorting Methods	1162.cpp
Cyclic Array	1191.cpp
List of Sums	2414.cpp
Increasing Array II
Food Division
Bit Problem	1654.cpp
Swap Round Sorting	1698.cpp
Binary Subsequences
Tree Isomorphism I	1700.cpp
Counting Sequences	2228.cpp
Critical Cities
School Excursion	1706.cpp
Coin Grid	1709.cpp
Robot Path
Programmers and Artists
Course Schedule II	1757.cpp
Removing Digits II
Coin Arrangement
Counting Bishops	2176.cpp
Grid Puzzle I	2432.cpp
Grid Puzzle II	2131.cpp
Empty String	1080.cpp
Grid Paths	1078.cpp
Bit Substrings
Reversal Sorting
Counting Reorders
Book Shop II	1159.cpp
Network Breakdown	1677.cpp
Visiting Cities
Missing Coin Sum Queries
Number Grid
Maximum Building II	1148.cpp
Filling Trominos
Stick Divisions	1161.cpp
Coding Company	1665.cpp
Flight Route Requests
Two Stacks Sorting
Tree Isomorphism II	1701.cpp
Forbidden Cities
Area of Rectangles	1741.cpp
Grid Completion
Creating Offices
Permutations II
Functional Graph Distribution
New Flight Routes
Grid Path Construction