DSA sheet
A curated sheet built on CSES
34 problems from the CSES Problem Set, each with a hint ladder, how to think about it, the intuition, and solutions in C++17, Python 3, Java 17 and Node.js that were compiled and checked against a brute force before publishing. Try the problem in the browser first, then peek.
Problem statements belong to CSES (Antti Laaksonen, University of Helsinki) and are licensed CC BY-NC-SA 4.0. This sheet links to the official task. Each "problem in brief" is an adapted, shortened summary of the CSES statement, shared under the same CC BY-NC-SA 4.0 licence; the hints, explanations and code are my own (© Anupam Kumar). Not affiliated with CSES.
Pick up where you left off: Continue
Available offline once visited
0 of 34 solved 0%
Progress is saved in this browser only.
No problems match these filters.
Introductory
0 / 10 solved- Weird Algorithm Follow an even/odd rule from a starting number down to 1 and print every value you visit.
- Missing Number One number from 1..n is absent from a list of n-1 distinct values; find it.
- Repetitions Find the length of the longest run of identical letters in a DNA-style string.
- Increasing Array Using only "add 1 to an element" moves, make an array non-decreasing with as few moves as possible.
- Permutations Arrange 1..n so that no two neighbours differ by exactly 1, or say it is impossible.
- Number Spiral An infinite grid is numbered along a spiral; answer "what number sits at row y, column x" for many queries.
- Two Knights For every board size k from 1 to n, count the ways to place two knights so neither attacks the other.
- Bit Strings Count the binary strings of length n and print the count modulo 1 000 000 007.
- Trailing Zeros Count the zeros at the end of n factorial for n up to a billion, without computing the factorial.
- Coin Piles Two piles of coins; each move takes 2 from one pile and 1 from the other. Can both be emptied?
Sorting and searching
0 / 9 solved- Distinct Numbers Count how many different values appear in a list of up to 200 000 integers.
- Apartments Match applicants to apartments by desired size within a tolerance k, maximizing the number of matches.
- Ferris Wheel Children with given weights ride gondolas that hold at most two and a total weight limit; use as few gondolas as possible.
- Concert Tickets Customers arrive in order, each buying the priciest ticket they can afford; report the price each pays or -1.
- Restaurant Customers Given each customer's arrival and leaving time, find the largest number of people in the restaurant at once.
- Movie Festival Pick the largest set of movies whose showing times do not overlap.
- Sum of Two Values Find two different positions in an array whose values add up to a target x, or report that none exist.
- Maximum Subarray Sum Find the largest possible sum of a non-empty contiguous block of an array that may contain negatives.
- Stick Lengths Change stick lengths at a cost equal to the size of the change, so that all sticks end up the same length as cheaply as possible.
Dynamic programming
0 / 8 solved- Dice Combinations Count the ordered sequences of ordinary dice throws whose total is exactly n, modulo 1 000 000 007.
- Minimizing Coins Make a target sum from unlimited copies of given coin values using as few coins as possible.
- Coin Combinations I Count the ordered sequences of coins (from unlimited supplies of given values) that add up to x, modulo 1 000 000 007.
- Coin Combinations II Count the distinct multisets of coins (order does not matter) that add up to x, modulo 1 000 000 007.
- Removing Digits Repeatedly subtract one of your current number's own digits until you reach zero, using as few steps as possible.
- Grid Paths I Count right/down paths from the top-left to the bottom-right of an n by n grid that has some blocked cells.
- Book Shop Choose books, each at most once, with a price and page count, to maximise total pages within a budget.
- Array Description Some entries of an array are unknown; count the ways to fill them with values 1..m so neighbours differ by at most 1.
Graph
0 / 5 solved- Counting Rooms Count the connected regions of floor cells in a map with walls, moving up, down, left and right.
- Labyrinth Find a shortest path from A to B through a grid with walls and print its length and the sequence of moves.
- Message Route Find the shortest chain of connected computers from computer 1 to computer n, or say there is none.
- Round Trip Find any cycle of at least three different cities in an undirected road network, or report that there is none.
- Shortest Routes I Compute the cheapest travel cost from city 1 to every other city over one-way flights with positive prices.