DWITE programming contest solutions
DWITE is a online programming contest primarily for Canadian students. On this page I provide an unofficial archive of contest problems and my own solutions in Java. The official web site is http://dwite.ca/.
Repository
My repository at GitHub has this content:
- My DWITE solution code (Java)
- Problem statements (for the rounds I solved)
- Test data (for the rounds I solved)
- JUnit test suites (to validate my solutions)
You can browse the repository or download the entire package. If you see any improvements that can be made, feel free to fork the project and publish your changes!
Problems and solutions
Quick jump by school year:
- 2004–2005: October, November, December, January, February
- 2005–2006: October, November, December, January, February
- 2006–2007: October, November, December, January
- 2009–2010: October, November, December, January, March, April, June
- 2010–2011: October, November, December, January, February
- 2011–2012: October, November, December, January, February
Important: Every solution program depends on four shared classes: DwiteAlgorithm.java, DwiteIo.java, DwiteRunner.java, DwiteSolution.java. You must compile these classes, in addition to the specific solution class.
| Contest round | Problem | Solution | Comments |
|---|---|---|---|
| October 2004 | Area of Circle | dwite200410p1.java | Trivial. |
| 24 Hour Clock | dwite200410p2.java | Trivial. | |
| The Tallest in the Class | dwite200410p3.java | Straightforward: Convert to common unit, and sort. | |
| CD-ROM Files | dwite200410p4.java | Easy: Knapsack problem, dynamic programming. | |
| Super Long Sums | dwite200410p5.java | Easy, and trivial if using bignums. | |
| November 2004 | Credit Card Check Digit | dwite200411p1.java | Easy. |
| Squareland | dwite200411p2.java | Trivial. | |
| Factoring | dwite200411p3.java | Hard, messy: Rational zeros of polynomials. | |
| For Loops | dwite200411p4.java | Hard, messy: Multi-scan evaluation or Dijkstra’s shunting yard algorithm. | |
| Wind Chill | dwite200411p5.java | Easy. | |
| December 2004 | Prime Factorization | dwite200412p1.java | Medium: Recursion, primality testing. |
| Squareland II | dwite200412p2.java | Straightforward. Can be sped up from O(n4) to O(n2) by dynamic programming, though. | |
| Reflections | dwite200412p3.java | Easy: Trigonometry. | |
| Waring’s Prime Number Conjecture | dwite200412p4.java | Messy: Brute force search with help from the sieve of Eratosthenes. | |
| Hidden Geography | dwite200412p5.java | Easy: String processing and searching. | |
| January 2005 | DWITE Golf Tournament | dwite200501p1.java | Straightforward: Sorting. |
| Minesweeper | dwite200501p2.java | Straightforward. | |
| Harshad Numbers | dwite200501p3.java | Straightforward, using brute force search. | |
| Zeller’s Congruence | dwite200501p4.java | Easy: Follow the given algorithm. | |
| Different Bases Multiplication | dwite200501p5.java | Easy. | |
| February 2005 | Bretschneider’s Formula | dwite200502p1.java | Easy. |
| Snakes | dwite200502p2.java | Medium: Flood fill and neighbor count. | |
| Simple Continued Fractions | dwite200502p3.java | Easy. | |
| Matrix Chain Product | dwite200502p4.java | Hard: Matrix chain multiplication, dynamic programming. | |
| Tsunami Speed | dwite200502p5.java | Easy. | |
| October 2005 | Odometers | dwite200510p1.java | Straightforward for the O(10n) solution, where n is the number of digits. Mine runs in O(n2) time, which is a more complicated algorithm. |
| The Game of Life | dwite200510p2.java | Straightforward. | |
| Sum ’Em Up | dwite200510p3.java | Easy, and the sum can be written in closed form. | |
| Minesweeper | dwite200510p4.java | Medium: Flood fill (recursion). | |
| Five Digit Divisibility | dwite200510p5.java | Brute force search through all permutations. | |
| November 2005 | Quadrilateral Centroid | dwite200511p1.java | Easy, arithmetic mean. |
| Variations on the Game of Life | dwite200511p2.java | Straightforward. | |
| Cinquain Poetry | dwite200511p3.java | Easy. | |
| Stacking Blocks | dwite200511p4.java | Easy: Subset sum problem, dynamic programming. | |
| Base64 Encoding | dwite200511p5.java | Straightforward. | |
| December 2005 | Semiprimes | dwite200512p1.java | Straightforward. |
| The Maze | dwite200512p2.java | Medium: Breadth-first search. Reused from DWITE 2003-10 P5. | |
| Reducing Fractions | dwite200512p3.java | Medium: GCD algorithm. | |
| Now I Know My ABC’s | dwite200512p4.java | Easy: Histogram. | |
| How Many Sums | dwite200512p5.java | Medium: Subset sum problem, dynamic programming. | |
| January 2006 | Filling The Cone | dwite200601p1.java | Easy: Algebra. |
| Scrabble | dwite200601p2.java | Messy and long. | |
| London Knights | dwite200601p3.java | Straightforward: Sorting. It screams for the use of SQL, though. | |
| Equivalent Amounts | dwite200601p4.java | Easy: Convert to common unit, then convert from common unit. | |
| Distance Between Towns | dwite200601p5.java | Medium: Dijkstra’s algorithm. | |
| February 2006 | Points on a Line | dwite200602p1.java | Easy. Mine doesn’t use the division or floating-point. |
| Floppy Disk 3½-inch High Density | dwite200602p2.java | Easy: Knapsack problem, dynamic programming. | |
| UPC Check Digit | dwite200602p3.java | Easy. | |
| Connect-4 | dwite200602p4.java | Straightforward. | |
| Prime Palindromes | dwite200602p5.java | Medium: Brute force search, sieve of Eratosthenes. | |
| October 2006 | Pete’s Printing Press | dwite200610p1.java | Straightforward, but the data table to be manually input is large. |
| Body Mass Index | dwite200610p2.java | Easy. | |
| Basketball Statistics II | dwite200610p3.java | Straightforward: Sorting. | |
| Count Squares | dwite200610p4.java | Straightforward. Can be sped up from O(n5/2) to O(n3/2) using dynamic programming, where n is the number of cells. | |
| Bad Input II | dwite200610p5.java | Easy if you have access to regexes and bignums. | |
| November 2006 | 13375P34|< | dwite200611p1.java | Easy. |
| Lottery Ticket Checker | dwite200611p2.java | Straightforward. | |
| Linear Binomial Products | dwite200611p3.java | Straightforward. | |
| Money Prize | dwite200611p4.java | Medium: Dynamic programming. | |
| Goldbach’s Weak Conjecture | dwite200611p5.java | Medium: Recursion, sieve of Eratosthenes. | |
| December 2006 | Jimmy’s Lost His Marbles | dwite200612p1.java | Easy: Knapsack problem, dynamic programming. |
| Ulam Spiral Walkway | dwite200612p2.java | Straightforward. | |
| Circular Primes | dwite200612p3.java | Straightforward. | |
| The Ubiquitous 196 | dwite200612p4.java | Straightforward. | |
| Caesar’s Cipher | dwite200612p5.java | Easy. | |
| January 2007 | Filling The Cone | dwite200701p1.java | Easy: Algebra. Reused from DWITE 2006-01 P1. |
| Minesweeper | dwite200701p2.java | Straightforward. Reused from DWITE 2005-01 P2. | |
| Elapsed Time in Seconds | dwite200701p3.java | Date calculation. It helps to use a date library. | |
| Number Theory | dwite200701p4.java | Easy if you know about the partition function, otherwise use recursion and a loop. | |
| Dutch Solitaire | dwite200701p5.java | Straightforward. Know how to use data structure libraries! | |
| 2007–2008 | Not available | ||
| 2008–2009 | Not available | ||
| October 2009 | iProfits | dwite200910p1.java | Easy, but you have to do the math exactly. |
| Word Scrambler | dwite200910p2.java | Medium: Permutations. | |
| That Missing Number | dwite200910p3.java | Easy: Think about it mathematically. | |
| My First True Letter | dwite200910p4.java | Easy. | |
| Running In Circles | dwite200910p5.java | Medium: Recursion, graph traversal. | |
| November 2009 | Angles | dwite200911p1.java | Easy, as long as you learn about atan2(). |
| Mini DWITE | dwite200911p2.java | Easy. | |
| Binary Test String | dwite200911p3.java | Straightforward. | |
| Breadth First Not Quite Tree | dwite200911p4.java | Medium: Single-source shortest paths in an unweighted graph. | |
| Portals Redux | dwite200911p5.java | Medium: Flood fill, with portals added. | |
| December 2009 | Quiz Time | dwite200912p1.java | Easy. |
| Rounding to Fibonacci | dwite200912p2.java | Easy. | |
| Binary Test Strings 2 | dwite200912p3.java | Straightforward. | |
| Spiral Out | dwite200912p4.java | Straightforward because n ≤ 20, but messy in the general case. | |
| Up To Four Colours | dwite200912p5.java | Medium: Recursion, graph coloring, chromatic number. | |
| January 2010 | Social Media Overload | dwite201001p1.java | Trivial. |
| Verifying Distributed Work | dwite201001p2.java | Easy: Histogram. | |
| Moving at the same time | dwite201001p3.java | Straightforward. | |
| Autocomplete | dwite201001p4.java | Straightforward. | |
| Ice Maze | dwite201001p5.java | Medium: Minimum distance with a curious set of edges. Similar to DWITE 2010-10 P5. | |
| March 2010 | ASCII bar graphs | dwite201003p1.java | Easy. |
| Round to Second Prime | dwite201003p2.java | Straightforward. | |
| Summary Diff | dwite201003p3.java | Straightforward. | |
| Kind of like OCR | dwite201003p4.java | Easy: Recursion. | |
| Weak Passwords | dwite201003p5.java | Straightforward: Brute force. | |
| April 2010 | ROT13 Encryption | dwite201004p1.java | Easy. |
| Round to power of two | dwite201004p2.java | Straightforward: Takes a bit of thinking. | |
| Bill Amendments | dwite201004p3.java | Straightforward: Takes a bit of code. | |
| Time for Change | dwite201004p4.java | Easy: Knapsack problem, dynamic programming. | |
| Air Travel Planning | dwite201004p5.java | Straightfoward: Shortest path algorithm; I used Bellman-Ford. | |
| June 2010 | Binary Equipment | dwite201006p1.java | Trivial if you know your bitwise operators. |
| Sum of Primes | dwite201006p2.java | Easy if you have the sieve of Eratosthenes. | |
| Oil Spill Area | dwite201006p3.java | Medium: Recursion for flood fill. | |
| What is this Algebra? | dwite201006p4.java | Medium, messy: Parsing, order of operations. I used a dumb brute-force approach to keep the code simple. Related to DWITE 2004-11 P4. | |
| Snapper Chain | dwite201006p5.java | Easy: Think about it mathematically; don’t use brute force. | |
| October 2010 | Age Gate | dwite201010p1.java | Easy. |
| Robot Vacuum Prototype | dwite201010p2.java | Easy. | |
| Power tiles | dwite201010p3.java | Medium: Recursion, but it’s not easy to see the problem in this light. | |
| Planting Trees | dwite201010p4.java | Medium: Computational geometry. | |
| Ricochet Robot | dwite201010p5.java | Medium: Minimum distance with a curious set of edges. Similar to DWITE 2010-01 P5. | |
| November 2010 | Pattern Matching | dwite201011p1.java | Easy. |
| Seating Arrangement | dwite201011p2.java | Medium: A lot of code for a seemingly simple problem. | |
| Escape and Loot | dwite201011p3.java | Medium: Dynamic programming. | |
| Fractions to Decimal | dwite201011p4.java | Medium: Finite state machine (FSM) loop detection. | |
| Cogwheels | dwite201011p5.java | Medium: Alternating flood fill. | |
| December 2010 | Integers along a line | dwite201012p1.java | Easy if you see the connection with GCD. |
| Unit rectangles | dwite201012p2.java | Straightforward. | |
| Dominos Tiling | dwite201012p3.java | Hard: Dynamic programming with some subtlety. | |
| Forest Fires | dwite201012p4.java | Medium: Distance on a grid. | |
| E-Searching | dwite201012p5.java | Easy if using regex library, hard if writing a good pattern matcher. Mine is an NFA that runs in linear time. | |
| January 2011 | Future Printer | dwite201101p1.java | Easy, but reason about odd and even numbers carefully. |
| Primal Numbers | dwite201101p2.java | Easy if you have the sieve of Eratosthenes. | |
| Binary Weight | dwite201101p3.java | Easy if you can think of the right approach. | |
| Mountain Hiking | dwite201101p4.java | Medium: Path distance on a grid. | |
| Sleepwalking Probabilities | dwite201101p5.java | Easy: Dynamic programming. | |
| February 2011 | Colourful Words | dwite201102p1.java | Easy. |
| Safe from Rooks | dwite201102p2.java | Easy: Think about it mathematically; don’t use brute force. | |
| Balancing Act | dwite201102p3.java | Easy: Knapsack problem. | |
| New type of wordplay | dwite201102p4.java | Hard: Somewhat subtle dynamic programming. | |
| Cube World | dwite201102p5.java | Medium: Flood fill used in a specific way. | |
| October 2011 | Arab-lish Numbers | dwite201110p1.java | Straightforward. Regular expressions are helpful. |
| Penny Game | dwite201110p2.java | Easy. | |
| Take a Walk | dwite201110p3.java | Medium: Vector geometry, projections. | |
| C001 Numbers | dwite201110p4.java | Easy for the slow algorithm. I have a fast algorithm that is rather tricky. | |
| Tattarrattat | dwite201110p5.java | Medium: Dynamic programming. Somewhat similar to the longest common subsequence (LCS) problem. | |
| November 2011 | Wandering Billy | dwite201111p1.java | Easy. |
| Scratch Card | dwite201111p2.java | Easy: Subsequence matching. | |
| Anonymous Shopping | dwite201111p3.java | Straightforward. | |
| Bear Trees | dwite201111p4.java | Medium: A generalization of BFS and DFS into a kind of “best-first search”. | |
| Portals Check | dwite201111p5.java | Medium: Union-find. | |
| December 2011 | Weighted Presents | dwite201112p1.java | Easy. |
| Magical Ponds | dwite201112p2.java | Medium: Number theory, GCD. | |
| Combo Discounts | dwite201112p3.java | Medium: Recursion/backtracking. Vaguely similar to the knapsack problem. | |
| ABCA Maze | dwite201112p4.java | Straightforward: Breadth-first search. | |
| Tautology | dwite201112p5.java | Medium: Formula parsing, brute force truth assignment. | |
| January 2012 | Crossword Count | dwite201201p1.java | Straightforward: Scan the grid. |
| Prime Time | dwite201201p2.java | Easy if you have the sieve of Eratosthenes. | |
| Breaking Bonds | dwite201201p3.java | Medium: Graph connectedness and brute force search. | |
| Lego Ladder | dwite201201p4.java | Medium: Use dynamic programming on all possible game states. | |
| Comet Vomit | dwite201201p5.java | Medium: Use clever math to reduce it to linear time. | |
| February 2012 | Age Gate | dwite201202p1.java | Reused from DWITE 2010-10 P1. |
| Unit rectangles | dwite201202p2.java | Reused from DWITE 2010-12 P2. | |
| Binary Weight | dwite201202p3.java | Reused from DWITE 2011-01 P3. | |
| Forest Fires | dwite201202p4.java | Reused from DWITE 2010-12 P4. | |
| Cube World | dwite201202p5.java | Reused from DWITE 2011-02 P5. | |
Notes
DWITE has two incarnations. The first was by Will Sentjens (I think) from June 2002 to February 2006. The second is by Hacker Dan and CompSci.ca starting from October 2007. See the current DWITE about page for more details. At the moment, my solutions cover about half of the first DWITE incarnation and a tiny bit of the second DWITE incarnation.
The DWITE problems (PDF and HTML files) are not made by Nayuki.
Trivia: DWITE stands for Do While If Then Else.
