# DWITE programming contest solutions

DWITE is an online programming contest primarily for Canadian high school students. Their official website is http://dwite.org/. On this page I provide an unofficial archive of contest problems, in addition to my own solution programs in Java.

## Repository

The project repository contains:

- My runnable solution programs (Java code)
- Problem statements (for the contest rounds I solved)
- Test data files (for the rounds I solved)
- JUnit test suites (to check solutions automatically)

You can browse the repository at GitHub or download a ZIP package .

## Problems and solutions

Quick jump by school year:

- 2002–2004: Not available
- 2004–2005: October, November, December, January, February
- 2005–2006: October, November, December, January, February
- 2006–2007: October, November, December, January
- 2007–2008: October, November, December, January, February
- 2008–2009: October, November, December, January, February
- 2009–2010: October, November, December, January, March, April, June
- 2010–2011: October, November, December, January, February, July (cs4hs)
- 2011–2012: October, November, December, January, February
- 2012–2013: October, November, February

**Important**: Every solution program depends on three shared classes: DwiteAlgorithm.java, DwiteIo.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 | Easy: Recursion, primality testing. |

Squareland II | dwite200412p2.java | Straightforward. Can be sped up from O(n^{4}) to O(n^{2}) by dynamic programming, though. | |

Reflections | dwite200412p3.java | Trivial: 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 | Easy, brute force computation. | |

Zeller’s Congruence | dwite200501p4.java | Easy: Follow the given algorithm. | |

Different Bases Multiplication | dwite200501p5.java | Trivial using library functions, otherwise medium. | |

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 | Trivial. | |

