Bounded-Error Log

After the first stage of selection camp, I was very nervous because I was fifth place in a selection sequence that would finally result in a team of four.

I screwed myself over on the first mock test by committing to a bad implementation method on a problem that was hard to get points on. My method seemed simple, but the memory usage leaked out in a way that was confusing and hard to patch; unfortunately, I tried to patch it in increasingly desperate and convoluted ways rather than scrapping the method, and thus missed out on many of the points elsewhere.

During the second test I failed to read the last problem carefully and spent too much of my time on the second problem, once again missing out on a lot of relatively easy points. I had optimized and optimized and pushed my quadratic runtime down to linearithmic, which would allow me to get the points for the last subtask — or so I thought. But with 10 minutes left I had all but one testcase right, and after desperately rereading my code, I realized that I had a string comparison stuck in an inner loop that could make my runtime degenerate to quadratic if the input string had lots of the same digit. In order to have a solidly linearithmic algorithm, I would have to implement a suffix array. Ten minutes? I gave up. (The problem setters told me afterwards that hashing would have worked too; I didn’t think of that at all. Oops.) I spent the 10 minutes reading the last problem and still failed to read it carefully. So that did not go very well.

But, as the title probably gave away, during the third and fourth mock tests everything went much better than expected. :)

As requested, a puzzle post! Straight from the WTF-variant department. Quite hard.

This is a Fillomino, with the additional constraint that for each polyomino, there must not exist a path (i.e. a sequence of cells, each orthogonally adjacent to the next) that includes each of the polyomino’s cells exactly once (and does not include cells outside the polyomino).

As a degenerate case, 1-ominoes are banned as well.

First Google Code Jam!

The format of this competition, allowing us to run programs on our own machines, brought up a very interesting issue for me: what programming language should I be using? (I had had similar considerations for IPSC 2013, but GCJ’s problems are closer to the traditional ACM-ICPC style.)

The obvious choice is C++, the language I use for roughly every other competition, but its safety (or lack thereof) is not very appealing. I need speed, but not that much speed. Unfortunately I still haven’t gotten around to learning any other friendlier mid-level languages (on the list: D, Go, or Rust), so I have no close substitutes for C++ right now.

Python is certainly available for a reliable arbitrary-length integer type, if nothing else.

As for non-candidates, Java has BigInteger and memory safety, but all in all I decided the benefits are too minor and it’s too ugly without operator overloading. Scala is probably way too slow. So I don’t expect to be writing either language.

The only difficult choice I have to make is, of course, Haskell — which can be quite fast, even while it’s ridiculously type-safe and expressive and referentially transparent and easy to reason about, once you’ve:

• figured out how to do the problem
• scrapped step 1 and actually figured out how to do the problem functionally
• gotten the thing to compile

Even if I can handle step 1, step 2 is by no means a simple task, as my struggle to implement a mere Sieve of Eratosthenes efficiently shows. That is fun, but not at all intuitive; I am doubtful I can do this under contest conditions. It is extremely difficult to transfer my skills in learning how to implement, say, a segment tree or treap into this language.

But! Google links to the programming language breakdown for 2010 Qualification Round as an example, and much to my surprise, Haskell ranks somewhere between sixth and tenth place in popularity (depending on what you sort by), so there are functional superprogrammers who can presumably do something like this.

As it happens, I ended up implementing all four solutions to the qualification rounds in Haskell, because of the relaxed time limit and lack of any involved algorithms and data structures. I think it was worth it.

First, I got worked up about the test. Then I got a score and ranted about it on this blog. (I’m still uncertainly hoping that didn’t come off as arrogant. Let me add, I did not get a perfect PSAT.) Then a friend pitched to me the idea that I write an article about it for my school newspaper, which I did. It was far too long. As if that weren’t enough, I then decided to examine whether the SAT was an accurate prediction of “academic ability and success” for my English research paper. Now I’ve come full circle to this blog, where I’m going to try to synthesize and conclude everything, free of the shackles of the research paper format, to allow me to move on with my life. This post contains bits lifted from all three essays and lots of new stuff; I’ve been editing it for so long that I feel like I have it memorized. Its word count is around that of the newspaper article plus the research paper, i.e. far far far too long.

But whatever, nobody reads this blog anyway and I have to get this out of my system. When I said I wanted to “move on with my life”, I really meant my winter homework. Oops!

Disclaimer: I am not an admissions officer. I have not yet even been accepted to a prestigious university (despite rumors to the contrary…), for whatever definition of “prestigious”, unlike some of the bloggers I’m referencing. So some of this is pure speculation. On the other hand, some of it is researched and referenced, and I think the pure speculation still makes sense. That’s why I’m posting it.

Okay, here we go…

Let’s start with the question of accurate prediction. The SAT is a useful predictor, but not as useful as one might assume. Intuitively, it ought to be more accurate than other metrics because it’s a standardized test, whereas GPAs other awards vary by habits of teacher and region and are hard to compare objectively. But as a study from the College Board itself (PDF) found:

