HSPC: Finding (or Building) a Team

This is a post in my High School Programming Competition (HSPC) series.  For an outline of current and upcoming posts, please see this introduction.
 
At the collegiate level, programming competition teams are typically formed by a chapter of the ACM (Association for Computing Machinery) or a similar club within the computer science department.  While many universities have a CS (or related) department, analogous organizations tend not to exist in high school.  In this post, I hope to share some tips on what to do if you're interested in participating in an HSPC but can't find a team to join.

I'll be writing this primarily from the perspective of a student who is looking for or building a team, as this is what I ended up doing.

School teams

Finding a coach

Most teams tend to represent and are sponsored by a single high school.  If your high school already has a team, there's not much left to do.  Thus, I'll assume there isn't one at your school.  You'll likely want to get a teacher to agree to coach a new team.  If your school has a computer science class, the right teacher to approach is pretty much obvious.

If you don't have a CS class at your school, though, this can be a little more tricky.  Some related classes which attract the type of teachers that could be interested in leading a class include math (especially higher-level math) and science (especially physics).  A robotics team coach (i.e. for a FIRST or VRC team) may be interested in coaching a programming team, too.  If none of these options apply for you, consider looking outside the school for a parent who works in a related field, like engineering or mathematics.

Realize, though, that when you approach this teacher requesting them to advise your team, you're really asking if they'd be willing to spend several hours of their time (possibly likely unpaid) to provide your team with a place to practice, advice for improvement, and the many logistical steps required to get your team to a tournament.  The more preparation and thought you put into your request before talking with your teacher, the more likely they are to agree to help.  Don't just say "I'd like to do programming contests, kthxbai!"  Instead, research a specific contest that is a reasonable distance from your school you'd like to attend, come up with an estimate on the time they'd have to spend per week on this project, and explain (in as precise a way as possible) how you need their help.  This way, they have more information to make a good decision.

Team Members

You will want to find around 3 other people to join your team (team size limits may vary based on the contest you will attend).  If you already know some friends who would be interested in competing, this isn't a very hard task.  However, it may be that you're the only one you know at your school interested in CS.  This is one area in which having a teacher as a coach is very helpful; they may be interested in making an announcement before class, which will get the word out quickly.  Depending on your school policies, it may be possible to create a flyer and post it on a bulletin board in the hall, or post to a class Facebook group.

On the other hand, it could be that you have way too many people who are interested.  This is a good problem!  Many contests will allow multiple team registrations per school, so it may be possible to send everyone who is interested.  However, it is also typical for contests to cap the number of teams coming from the same school; for instance, UVa caps our contest at 3 teams.  In this event, it is a good idea to hold a "qualifier" tournament or give all interested parties a test and take only the top students. 

Community teams

School teams are sometimes infeasible for various reasons; this was the circumstance in which I found myself.  Building a community team tends to be a little more difficult, particularly because there isn't an easy way to locate potential team members.

Finding a Coach

Finding a coach for a community team can be somewhat challenging; most often, it ends up being a parent of one of the team members who may have some relevant background.

If none of your team members' parents have any interest in CS, fear not!  It is completely possible to have a student-led team, but you do need an adult "figurehead" to handle logistical concerns and act as a point-of-contact for the contest director.  Technical mentorship can be sourced through means other than your "official coach;" for instance, you could contact a local university with a CS competition team and ask if they'd be interested in sending a few students to give a presentation and/or provide some feedback on your preparation.

My advice from above on preparing before approaching your potential coach is still applicable in this situation: the more complete of a picture you can "paint" for this person, the more easily they can make a decision to volunteer their time.

Team Members

Many programming competitions are built around the concept of a team of 3 or 4 students working to solve more problems than other teams.  While policies on "one-person teams" vary between host organizations, the general sentiment is that you need team members to do well and to optimally learn.  (My personal experience testifies to this.)  So, although it can be tempting to try to compete solo instead of going to the effort of finding possible team members, it is well worth the time to find friends interested in this topic.

Unfortunately, there is no universal way to contact anyone in a geographic region to ascertain their interest in an activity.  Some options could include posting a notice in a local library, reaching out via Facebook groups, or talking with members of a local hackerspace.

