Topcoder Problems for Review and Practice
James S. Plank, University of Tennessee
The purpose of this web site is to have a bunch of Topcoder problems for CS140 and CS302
students to go through on their own for practice. In these files, I will give various hints
and perhaps solutions to the problems.
Please email me if you see typos and/or problems with any of these writeups.
D2 250-point Practice Problems
When students ask me what they can do to prepare for CS302 (and even CS140), my response is
always, "Topcoder." The 250-point problems from Division 2 are great in this regard,
because they typically require small (10-line) solutions, and are straightfoward. Your
goal with these problems should be to get them within 20 minutes or so. When you get
better at coding quickly, make that goal 5 minutes!
With these web pages, what you should do is the following:
- Go to topcoder and attempt the problem without reading my help. If you
get it, great! Go on to the next.
- If you are having trouble, especially if you having trouble getting started or
crafting a solution, then click on the web link and read the help/hints. Then go
back and try it again.
- If this is a problem that I don't assign for labs, I'll try to include a
commented solution. That way, you can compare your code to the code of a seasoned
veteran, and that may help you learn!
I'm going to order these problems from easiest to hardest, using the success rates from
Topcoder as the metric.
- 93.7% - SRM 608, D2, 250-Pointer (OneDimensionalRobotEasy). Simulate a robot with a for loop and three if statements.
- 93.2% - SRM 714, D2, 250-Pointer (RangeEncoding). One for loop (no solution).
- 92.3% - SRM 719, D2, 250-Pointer (LongLiveZhangzj). Inserting strings into a set, and then finding them (no solution).
- 92.2% - SRM 616, D2, 250-Pointer (WakingUpEasy). Successively run through a vector, subtracting from a value, until it is ≤ 0.
- 91.9% - SRM 480, D2, 250-Pointer (Cryptography). Sort and use long long's. (I don't provide a solution).
- 91.7% - SRM 702, D2, 250-Pointer (TestTaking). Some subtraction and some tertiary expressions.
- 87.1% - SRM 698, D2, 250-Pointer (Initials).
A three-line practice problem with strings.
- 86.6% - SRM 708, D2, 250-Pointer (SafeBetting).
Simple simulation. (No solution).
- 86.2% - SRM 695, D2, 250-Pointer (BearNSWE).
Maintaining the Bear's (x,y) coordinate, and then using the distance formula.
- 85.8% - SRM 697, D2, 250-Pointer (TriangleMaking). Reasoning about a triangle, and using sorting to make your life easier.
- 85.6% - SRM 704, D2, 250-Pointer (SwapAndArithmetic). Sort and traverse.
- 85.5% - SRM 673, D2, 250-Pointer (BearSong). Create a map and traverse it.
- 83.2% - SRM 666, D2, 222-Pointer (DevuAndGame).
Simulate a really easy game. (I don't provide a solution).
- 80.0% - SRM 705, D2, 250-Pointer (SuperUserDo).
Simulate and count.
- 77.9% - SRM 707, D2, 250-Pointer (Cross). Processing a vector of strings (No solution).
- 77.7% - SRM 706, D2, 250-Pointer (ThreeIncreasing). Thinking about a problem in the correct order. (I don't provide a solution).
- 73.9% - SRM 700, D2, 250-Pointer (Xylophone). Mod. (I don't provide a solution).
- 72.0% - SRM 686, D2, 250-Pointer (TreeAndVertex). Count edges coming out of nodes of a tree.
- 71.0% - SRM 688, D2, 250-Pointer (ParenthesesDiv2Easy). Run through a string and maintain a counter.
- 70.9% - TCO 2017, Q1A, 250-Pointer (PingPongQueue). Simulate a simple system.
- 69.8% - SRM 691, D2, 300-Pointer (Plusonegame).
Counting digits and building a return string.
- 69.8% - SRM 499, D2, 250-Pointer (SimpleGuess). Using a set and a simple enumeration of (X,Y) pairs.
- 68.7% - SRM 701, D2, 250-Pointer (SquareFreeString). Simple enumeration and substrings. (I don't provide a solution.)
- 68.4% - SRM 718, D2, 250-Pointer (RelativeHeights). Maps, sets and some string processing. (No solution, but a lot of help).
- 66.1% - SRM 699, D2, 250-Pointer (UpDownHiking). Keep track of two values per day for N days.
- 65.8% - SRM 689, D2, 250-Pointer (SimilarUserDetection). Strings and sets (No solution).
- 62.4% - SRM 696, D2, 250-Pointer (Ropestring).
Counting rope lengths, and then using them to create a return string.
- 60.2% - TCO 2017, Q1B, 250-Pointer (WaterAndOxygen). Algebra.
- 59.3% - SRM 643, D2, 250-Pointer (TheKingsArmyDiv2).
Using the find() method for strings, and running though the characters in a vector of strings.
(I don't provide a solution)
- 57.0% - SRM 597, D2, 250-Pointer (LittleElephantAndDouble). Sort a vector and traverse it.
- 52.3% - SRM 679, D2, 250-Pointer (ListeningSongs).
Break the problem into parts, and use sort() to help you.
- 52.0% - SRM 663, D2, 250-Pointer (ChessFloor). Enumerate two letters and run through a two-dimensional vector.
- 48.4% - SRM 717, D2, 250-Pointer (NiceTable). You'll be tempted to try to be smart, but instead, look at the constraints and do two power set enumerations.
- 47.4% - SRM 693, D2, 250-Pointer (TriangleEasy). This is a simple O(n3) enumeration, but you have to use the right O(n3) enumeration.
- 46.3% - SRM 623, D2, 250-Pointer (CatchTheBeatEasy). Create a multimap and traverse it.
- 44.6% - SRM 183, D2, 350-Pointer (CountGame). You'll
want to think of game strategy, but if you simply use dynamic programming, you'll get the answer quickly!
- 43.9% - SRM 606, D2, 250-Pointer (EllysSubstringSorter). Gives you practice with the substr() method, and sort(). (No Solution)
- 39.8% - SRM 709, D2, 250-Pointer (RoboFactory). Thinking precisely.
D1 250-point Problems (or D2 500-point Problems)
These are harder than the problems above, and often fit into some class of algorithm
from CS140 or CS302. The percentages for the D2, 500-pointers are much lower than
the D1, 250 pointers for two reasons: First, the programmers in D1 are better. Second,
by the time the programmers get to the 500-point problem, they may not have time to
complete it. Keep that in mind.
- 88.2% - SRM 719, D1, 250-Pointer (LongMansionDiv1). Run through a vector and calculate a minimum. (No solution)
- 74.2% - SRM 619, D1, 250-Pointer (SplitStoneGame). A straightforward dynamic program. (I don't provide a solution)
- 73.3% - SRM 590, D1, 250-Pointer (FoxAndChess). Vectors and Strings. (I don't provide a solution)
- 70.2% - SRM 468, D1, 250-Pointer (T9). Create a map, whose vals are vectors of strings. Parse a string and create a return value. (No solution)
- 65.9% - SRM 612, D1, 250-Pointer (EmoticonsDiv1). I solve this as a classic Breadth-First Search, where you create the graph as you process the BFS queue.
- 63.1% - TCO 2017, Q1A, 500-Pointer (CheeseSlicing). Dynamic programming.
- 62.9% - SRM 702, D1, 300-Pointer (GridSortMax). A greedy algorithm on vectors.
- 59.5% - SRM 596, D2, 500-Pointer (ColorfulRoad). Good practice for Dijkstra's Algorithm, Dynamic Programming or Toplogical Sort. (No solution)
- 57.0% - TCO 2016 Round 1A, 500-Pointer (EllysSocks). Straightforward Dynamic Program (I don't provide a solution).
- 53.5% - SRM 183, D2, 550-Pointer (BridgeSort). Simple sorting (no solution).
- 53.5% - SRM 686, D1, 250-Pointer (BracketSequenceDiv1). Dynamic programming, plain and simple.
- 51.9% - TCO 2015 Round 1A, 250-pointer (Similars).
Gives you good practice using bits as sets.
- 49.7% - SRM 706, 21, 500-Pointer (SellingFruits).
Avoiding pitfalls. (No solution).
- 49.6% - SRM 700, D1, 300-Pointer (FindingFriend). Running through a vector and maintaining the correct information to solve the problem.
- 48.5% - SRM 614, D1, 250-Pointer (MinimumSquare). I go over this problem in my CS494 class. These are the lecture notes. It's one of those problems that I beat to death. Sorry.
- 47.0% - SRM 708, D2, 500-Pointer (BuildingStrings). Iteratively solving a problem with strings.
- 43.0% - SRM 604, D2, 500-Pointer (PowerOfThreeEasy). I solve this using a power set enumeration, and teach this in CS302.
- 41.6% - SRM 699, D1, 250-Pointer (OthersXor).
Nice problem to practice bits and thinking about XOR's.
- 39.9% - SRM 714, D2, 500-Pointer (RemovingParenthesis).
A straightforward dynamic programming counting problem.
- 39.3% - SRM 701, D1, 250-Pointer (PartisanGame).
Dynamic Programming. (No solution, but I walk you through the answer).
- 37.2% - SRM 641, D1, 250-Pointer (TrianglesContainOrigin).
Geometry and Maps. I walk through the solution in my CS494 class and include the presentation here.
- 32.8% - SRM 699, D2, 500-Pointer (LastDigit). Dynamic programming with big integers.
- 32.5% - SRM 695, D1, 300-Pointer (BearPasswordLexic). Turn a vector into a map, and a map into a string.
- 30.0% - SRM 705, D2, 500-Pointer (AlphabetOrderDiv2). DFS on a directed graph.
- 28.9% - SRM 347, D1, 250-Pointer (Aircraft). Either use calculus, or a really neat binary search.
- 25.0% - SRM 686, D2, 500-Pointer (SegmentsAndPoints). This is not a hard problem. I suspect the low scores were due to time constraints from the 250-point problem.
- 22.0% - SRM 691, D1, 300-Pointer (Sunnygraphs). The coding here is not bad -- a simple DFS that does not even have to be recursive. The hard part is turning that into a solution. This is a nice problem to make you think precisely about graphs. (I don't provide a solution)
- 19.9% - SRM 700, D2, 500-Pointer (XMarksTheSpot). Power set enumeration.
- 16.9% - SRM 707, D2, 500-Pointer (StepsConstruct). Breadth First Search.
D1 500-point Problems (or D2 1000-point Problems)
For these, I rank them by (number correct / number opened), but I also
report (number correct / number submitted). It's hard to gauge these, again, because it's
hard to know how much time a competitor had when he/she opened the problem.
- 47.4% / 93.2%- SRM 699, D1, 500-Pointer (FromToDivisible). This is a BFS problem where you have to convert their graph to a tractable one using GCD(). (No solution)
- 11.3% / 62.9% - SRM 713, D1, 500-Pointer (DFSCount). DFS, Dynamic programming and bit arithmetic. (No solution)
- 6.8% / 44.7% - SRM 348, D2, 1000-Pointer (IncreasingSubsequences). I use this as an example when I teach
Topological Sort in CS302.
- 5.9% / 61.1% - SRM 702, D2, 1000-Pointer (SubsetSumExtreme). Dynamic programming with bit arithmetic. How can it get any better than that?
- 3.3 / 33.9% - TCO 2017, Q1A, 1000-Pointer (PolygonRotation). This is a problem that makes you reason about geometry. My solution relied on line intersection, plus maps. There's nothing here that a CS302 student cannot solve -- you just have to work through it step by step. (No solution)