the correlation of HSGPA [high-school GPA] and FYGPA [first-year GPA in college] is 0.36 (Adj. r = 0.54), which is slightly higher than the multiple correlation of the SAT (critical reading, math, and writing combined) with FYGPA (r = 0.35, Adj. r = 0.53).

Of course, that doesn’t mean the SAT is worthless, because combining the SAT score and high school GPA results in a more accurate metric than either one alone. But by “more accurate” I refer to a marginal improvement of 0.08 correlation.

Random video! Although I feel that I’ve heard it earlier, my first conscious memory of getting linked to it is from this post. At first I thought it would be the right background music for this post, but upon further reflection I think it mainly suited me while I was writing this post. Well, it’s topical if you mentally replace “day” with “year”.

Anyway. Around this time a year ago, I paused my participation in big high-school competitions, for a variety of reasons.

Firstly, I stopped attempting to make IMO both because I wouldn’t get that much from the training and because other people ought to have the opportunity. I was concerned that I might condition myself to only be able to do math with the short-term motivation of contests. Better to focus on college math and maybe some original research, I thought. During the year, I did lots of the former and very little of the latter. Meh.

As for the IOI, my obvious next target: I was tired of training and going abroad while paranoid about whether my immune system would hold up. I didn’t feel that the IOI was worth that. To some degree, I also felt burned out about programming. Long story short, my treatment should end soon, and learning Haskell completely resolved the burnout problem.

But the most important reason, I think, was that “high school was too short”. I started math competitions ridiculously early and didn’t spend much time exploring other interests. I thought I knew myself well enough that I could say I didn’t have many more interests at all, but I was completely wrong (psych nerds will reflexively note this to be the Dunning-Kruger effect). I coded lots in weird languages — Haskell, as mentioned previously, plus Scala, plus all manner of other magical command line tools. I wrote my first math problem and submitted it officially, picked up a new instrument, went to a debate competition, served as an unimportant tech guy for MUN, discovered and became hooked on Pentatonix, participated in three puzzle hunts in Australia and one in Massachusetts, figured out my rough political stance, rode a boat, got retweeted by @eevee and @Kyrgyzstan_News, increased my Neopets™ fortune by over 3400%, and lurked on FurAffinity a little too much.

But now, dear competition world, I’m back.

I did it!

I have to admit, I got unhealthily worked up about getting this score.

For the purposes of college, I only ever wanted a score that wouldn’t be a deal-breaker — anything above 2300 would be enough. Any other time I had left would be better spent in other endeavors. Such endeavors might help on the college app, but more importantly, I’d also get to enjoy them.

So why am I here? Partly it’s because my classmates got worked up about it. Somebody specifically requested me to post my score somewhere. And partly it’s because there couldn’t be a better way at the moment to establish my authority to (yet again) rant against standardized tests here.

Logic puzzles are easy to construct if one doesn’t have some specific pattern or theme in mind. It’s just that, given the increasing number of constructors and puzzles with amazing themes, I don’t think it’s very meaningful for me to just construct more puzzles of the same genres by putting down clues randomly. That’s why, for my seventeenth birthday, I took the puzzlehunt route and made something without instructions that is not completely solved by logical deduction. Still, I’ve provided all the information needed to do this puzzle initially, so I hope my not getting the inductive bits test-solved can be excused.

“I like fantasy books! I used to read a lot of Eoin Colfer.”

“What does that mean, used to? You don’t read anymore? That’s so sa-a-a-ad…”

Our teacher and I had this conversation during our first English class, and I realized I agreed with her. Well, no, of course I still read: news articles, r/AskReddit threads, and the books we get assigned in class. But not fiction, almost. As I later mentioned to my teacher, I followed Sam Hughes’ Ra avidly (something I highly recommend). That was it.

What does my present self still think of Eoin Colfer? Although I adored the Artemis Fowl books when I was younger, my interest faded, but not before I had recommended it to my sister. The conversation spurred me to get out the seventh Artemis Fowl book, which I had stopped reading halfway through a year ago, and finish it. It was still true that I didn’t like it as much, because I couldn’t feel the high stakes strongly in the book and I found that the joking asides compounded the problem. But a few days later, when we took a trip to the Taipei library, I found the eighth book and borrowed it, plowing through nine-tenths of the book before we left. The ending seemed to be happy but still felt counterintuitively poignant for me. In any case, I had closure.

So what’s the lesson? Authors vary in output too. I was naïve to suppose that because I found this book boring, I had outgrown all books that were even vaguely similar. In the same trip, I also borrowed a bunch of other random fantasy books, plus a realistic fiction book about a teenage pregnancy, just for kicks. It turned out to be surprisingly good. In a week, I read four books, cover to cover, despite a typical load of homework and chemo.

Any excuses I made before about not having enough time simply don’t hold water. Still, I have yet to figure out if this sort of reading is sustainable, because not every book is so engrossing. Far from it…