As another point of note, these team members do not even need to be well-versed in programming.  In my senior year of high school, my team consisted of two people who really knew the Java language and two people who knew enough programming to write some simple things, but who were just really good at thinking logically and solving problems.  These contests really boil down to solving problems with programming as simply the medium for recording the solution, rather than a programming event that happens to involve solving problems.

If it is relevant to your situation, homeschoolers tend to have a geographically-defined association that may have a Facebook group or email distribution list.  Although, from your perspective, it may sometimes appear that you are the only person in your community interested in programming, trying an email list like that one can be quite fruitful.

Other Thoughts

This was a very non-technical entry and probably the least important post in the series.  Finding team members and coaches is a "soft-skills" problem, and there is no right answer.  I promise the future posts in the series will be much more technical and easily applicable, but I wanted to write this first because one must have a team before getting really crazy about preparing for a contest. 

Deranged Exams [A Solved ICPC Problem]

This past week, my ICPC team worked the 2013 Greater New York Regional problem packet.  One of my favorite problems in this set was Problem E: Deranged Exams.  The code required to solve this problem isn't that complicated, but the math behind it is a little unusual.  In this post, I aim to explain the math and provide a solution to this problem.

Problem Description

The full problem statement is archived online; in shortened form, we can consider the problem to be:

Given a "matching" test of $n$ questions (each question maps to exactly one answer, and no two questions have the same answer), how many possible ways are there to answer at least the first $k$ questions wrong?

It turns out that there's a really nice solution to this problem using a topic from combinatorics called "derangements."  (Note that the problem title was a not-so-subtle hint towards the solution.)

Derangements

While the idea of a permutation should be familiar to most readers, the closely related topic of a derangement is rarely discussed in most undergraduate curriculum.  So, it is reasonable to start with a definition:

A derangement is a permutation in which no element is in its original place.  The number of derangements on $n$ elements is denoted $D_n$; this is also called the subfactorial of $n$, denoted $!n$.

The sequence $\langle D_n\rangle$ is A000166 in OEIS (a website with which, by the way, every competitive programmer should familiarize themselves).

It turns out that there is both a recursive and an explicit formula for $D_n$:
\begin{align}
D_n &= (-1)^n \sum_k\binom{n}{k} (-1)^k k! \\
&= n\cdot D_{n-1} + (-1)^n;\;(D_0=1)
\end{align}
This is significant because we can use the explicit formulation for computing single values of derangements, or we can use dynamic programming to rapidly compute $D_n$ for relatively small $n$.

Problem Approach

The key observation here is that, using the derangement formula, we may compute the number of ways to answer a given set of questions incorrectly, using only the answers corresponding to those questions.  Instead of focusing on the first $k$ questions, which we must answer incorrectly, let us look to the remaining $n-k$ questions.

Consider the case when we answer $r$ questions correctly.  There are $\binom{n-k}{r}$ ways of choosing which $r$ questions we answer correctly (since the first $k$ must be wrong).

The remaining $n-r$ questions must be answered incorrectly using only the answers to the same $n-r$ questions.  Using our knowledge of derangements, there are $!(n-r)$ ways to assign those incorrect answers.

Finally, note that the number of correct answers, $r$ is bounded by $n-k$; summing over all possible values of $r$, we obtain:
\[S(n, k) = \sum_{r=0}^{n-k} \binom{n-k}{r}!(n-r)\]

Code

Equations are great, but implementation is required for ICPC.  First, we must consider input/output size.  The problem statement gives the following ranges for $n$ and $k$:
\[1\leq n \leq 17 \\  0 \leq k \leq n \]

We can expect that this will fit in a 64-bit integer, as $n! \leq 2^{63}-1$ for $n\leq 20$.  Thus, we don't even need to be careful in computing binomial coefficients due to intermediate overflow!  I'll let the code (and comments) speak for itself:

import java.util.*;
 

public class Test {
  // Basic iterative factorial; just multiply all
  // the numbers less than or equal to n.
  // returns 1 if n < 1 (which is important for n=0)
  private static long fact(int n) {
    long retval = 1; 
    while(n > 0) 
      retval *= n--;
    return retval;
  }

