CSES Solutions

My accepted solutions of CSES problemset

• CSES Solutions
  • Introductory Problems
  • Sorting and Searching
  • Dynamic Programming
  • Graph Algorithms
  • Range Queries
  • Tree Algorithms
  • Mathematics
  • String Algorithms
  • Geometry
  • Advanced Techniques
  • Additional Problems

---

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	2072.cpp
Substring Reversals	2073.cpp
Reversals and Sums	2074.cpp
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
Counting Bits
Swap Game
Prüfer Code
Acyclic Graph Edges
Strongly Connected Edges
Even Outdegree Edges
Multiplication Table
Advertisement
Special Substrings
Permutation Inversions
Maximum Xor Subarray
Movie Festival Queries
Chess Tournament
Tree Traversals
Network Renovation
Graph Girth
Intersection Points
Inverse Inversions
Monotone Subsequences
String Reorder
Stack Weights
Pyramid Array
Increasing Subsequence II
String Removals
Bit Inversions
Xor Pyramid
Writing Numbers
String Transform
Letter Pair Move Game
Maximum Building I
Sorting Methods
Cyclic Array
List of Sums
Increasing Array II
Food Division
Bit Problem
Swap Round Sorting
Binary Subsequences
Tree Isomorphism I
Counting Sequences
Critical Cities
School Excursion
Coin Grid
Robot Path
Programmers and Artists
Course Schedule II
Removing Digits II
Coin Arrangement
Counting Bishops
Grid Puzzle I
Grid Puzzle II
Empty String
Grid Paths
Bit Substrings
Reversal Sorting
Counting Reorders
Book Shop II
Network Breakdown
Visiting Cities
Missing Coin Sum Queries
Number Grid
Maximum Building II
Filling Trominos
Stick Divisions
Coding Company
Flight Route Requests
Two Stacks Sorting
Tree Isomorphism II
Forbidden Cities
Area of Rectangles
Grid Completion
Creating Offices
Permutations II
Functional Graph Distribution
New Flight Routes
Grid Path Construction