October 2005 | Odometers | dwite200510p1.java | Straightforward for the O(10^{n} n) solution, where n is the number of digits. Mine runs in O(n^{2}) 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 | Medium: 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. Similar to DWITE 2004-10 P4. | |

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(n^{5/2}) to O(n^{3/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. Essentially the same as DWITE 2004-10 P4. |

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! | |

October 2007 | Vanilla Primes | dwite200710p1.java | Easy. |

Cubes in a Pyramid | dwite200710p2.java | Trivial. | |

Where’s my QWERTY? | dwite200710p3.java | Straightforward. | |

Stacks of Blocks | dwite200710p4.java | Easy: Knapsack problem, dynamic programming. | |

Velociraptor Maze | dwite200710p5.java | Medium: Breadth-first search, movement simulation. | |

November 2007 | Not Quite Prime | dwite200711p1.java | Easy. |

Show Me The Money! | dwite200711p2.java | Easy. | |

Floor Plan | dwite200711p3.java | Medium: Flood fill / breadth-first search. | |

All Is Balanced | dwite200711p4.java | Easy: Use a stack. | |

Bridges In A Graph | dwite200711p5.java | Medium: Union-find. | |

December 2007 | Yet Another Primes Question | dwite200712p1.java | Easy. |

There’s An Essay In My Code | dwite200712p2.java | Medium: String processing with a regular expression or a state machine. | |

Playlist | dwite200712p3.java | Easy: Knapsack problem. | |

The Convex Fence Company | dwite200712p4.java | Hard: Convex hull, gift-wrapping algorithm. | |

Portals | dwite200712p5.java | Medium: Breadth-first search. | |

January 2008 | Curve-shot | dwite200801p1.java | Trivial, though needs a bit of math. |

And the winner is... | dwite200801p2.java | Easy. | |

Don’t follow my links | dwite200801p3.java | Straightforward: Ad hoc string manipulation. | |

Shortest path around | dwite200801p4.java | Medium: Breadth-first search. | |

It all adds up | dwite200801p5.java | Medium: Parsing, dynamic programming / memoization. | |

February 2008 | I heart you | dwite200802p1.java | Trivial. |

Number of factors | dwite200802p2.java | Easy. | |

Parity bit | dwite200802p3.java | Trivial if you use a Hamming weight function, easy otherwise. | |

Train ride | dwite200802p4.java | Medium: Breadth-first search. | |

Tetris! | dwite200802p5.java | Medium: Ad hoc grid manipulation. | |

October 2008 | LaNDscAPE ii | dwite200810p1.java | Easy. |

Simple Checksum | dwite200810p2.java | Easy. | |

School’s a maze | dwite200810p3.java | Medium: Breadth-first search. | |

What is this Roman Numeral? | dwite200810p4.java | Straightforward. | |

Moving Stuff in Boxes | dwite200810p5.java | Hard: A souped-up version of the NP-complete bin-packing problem; exponential time. | |

November 2008 | My shiny digital key | dwite200811p1.java | Trivial. |

My favourite digit | dwite200811p2.java | Trivial. | |

My drink is made of cubes | dwite200811p3.java | Easy: Integer factoring. | |

Big shiny tunes | dwite200811p4.java | Easy: Knapsack problem, essentially the same as DWITE 2007-12 P3. | |

Water damage | dwite200811p5.java | Straightforward: Grid traversal. | |

December 2008 | ASCII Rhombus | dwite200812p1.java | Easy. |

Wordcount++ | dwite200812p2.java | Easy. | |

Unicorns and Teaspoons | dwite200812p3.java | Easy, essentially the same as DWITE 2006-01 P4. | |

Time for change | dwite200812p4.java | Easy: Knapsack problem. Similar to DWITE 2007-10 P4. | |

Now in 3D | dwite200812p5.java | Medium: Breadth-first search, a slightly more complex version of DWITE 2008-01 P4. | |

January 2009 | Four-player Pong with no players | dwite200901p1.java | Easy. |

Tic-Tac-Win | dwite200901p2.java | Straightforward. | |

Secret party | dwite200901p3.java | Medium: Graph traversal. | |

Shortest path around v2 | dwite200901p4.java | Medium: Breadth-first search, essentially the same as DWITE 2008-01 P4. | |

Blow your mind with 4th D | dwite200901p5.java | Medium: Breadth-first search. | |

February 2009 | Baby Diff | dwite200902p1.java | Trivial. |

Kill Dash Nine | dwite200902p2.java | Trivial. | |

Working Directory | dwite200902p3.java | Straightforward. | |

Wiring the Server Room | dwite200902p4.java | Hard: Travelling salesman problem with a simple distance metric, with memoization. | |

Nash in Traffic | dwite200902p5.java | Hard: Expression parsing and evaluation, iterated shortest paths. Not network flow. | |

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. Similar to DWITE 2009-11 P3. | |

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. Reused from DWITE 2008-12 P4 | |

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: Bipartite graph testing. | |

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 | Medium: Next permutation of a bit string. | |

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. | |

July 2011 (cs4hs) | Root of a string | dwite201107p1.java | Easy. |

Sum of primes | dwite201107p2.java | Easy: Sieve of Eratosthenes. | |

Triangles in a grid | dwite201107p3.java | Medium: Geometry, equivalence detection. | |

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/ | |

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 understand properties of integer factorization. | |

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. | |

October 2012 | Candy Piles | dwite201210p1.java | Trivial. |

Candybar Graphs | dwite201210p2.java | Trivial. | |

Costume Party | dwite201210p3.java | Easy. | |

Trick or Tree’ing | dwite201210p4.java | Medium: Tree recursion. | |

Haunted House | dwite201210p5.java | Hard: Breadth-first search, memoization, probably NP-complete because similar to travelling salesman problem, probably needs exponential time in general. | |

November 2012 | Sugar Rush | dwite201211p1.java | Easy. |

Word Arithmetic | dwite201211p2.java | Straightforward, should use bigint. | |

Bitstrings | dwite201211p3.java | Easy, requires bigint. | |

Magic Trick | dwite201211p4.java | Medium: Rank-based insertion. | |

Car Hoppers | dwite201211p5.java | Medium: Dynamic programming. | |

February 2013 | Travel Time | dwite201302p1.java | Trivial. |

Copycat SMS | dwite201302p2.java | Easy. | |

Triangle Count | dwite201302p3.java | Medium: Dynamic programming. | |

Fencing Problems | dwite201302p4.java | Straightforward: Grid neighbor manipulation, but difficult to interpret the problem statement. | |

Pattern Lock | dwite201302p5.java | Medium: Recursion. |

## Notes

Trivia: *DWITE* stands for *Do While If Then Else*.

DWITE has two incarnations. The first incarnation was by Will Sentjens (I think), from June 2002 to February 2006. The second incarnation is by Hacker Dan and CompSci.ca from October 2007 to February 2013. See the current DWITE about page for more details on the goals and history. At the moment, this collection of my solution code covers about half of the first DWITE incarnation and the entire second DWITE incarnation.

The contest problems statements (PDF and HTML files) are not made by Nayuki. The problems in the second incarnation (Oct 2007 to Feb 2013) are licensed under Creative Commons BY-NC-SA 3.0, and are republished (and slightly edited) with permission.