  // Naive binomial coefficient computation 
  // Generally, you need to watch overflow.  But,
  // we can ignore that here because fact(17) < 2^63-1
  private static long binom(int n, int k) {
    return fact(n)/(fact(k)*fact(n-k));
  }
 
  public static void main(String[] args) { 
    //While not recommended in general, we can use 
    // a scanner because we're not reading a lot of input.
    Scanner cin = new Scanner(System.in);
 
    // Precompute the derangement numbers
    long[] d = new long[18]; // we might need values of D_n up to n=17
    d[0] = 1;
    for (int i = 1, j=-1; i < d.length; i++, j*=-1)
      d[i] = i*d[i-1] + j;
    //Process the input
    int P = cin.nextInt();
    for (int caseNum = 0; caseNum < P; caseNum++) {
      cin.nextInt();
      int n = cin.nextInt();
      int k = cin.nextInt();
 
      //S(n, k) = sum(binom(n-k, r)*d[n-r], r=0..n-k)
      long ans = 0;
      for (int r = 0; r <= n-k; r++)
         ans += binom(n-k, r)*d[n-r];
 
      System.out.printf("%d %d\n", caseNum+1, ans);
    }
  }
}

Further Reference

Derangements are discussed in Concrete Mathematics by Graham, Knuth, and Patashnik on pages 193-196.  In those pages, the identities shown in this blog entry are derived.  Also discussed is a closely related problem that may be called $r$-derangements.

In the $r$-derangement problem, we seek the number of arrangements in which exactly $r$ elements are in their original place.  (The number of $0$-derangements, then, is just $D_n$.)

High School Programming Competition: A Series

When I was a junior in high school, I attended ACM@UVa's High School Programming Competition (HSPC).   A friend told me about the event a couple of months before it was to be held, but I did not know anyone else in my hometown who would be interested in (or even capable of) driving multiple hours and spending a Saturday looking at code on a computer screen--so, I sent an email off to the organizers asking if someone could participate as a team of one.  They said yes, and I rolled up early on a Saturday morning in March to find I was the only team with fewer than 3 people, with most teams having 4.  Several hours later, I emerged in 5th place out of the 17 teams, solving as many problems as the 3rd place team (but slower).

The thrill of competition is like nothing else; I had to do this again, but I knew I would need a team.  I spent the following summer and start of fall searching for teammates, and found one other person with programming experience and two more who loved to solve problems and had analytical thinking skill.  We spent the rest of fall and spring preparing for the competition, and returned with a 2nd place standing.

As team lead, I found that there is a surprising lack of material explaining how a team should prepare for a high school programming competition (hereinafter, HSPC).  As I now organize the ACM@UVa HSPC, I have received email and verbal feedback from coaches asking how to prepare, so I know content in this area is still lacking.  I aim to resolve this issue by writing a series of blog posts to convey the lessons I learned in preparing a team.

The advice I have will apply primarily to ICPC-style programming contests, like those held by ACM@UVa, UMD, VCU, Cornell, and others.  However, many of these concepts will cross-apply to other contest styles.

The topics I'll cover are:

1. Finding a team - If I don't have a team, how can I grow interest?
2. Language Selection - What language should I use, and any good libraries?
3. Contest Environment - What will the contest computers be like?
4. Problem Types - How do I solve this problem?
5. Meeting Agenda - I'm stuck running this! What should I do?
6. Resources - Where else can I get help?

