Here is a list of some of the problems I have successfully solved on Kattis, as well as some keywords I associated to them. I usually attempt to solve the problem in Python 3 first (though not always), then Python 2 if that was too slow, then finally I write it in Java or C++. There certainly are problems where a particular algorithm (perhaps even the best one) is too slow (or use too much memory) in Python, whereas it is perfectly sufficient in C++. A reason why I may use C++ is if I expect to recurse a lot (e.g. in a dfs), which Python handles horribly compared to C++.
There are more tagged problems available at contest.ii.uib.no, most of which I have not solved yet.
| ID | Problem | Language | Keywords |
|---|---|---|---|
| transitcard | Transit Card | Java | dp |
| clockpictures | Grid | Python 2 | strings, polynomial hashing |
| stringmatching | Grid | Python 2 | strings, polynomial hashing |
| inversefactorial | Inverse Factorial | Python 3 | number theory |
| forestevolution | Forest Evolution | Python 3 | geometry, convex hull, point in polygon, polygon area, line segment intersection |
| maxflow | Maximum Flow | Python 2 | graph, max flow |
| waif | Waif Until Dark | Python 3 | max flow, three-way matching |
| marblestree | Marbles On A Tree | Python 3 | tree, greedy, dfs |
| knightsfen | Knights in Fen | Python 3 | bfs, state-space, brute force |
| grid | Grid | Python 3 | bfs, grid |
| magicallights | Association of Cats and Magical Lights | Java | segment tree, tree, dfs |
| amoebas | Sheba's Amoebas | Python 3 | bfs, grid |
| arachnophobia | Arachnophobia | Python 3 | graph, dijkstra, binary search |
| lostmap | Lost Map | Java | union find |
| lipschitzconstant | Lipschitz Constant | Python 3 | sorting, sweep |
| otherside | Other Side | Python 3 | ad hoc |
| eatingout | Eating Out | Python 3 | ad hoc |
| froshweek | Frosh Week | Python 2 | segment tree |
| ticketpricing | Plane Ticket Pricing | Python 3 | dp |
| pebblesolitaire | Pettle Solitaire | Python 3 | dp, memoization |
| backpackbuddies | Backpack Buddies | Python 3 | timetable dijkstra, graph |
| grid | Grid | Python 3 | bfs, grid |
| bumped | Bumped! | Python 3 | dijkstra, graph |
| kornislav | Kornislav | Python 3 | oneliner, greedy |
| onechicken | One Chicken Per Person! | Python 3 | ad hoc |
| justaminute | Just a Minute | Python 3 | ad hoc |
| chopwood | Chopping Wood | Java | ad hoc |
| ultraquicksort | Ultra-QuickSort | Java | merge sort |
| greedilyincreasing | Greedily Increasing Subsequence | Python 3 | ad hoc, greedy |
| pizza2 | Pizza Crust | Python 3 | ad hoc, geometry |
| fizzbuzz | FizzBuzz | Python 3 | ad hoc |
| unionfind | Union Find | Java | union find |
| virtualfriends | Virtual Friends | Java | union find |
| chewbacca | Chewbacca | Python 3 | tree, graph |
| familydag | Family DAG | Python 3 | bfs, graph exploration |
| zigzag | Zig Zag Name Tag | Python 3 | greedy, strings |
| flexible | Flexible Spaces | Python 3 | brute force |
| stararrangements | Star Arrangements | Python 3 | ad hoc, brute force |
| aboveaverage | Above Average | Python 3 | ad hoc |
| faktor | Faktor | Python 3 | ad hoc |
| comma | Comma Sprinkler | Python 3 | bfs |
| gearchanging | Gear Changin | Python 3 | sorting, ad hoc |
| nanagrams | Number Anagrams | Python 3 | meomization |
| witchwood | Witchwood | Python 3 | dp, probability |
| cookingwater | Cooking Water | Python 3 | ad hoc |
| nesteddolls | Nested Dolls | Python 3 | sorting, binary search |
| ballotboxes | Distributing Ballot Boxes | Python 3 | binary search, priority queue |
| ceremony | Opening Ceremony | Python 3 | oneliner, sorting |
| rationalsequence3 | A Rational Sequence (Take 3) | Python 3 | tree, number theory |
| rationalsequence2 | A Rational Sequence 2 | Python 3 | tree, number theory |
| rationalsequence | A Rational Sequence | Python 3 | tree, number theory |
| brexit | Brexit | Python 3 | simulation, graph, bfs |
| bard | Bard | Python 3 | simulation |
| flowergarden | Flower Garden | Python 3 | simulation, preprocessing, number theory, geometry |
| catalan | Catalan Numbers | Python 3 | number theory |
| cats | A Feast For Cats | Python 3 | graph, mst |
| howmanydigits | How Many Digits? | Python 3 | number theory, preprocessing |
| powerstrings | Power Strings | Python 2 | kmp, strings |
| perfectpowers | Perfect Pth Powers | Python 3 | number theory |
| bachetsgame | Bachet's Game | C++ | game strategy |
| nine | I Hate the Number Nine | Python 3 | oneliner, number theory |
| islandhopping | Island Hopping | Python 2 | graph, mst |
| estate | Integer Estate Agent | Python 2 | sliding window, amortized analysis, preprocessing |
| color | Color | Python 3 | sorting, greedy |
| meowfactor | Meow Factor | Python 3 | exhaustive search, pruning, ad hoc |
| runningmom | Running MoM | Python 3 | graph, dfs |
| secretchamber | Secret Chamber at Mount Rushmore | Python 3 | graph, bfs |
| concentration | Concentration | Python 3 | simulation, game strategy, walking dudes |
| racetrack | Race Track | Python 3 | simulation, queue |
| factorfree | Factor-Free Tree | Python 2 | number theory, divide and conquer, tree, sweep, prefix sum, amortized analysis |
| cd | CD | Python 2 | ad hoc |
| ascendingphoto | Ascending Photo | Python 3 | dp, greedy |
| knockout | Knockout Tournament | Python 2 | greedy, exhaustive search, segment tree |
| glyphrecognition | Glyph Recognition | Python 3 | geometry, binary search, point in polygon |
| installingapps | Installing Apps | Python 2 | dp, knapsacky |
| highscore2 | High Score | Python 3 | exhaustive search, pruning, ad hoc |
| dunglish | Dunglish | Python 3 | ad hoc |
| bossbattle | Boss Battle | Python 3 | oneliner, ad hoc |
| turbo | Turbo | Python 2 | segment tree |
| guess | Guess the Number | Python 3 | binary search, interactive |
| amazing | A Mazing! | Python 3 | dfs, interactive |
| megainversions | Mega Inversions | Python 2 | segment tree |
| moviecollection | Movie Collection | Python 2 | segment tree |
| toys | Toys | Python 3 | dp |
| sumsets | Sumsets | C++ | exhaustive search, binary search |
| hissingmicrophone | Hissing Microphone | Python 3 | oneliner, ad hoc |
| fulltank | Full Tank? | Python 3 | dijkstra, graph |
| squarefieldshard | Square Fields (Hard) | Python 3 | binary search, geometry, dp, bitmask |
| kitten | Kitten on a Tree | Python 3 | tree, ad hoc |
| pivot | Pivot | Python 3 | sweep, prefix sum -ish |
| trains | Trains | Python 3 | dijkstra, graph |
| digitsum | Digit Sum | Python 3 | dp, number theory |
| bottledup | Bottled-Up Feelings | Python 3 | greedy |
| oddities | Oddities | Python 3 | oneliner, ad hoc |
| risk | Risk | C++ | max flow, binary search, grid |
| subway3 | Subway | Python 3 | bfs, graph, sweep, amortized analysis |
| trainsorting | Train Sorting | Python 3 | dp, longest increasing subsequence |
| muzicari | Muzicari | Python 2 | dp, knapsacky |
| uxuhulvoting | The Uxuhul Voting System | Python 3 | dp, bitmask |
| solitaire | Peg Solitaire | Python 3 | memoization |
| timing | Timing | C++ | simulation, graph |
| boggle | Boggle | C++ | trie, bfs, grid, strings |
| funhouse | Fun House | Python 3 | simulation, grid |
| maximizingwinnings | Maximizing (and Minimizing) Your Winnings | C++ | dp, grid |
| mountainvillage | Mountain Village | Python 2 | sliding window, bfs, grid |
| roundedbuttons | Rounded Buttons | Python 3 | geometry |
| bucketbrigade | Bucket Brigade | Python 3 | ad hoc |
| kayaking | Kayaking Trip | Python 3 | binary search, greedy |
| bestrelayteam | Best Relay Team | Python 3 | sorting |
| distinctivecharacter | Distinctive Character | Python 2 | bfs, state-space |
| emptyingbaltic | Emptying the Baltic | Python 2 | dijkstra, grid |
| gcpc | Galactic Collegiate Programming Contest | Python 3 | greedy, amortized analysis |
| judgingmoose | Judging Moose | Python 3 | ad hoc |
| importspaghetti | Import Spaghetti | Python 2 | bfs, graph |
| pongtournament | Pong Tournament | Python 2 | graph, sorting, dp, longest increasing subsequence |
| birdrescue | Bird Rescue | Python 2 | manhattan, prefix sum |
| toast | Toast | Python 2 | binary search, geometry |
| politicaldevelopment | Political Development | Python 2 | graph, sorting, exhaustive search |
| toll | Toll | Python 2 | segment tree, dp, dag |
| railway2 | Railway | Python 2 | dfs, tree, amortized analysis |
| catinatree | Cat in a Tree | Python 2 | tree, dp |
| friends2 | Friends | Python 2 | graph, exhaustive search |
| plusminus | Plus Minus | Python 2 | combinatorics |
| deathknight | Death Knight Hero | Python 3 | oneliner, ad hoc |
| bread | Bread Sorting | Python 3 | counting tree |
| exactchange2 | Exact Change | Python 2 | dp, knapsacky |
| wolf | Wolf | Python 3 | exhaustive search, greedy |
| compromise | Best Compromise | Python 3 | hamming distance, greedy |
| primaryarithmetic | Primary Arithmetic | Python 3 | simulation |
| billiard | Billiard | Python 3 | geometry, ad hoc |
| bookingaroom | Booking a Room | Python 3 | greedy |
| beehives | Beehives | Python 3 | geometry, exhaustive search |
| vote | Popular Vote | Python 3 | ad hoc |
| charlesincharge | Charles in Charge | Python 2 | binary search, dijkstra, graph |
| debugging | Debugging | Python 2 | memoization, amortized analysis |
| fire3 | Fire! | Python 2 | bfs, grid |
| communication | Jumbled Communication | Python 3 | ad hoc |
| carrots | Solving for Carrots | Python 3 | oneliner, ad hoc |
| almostunionfind | Almost Union-Find | C++ | union-find |
| bridgeautomation | Bridge Automation | Python 2 | dp |
| completingthesquare | Completing the Square | Python 3 | geometry, vectors |
| sodasurpler | Soda Surpler | Python 3 | simulation |
| r2 | R2 | Python 3 | oneliner, ad hoc |
| modulo | Modulo | Java | ad hoc |
| restaurantbribes | Restaurant Bribes | Python 3 | graph, greedy |
| speedyescape | Speedy Escape | Python 3 | dijkstra, binary search, graph |
| 10kindsofpeople | 10 Kinds of People | Python 2 | union-find, grid |
| twostones | Take Two Stones | Python 3 | oneliner, ad hoc, game strategy |
| catvsdog | Cat vs. Dog | Python 2 | bipartite matching |
| anti11 | Ocean's Anti-11 | Python 3 | dp |
| wheresmyinternet | Where's My Internet?? | Python 3 | bfs, graph |
| arcticnetwork | Arctic Network | Python 3 | graph, mst |
| airconditioned | Air Conditioned Minons | Python 3 | sorting, greedy |
| dicecup | Dice Cup | Python 3 | probability, exhaustive search |
| cups | Stacking Cups | Python 3 | sorting, ad hoc |
| walkforest | A Walk Through the Forest | C++ | dijkstra, dfs, graph, dag |
| tritiling | Tri Tiling | Python 3 | dp |
| rubiksrevenge | Rubik's Revenge in ... 2D!? 3D? | Python 3 | bfs, state-space, bidirectional |
| worstweather | Worst Weather Ever | Python 2 | segment tree |
| fence2 | Building Fences | Python 3 | binary search, floating point precision |
| beehives2 | Beehives | Python 2 | bfs, graph |
| paintball | Paintball | Python 2 | bipartite matching |
| mailbox | The Mailbox Manufacturers Problem | Python 2 | dp |
| rockpaperscissors | Rock-Paper-Scissors Tournament | C++ | greedy |
| builddeps | Build Dependencies | Python 3 | dfs, graph |
| amanda | Amanda Lounges | Python 3 | bfs, graph |
| ironcoal | Iron and Coal | Python 3 | bfs, graph |
| cold | Cold-puter Science | Python 2 | oneliner, ad hoc |
| trollhunt | Troll Hunt | Python 3 | ad hoc |
| primes2 | Blackboard Numbers | Python 3 | number theory |
| timeloop | Stuck in a Time Loop | Python 3 | ad hoc |
| pointinpolygon | Point in Polygon | Python 3 | geometry, point in polygon |
| spiderman | Spiderman's Workout | Python 3 | dp, knapsacky |
| elementarymath | Elementary Math | Python 2 | bipartite matching |
| convexhull | Convex Hull | Python 3 | geometry, convex hull |
| closestpair1 | Closest Pair (Uniform) | C++ | geometry, closest pair |
| closestpair2 | Closest Pair | C++ | geometry, closest pair |
| segmentdistance | Line Segment Distance | Python 3 | geometry, line segment distance |
| segmentintersection | Line Segment Intersection | Python 3 | geometry |
| supercomputer | Supercomputer | Python 3 | segment tree |
| backspace | Backspace | Python 3 | stack |
| androids | Androids | C++ | graph, mst |
| subseqhard | Counting Subsequences (Hard) | Python 3 | prefix sum |
| autocorrect | Bless You Autocorrect! | Python 2 | trie, bfs, strings |
| fenceortho | Fence Orthogonality | Python 2 | geometry, convex hull |
| rafting | White Water Rafting | Python 3 | geometry, line segment distance |
| polygonarea | Polygon Area | Python 3 | geometry, polygon area |
| jabuke | Jabuke | Python 3 | geometry, point in polygon |
| vacuumba | Vacuumba | Python 3 | geometry, simulation |
| tracksmoothing | Track Smoothing | Python 3 | geometry, ad hoc |
| findinglines | Finding Lines | Python 3 | randomization, geometry |
| wrapping | Board Wrapping | Python 3 | geometry, convex hull, polygon area |
| simpleaddition | Simple Addition | Python 3 | ad hoc |
| armystrengthhard | Army Strength (Hard) | Python 3 | ad hoc |
| ants | Ants | Python 3 | ad hoc |
| orders | Restaurant Orders | Python 3 | dp, knapsacky |
| pebblesolitaire2 | Pebble Solitaire | Python 3 | memoization |
| coast | Coast Length | Python 3 | bfs, grid |
| shortestpath1 | Single source shortest path, non-negative weights | C++ | dijkstra, graph |
| gamerank | Game Rank | Python 3 | simulation |
| stockbroker | Daydreaming Stockbroker | Python 3 | simulation |
| compass | Jumbled Compass | Python 3 | oneliner, ad hoc |
| getshorty | Get Shorty | Python 3 | dijkstra, graph |
| robotopia | Robotopia | Python 3 | exhaustive search |
| cargame | Car Game | C++ | strings, preprocessing |
| birthday | Birthday Party | Python 3 | dfs, graph |
| a1paper | A1 Paper | Python 3 | greedy |
| easiest | The Easiest Problem Is This One | Python 3 | ad hoc |
| numbertree | Numbers on a Tree | Python 3 | tree |
| busnumbers | Bus Numbers | Python 3 | greedy |
| plantingtrees | Planting Trees | Java | sorting |
| vegetables | Boiling Vegetables | Java | priority queue, greedy |
| erase | Erase Securely | Java | ad hoc |
dp/memoization: Dynamic Programming (dp) and memoization are flip sides of the same technique, but in some cases memoization makes much more sense than dynamic programming. This is especially true if memoization will reduce the number of calculated entries drastically, or if one needs to do a reachability search across the state space. For such problems I use the keyword memoization, otherwise I stick with dp.
graph/grid/tree/dag: General graphs are tagget as graph, but often graphs have special structures, such as being a tree, a (subgraph of a) grid or a directed acyclig graph (dag). In these cases, the keyword graph is omitted, and keywords tree, grid or dag are used instead. If both a general graph and a restricted graph show up in the same problem, I attempt to use all relevant keywords.
bfs/dfs: In cases of exploration, one can use either breath first search (bfs) or depth first search (dfs). I personally prefer using bfs whenever I have the choice because it is easier to code without recursion. Hence, some problems categorized as bfs use it for exploration, other problems use it for finding shortest paths. The dfs keyword is reserved for cases when dfs is the only appropriate option; usually this means that the pre- and post-values of the dfs tree are used in a clever way, we are interested in strongly connected components, or something needs to be done in post-value order.
max flow/bipartite matching: Bipartite matching problems can famously be solved using a max flow algorithm, but it is overkill. Hence, I separate between the two categories.
union-find/mst: Minimum spanning trees (mst) can be found with Kruskal's algorithm using the union-find datastructure. However, there are also other problems where the union-find data structure may be beneficial, and for mst you also have the choice of Prim's algorithm.
segment tree/fenwick tree/binary index tree/interval tree: There are subtle differences between these notions, but I label all of them as segment tree, even in the cases when a Fenwick tree or BIT tree would suffice. This is because I find segment trees to be equally easy to code as the other trees, and a constant factor bigger space requirement doesn't bother me when segment trees are so much more flexible as to what I can do with them.
I am particularly fond of these problems: