Solved on Kattis

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 (to see if I can assign the problem to Python users), then Python 2 if that was too slow, then finally I write it in C++ if all else fails. There may be many exceptions, but there's a chance Python might be too slow (or use too much memory) if it is listed with C++ on this list. Another 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
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

About the keywords

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.

 

Favourite problems

I am particularly fond of these problems:


I am the author of these problems.