At the end of the series, I'll post a list of contests organized by region and timeframe.  If you're reading this and have questions or suggestions for other topics (even if you're reading this years after I originally posted), leave a comment!

I believe that competition drives performance and is a necessary part of the educational process.  My experience in high school programming competitions was a major factor in my higher education decision process (both major and school selection) and pushed me to improve.  Because this was such a large part of my life, I want to encourage others considering this activity.

I should note that what I write here in no way reflects anything official about the ACM@UVa HSPC.

Eight Books on Math and Computer Science

A friend recently emailed me asking for titles of books I'd recommend to read over the summer, particularly to prepare for computer science and mathematics.  I've adapted my suggestions into this post.  I'd like to note that I've restricted my responses to "non-textbooks;" otherwise, I'd have several more additions that would increase the average page count and price quite drastically.  As such, these books don't have problems to work or present an extreme level of detail, but in many cases they present enough information to provide a strong foundation and context for math and CS classes.

From Mathematics to Generic Programming
Alexander Stepanov and Daniel Rose (on Amazon)

I will most likely write a separate blog post about this book.  I read it during the end of the fall semester and found that it presented a very interesting approach to designing reusable code by utilizing principles from abstract algebra.  It's written to be accessible by someone who hasn't studied abstract algebra yet, which means it also can serve as an introduction to that subject.


CODE: The Hidden Language of Computer Hardware and Software
Charles Petzold (on Amazon)

Four years ago, I wrote a review of this book on RoboDesigners.  At that time, my perspective was that of a high school student and I thought the book was interesting; with the additional perspective of a year of college study in Computer Science, I cannot recommend this book highly enough.

By "building" a computer piece-by-piece from the idea of a relay through developing a simple assembly language, it covers nearly all of the material as the Digital Logic Design course I took, but in an easy-to-read book.  If you comprehend the material in this book, you will be able to coast through DLD.

A Mathematician's Apology
G. H. Hardy (on Amazon) 

When a mathematician with Hardy's stature writes a book on why he studies math, it's probably advisable to read it!  Multiple professors of mine have said it's a book any mathematician should read and I wholeheartedly agree.  It's really short (the printing I've linked above is only 154 pages), but the content is amazing.  Hardy addresses the complaints many have with pure math and embodies the spirit of "doing mathematics for mathematics' sake."  If you are thinking about pursuing a theoretical route in either CS or math, I highly recommend you read this book.

The Code Book
Simon Singh (on Amazon)

I love codes--anything resembling secret or hidden knowledge has a particular allure.  Singh does a great job discussing the past, present, and likely future of codes, ciphers, and cryptography in this book.  Starting with Caesar Shift (what good historic code book doesn't?) and traveling through centuries to discuss the Vigenère cipher, RSA encryption, and the general idea of quantum cryptography, this book gave me a broad understanding of where we are at now with codes and how we got here.  It also includes the clearest description of the actual flaws in Enigma that I've ever read.

In Pursuit of the Unknown: 17 Equations that Changed the World
Ian Stewart (on Amazon)

Every equation has a story--how was this truth discovered, who discovered it, and what exists now because of it?  This book examines 17 equations and their impact on society.  If you're actually reading this blog, the early chapters will probably be old hat, but after (and including) Chapter 4 the content becomes quite interesting. 

Reading Chapter 4 helped me visualize vector fields for Vector Calculus and Differential Equations in the context of planetary movement (and it finally made me understand the age-old analogy for dense objects warping the fabric of spacetime).  The last chapter was also memorable for its description of a particular equation used in high-frequency stock trades, the misapplication of which Stewart claims was partially responsible for the 2008 recession.

The Music of the Primes
Marcus du Sautoy (on Amazon)
It is said that Gauss once asserted that "Mathematics is the queen of the sciences and number theory is the queen of mathematics."  This book outlines the history parts of this "queen of mathematics" that relate to prime numbers.  It includes mini-biographies on the people who made great breakthroughs in the search for a formula for the nth prime; obviously the story isn't finished yet, but it's a pretty neat overview of how primes are important, who made them important, and other related topics.

As someone who finds Number Theory fascinating, I'd recommend this book especially to people who like Project Euler problems--not because it will help you solve the problems per-se, but because it provides some historical background to the people who developed the equations you use to solve Project Euler problems.

To Engineer Is Human
Henry Petroski (on Amazon)

This is a wonderfully dry book--one that might bore some people, but I loved it.  (I actually read this right after reading CODE.)   Petroski discusses the role of failure in design, why the principles of engineering are intuitively "built-in" to the human brain, and how engineers must account for error in their designs.  The most thought-provoking and the single most vivid idea that has stuck with me since reading this book was a connection he drew between computerized design and an increased failure rate in new products (toys, furniture, or even buildings).

The Abolition of Man
C. S. Lewis (on Amazon)

C. S. Lewis is known primarily as the author of The Chronicles of Narnia, then as a Christian Apologist.  So then, why am I asserting that this particular book is relevant to all computer scientists?  In fact, this book is of particular interest to anyone working in a field of applied science.  It provokes thought on why we're solving the problems that we are and why we're even interested in the sciences.  In particular, it discusses the effect of a morality outside ourselves on the purpose of science; the third and final chapter paints a vivid picture of what happens when we reduce mankind simply to "nature."  This book bears re-reading, and perhaps someday I'll write another blog post on why every scientist (applied or not) should read this book.

Factorization and Number of Divisors

How many divisors are there of the number $1281942112$?  It turns out that determining the answer to this problem is (at most) only as difficult as determining the prime factorization of the number.  In this blog post, I will outline a solution to this (and similar) problems.

The Math

The Fundamental Theorem of Arithmetic guarantees each positive integer greater than $1$ a unique prime factorization.  We write this factorization as:
$$N = p_0^{e_0}p_1^{e_1}\cdots p_n^{e_n}$$
where $p_k$ is a prime number, and $e_k$ is its corresponding exponent.  This provides us with useful information regarding divisors of $N$: any divisor of $N$ must be comprised of some combination of those prime factors (and exponents).  Specifically, we can define the divisor, $D$, as:
$$D = p_0^{a_0}p_1^{a_1}\cdots p_n^{a_n}$$
where the $p_k$ are the same as in the factorization of $N$ and $a_k \in \{0, 1, \ldots, e_k\}$.  To find the total number of divisors, we multiply together the number of options we have for each exponent.  That is,
$$\text{Number of Divisors}\; = (e_0+1)(e_1+1)\cdots(e_n + 1)$$

Example:  Consider $N = 20$.  In this case, $N$ has $6$ divisors; to determine this without needing to list them all, we may note that $N = 2^2\cdot 5^1$.  Using the notation described above, this means that $p_0 = 2,\;p_1 = 5$ and $e_0 = 2\;e_1 = 1$.  Each of our divisors will be of the form $2^{a_0}\cdot 5^{a_1}$, where $a_0$ could be $0, 1,$ or $2$ and $a_1$ could be $0$ or $1$.  Since we have $e_0+1 = 3$ options for $a_0$ and $e_1+1 = 2$ options for $a_1$, we have $3\cdot 2 = 6$ total divisors.  In case you were wondering, the list of divisors is:
$$\{2^0 5^0, 2^1 5^0,2^2 5^0,2^0 5^1,2^1 5^1,2^2 5^1\}$$

The Program

We're not out of the woods yet--we have a formula, but we need to write a program to make use of it.  The first thing our program needs is a list of primes.  I'm going to assume you have a function already that can generate a list of primes.  A prime-listing function is an important tool in any programmer's toolkit, but I'll save that for a future post.

The pseudocode for our program is below:

numberOfDivisors: int N -> int divisorCount
  divisorCount = 1
  for (p = 1 to floor(sqrt(N)) && p prime):
    exponent = 0 

    //Determine exponent of p in prime factorization
    while (p divides N):
      exponent++
      N = N / p


     //Update divisorCount
     divisorCount = divisorCount * (exponent + 1)


    //In this case, there is one prime factor greater than the square root of N
    if (N != 1) divisorCount = divisorCount * 2


  return divisorCount

This is mostly straightforward: We iterate through all prime numbers less than the square root of N.  For each prime, we determine how many times it divides N--this is that prime's exponent.  We then multiply the current divisor count by one more than the exponent.  I have pushed an update to my math GitHub repository that includes a Java version of this algorithm in NumberTheory.java.

If we kept track of which primes divide $N$ (for example, adding them to a List whenever we enter the while loop) this program is easily modified to output the prime factorization of a number.

The Analysis

Before analyzing the performance of the algorithm, it would be best to explain why we only need to use primes less than $\sqrt{N}$, not primes less than $N$.  This is because there can only be one prime factor of $N$ greater than $\sqrt{N}$, and (if there is one) it must have only be raised to the $1$st power.  A proof by contradiction works well here (I'm skipping some rigor, please don't kill me):

Assume that there are two prime factors (not necessarily unique) $p$ and $q$ of $N$, such that $p,q \gt \sqrt{N}$.  Let the product of the remaining prime factors be some integer $m$.  Then we have:
$$\begin{align}
N &= p\cdot q\cdot m \\
&\le p\cdot q \\
&\lt \sqrt{N}\sqrt{N}\\
&\lt N\end{align}$$
This is clearly a contradiction, thus we have proven that there cannot be at least two prime factors of $N$ greater than $\sqrt{N}$.  Equivalently, there may only at most one prime factor of $N$ greater than $\sqrt{N}$.

This explains why we don't need to use primes greater than $\sqrt{N}$: if, after "dividing out" all primes less than $\sqrt{N}$, we are left with a number, then that number must be the single prime factor of $N$ greater than $\sqrt{N}$.

On to the performance of the algorithm.  Assuming we are given a list of prime numbers (and don't have to compute them), this procedure has a time complexity of $\mathcal{O}\left(\pi\left(\sqrt{N}\right)\text{lg}(N)\right)$ and $\Omega\left(\pi\left(\sqrt{N}\right)\right)$, where $\pi(x)$ is the prime counting function and $N$ is the input number.  ($\Omega$ provides a lower bound, and $\mathcal{O}$ provides an upper bound.)  Let's see why.

We have an outer-most for loop that makes one iteration for each prime less than $\sqrt{N}$.  This gives us the "$\pi\left(\sqrt{N}\right)$" part of the bounds.  For the lower bound, we would assume the inside of the for loop executes in constant time, every time.  (That is, we never enter the while loop.)  This occurs when $N$ is a prime number.  For the upper bound, we may assume that we execute the while loop at most $\text{lg}(N)$ times each iteration.  This is because $\text{lg}(N) = \log_2(N) \gt \log_b(N)$ for $N \gt 2$ and integer $b\gt 2$, and $\lfloor\log_{p_k}(N)\rfloor$ provides a fairly close upper bound on the exponent of $p_k$ in the prime factorization of $N$.

The upper bound can be improved by performing some summation and simplification, but it's close enough to show how fast this algorithm is.

How to Learn Haskell

To grow my programming repertoire, I decided to learn a functional language; at the recommendation of a friend, I selected Haskell. Thus far, it seems great.  As a mathematician at heart, I love the way that the notation and language constructs resemble math (list comprehensions, tuples, function composition, etc).  In this blog post, I will outline the major resources I am using to learn Haskell.

To learn Haskell, I am using the ebook Learn You a Haskell for Great Good.  Yes--terrible grammar in the title, but it's (fairly) grammatically correct on the inside.  This is a great introduction to Haskell, although I'd highly recommend prior knowledge of another programming language like Java or C++.

Unfortunately, that ebook is somewhat lacking in practice problems.  It does have examples, but there isn't a true "exercise" section like one would find in a textbook.  This is a common fault with online programming tutorials; to be honest, creating a good exercise set is hard work.  To remedy this problem, I turned to a favorite site of mine, HackerRank.com.  While designed for competitive programmers, this site also has an "introductory" set of functional programming challenges (see here).  These range in difficulty from very easy to extremely hard.  This provides a great compliment to the tutorial I referenced above.

Finally, one last resource I am going to use after finishing Learn You a Haskell is a set of lectures by former University of Virginia student-teacher Nishant Shukla.  Although I have not been able to view them in great detail, they present a great introduction to Haskell.

Sad news: Project Euler

As many in the Competition Programming circuit already know, the amazing website ProjectEuler.net was taken offline on June 15, 2014 due to a security risk. Fortunately, the problem list was restored and is available, but account functionality has been disabled.

If you have an account on Project Euler, it is highly recommended to change reused passwords on other websites.

EDIT (in case anyone stumbles upon this in the future): The good news is that Project Euler is up and running again!  The bad news is that I managed to lose my login credentials in the shuffle, so I'm starting over.