Bounded-Error Log

This post, or most of it, was published password-protected once because… well, I explain that below. (To the one person who actually bothered asking me for the password, just so you know, I did add and rewrite parts. More than a few.) I forgot how distinctly powerful a disincentive a large 2300-word block of text is to the average person, especially when the subject of half of those 2300 words is teenage angst (I’ve already linked to xkcd 1370 in enough places so I’m not even going to embed it here) interweaved with an insufferable amount of rationalist jargon. This will probably filter my readership more than sufficiently already.

I have still decided to protect one detail of the thought process, though. But even after that, I guess I do care more about how many people read this than I do for most of my other posts, so here’s a primitive attempt to gauge interest; if you choose anything beyond the first choice, I would also appreciate if you leave a comment, even if you don’t think you have anything to add:

I haven’t posted for a long period again, but I don’t feel too bad about it.

Well, until I look carefully at my blog draft folder and remember that I have 90%-finished drafts about the two debate competitions I went to (November 2013 and March 2014), and winning the previous Mystery Hunt (January 2014), and my summer trip to Penghu (July 2013). Which will probably never get posted out of awkwardness.

Oops.

But I’ve been busy, completely righteously busy, with college apps to write and algorithm classes to teach and speeches to write and a math club to sort-of lead and all the typical homework besides.

And then (for those of you who don’t have me as a friend on Facebook) I got accepted to MIT and Caltech early.

And for a few days after that, I checked Facebook about sixteen times a day for the Class of 2019 group discussion, except for one day when I really needed not to, thanks to the power of committing to my HabitRPG party to do something. I am increasingly learning that procrastination is something that has to be actively and strategically fought. But that’s not what this post is about.

College.

This post was written in Traditional Mandarin Chinese for my fellow competitive programmers in Taiwan.

題目在這裡，HOJ 226

有關的題目出現於NPSC 2014 高中組決賽pD。

前置要求：treap (split, merge)跟在上面實作區段操作（請參考資訊枝幹）。

這裡沒有完整的解答code，因為AC是要用血汗換來的才值得 :-)

Treap

我討厭單字母l的變數名稱（跟1太像了。我沒有被這個雷過，這只是自己對自己程式碼可讀性的要求），所以我的子樹叫做lc(left child)，rc(right child)。

struct Treap {
    Treap * lc;
    Treap * rc;
    unsigned pri;
    char val;
    int size;
};

int size(Treap * a) { return a ? a->size : 0; }
void pull(Treap * a) {
    if (a) a->size = 1 + size(a->lc) + size(a->rc);
}

Well, there had to be something here.

Unfortunately I don’t have time for anything more complex, so here’s a low-effort illogical puzzle for the occasion. (It has been testsolved, at least. Thanks, Yoshiap.) It also features a brand new category, so as not to distract the people on LMI.

If you don’t already know what occasion it is, it’s easy to find out by looking through my archives or possibly anywhere else I’ve left a trail online. Or you could solve the puzzle! (Or you could scroll down to read the solution!) If this puzzle had an answer, it would be a nine-letter word, although like most of mathematics, it’s less about the answer than about the path you take to get there…

original sillier post

The “Extreme Value Theorem”, according to my old calculus textbook (Larson, Hostetler, Edwards, 8th ed.), is “A continuous function defined on a closed interval attains a minimum and a maximum on the interval.” The calculus textbook continues,

Although [it] is intuitively plausible, a proof of this theorem is not within the scope of this text.

Of course Rudin proves this, but coming from an unrigorous calculus background, the required deductions span three chapters and are very hard to motivate. That’s probably because it proves things for extremely general objects.

In particular, I have no idea why the definition of “compact” is what it is: “a set for which every open cover has a finite subcovering”. Therefore, here’s a less general but more motivated proof, from the grounds-up.

Definitions

Real numbers are hard to define. We only need to know that we can add, subtract, multiply, divide, and compare them, i.e. they’re an ordered field, and that they have the least-upper-bound property. That is, if we have a set of real numbers that are bounded above, then the set has a least upper bound, a bound that “perfectly fits” the set. Precisely, the bound must be such that every element of the set is less than or equal to it, and no smaller value satisfies the same property.

Continuing the porting of stuff from betaveros.stash, and adding more stuff.

Mnemonic

Here’s my mnemonic table for digits, inspired by an old Martin Gardner column. I wrote from memory the first 132 digits of 2012! correctly at IMO 2012 with this table. I had remembered more, but unfortunately, if I recall correctly, I confused myself over whether I had encoded a 5 or a 2 by the S of “nose”, because this is supposed to be more of a phonetic code than a spelling one — otherwise double letters would be confusing and lots of randomly appearing digraphs would be wasted, because English is weird.

• During the first day a guy came into the secret computer room that the Taiwan team had concealed themselves in, saw us watching anime (SAO 2 among others), and innocently asked, "Are you the Japanese team?"
• The organizers had provided a free whack-a-mole machine, two basketball machines, a Kinect, and a table soccer table in the basement outside the dining hall. I don’t know what it is with science olympiads and table soccer; it’s been provided at all three Olympiads I’ve gone to. Can this be just a fluke?
• Paul spent most mornings and evenings playing Kingdom Rush in our room. Kingdom Rush is a great game, but the reason I put it here is that I was mildly amused to see a Kingdom Rush screenshot in Evan’s IMO 2014 report when it came out. Things that transcend boundaries…
• Somewhere among the many occasions when I abruptly switched to English to greet my classmates, our team developed the "Hey, Brian!" meme, which then got two letters transposed. Just for your information.
• I spotted T-shirts from IOI 2011, IOI 2012, IOI 2013, IMO 2012, Google Code Jam, TopCoder, Codeforces, Dropbox, and Quora.
• There really does appear to be a critical mass of confused people dining in one place above which clapping for no reason is contagious. I observed this during IMO 2012 too. The new thing I learned was that the same trick also works with singing “Happy Birthday” to some degree.
• During one of the bus rides, I was randomly pulled into a conversation about Phineas & Ferb. I impressed some contestant (I don’t remember which country he came from, unfortunately; it might have started with a T?) by mentioning the English name of the evil genius, Doofenshmirtz. (For a few seconds I wondered if I had met a certain IMO legend again.) The guy congratulated me, then remarked that my eye cover made me look like a character from Happy Tree Friends. "It’s not good news to be a character from Happy Tree Friends. Especially since we’re on a bus. Do you know the episode on a bus?" I didn’t know the episode on a bus, and I was pretty sure I preferred not to know.
• I still remember xyz111, the full scorer from China, for writing the Codeforces round (#254) that totally pwned me (my first rating decrease!) and then issuing an editorial in response to an unexpected solution saying,

  This is my mistake, and I feel sorry for not noticing that, I’m too naive, and not good at solving problems. Please forgive me.

  o_O

  not good at solving problems

  O_o and people wonder why I’m humble…

No, I didn’t forget. Not for one minute. I was doing homework. I am very happy because that means I was actually carrying out my priorities as I envisioned them. I’ve probably edited this post too many times, though. Meh. But it’s the first weekend after finishing summer homework, so here we go again!

Fun fact: This is by far my favorite post title in the entire series. Possibly in the entire history of this blog.

In the morning of the last day of official IOI activities, there were a bunch of cultural activities, e.g. writing Chinese characters calligraphically, doing tricks with the diabolo, or picking up beans with chopsticks, and noncultural activities, e.g. getting somebody to pour water into a cup on your head while he or she was blindfolded. Due to the last activity I got wet, but my shirt dried really quickly. And alas, even though I had taken calligraphy summer classes a long time ago, my calligraphy was awful — robotic, lifeless strokes without the right aesthetic proportions to make up for it. Blargh.

Anyway, lunch followed, and then it was time for the closing ceremony, in the same building as the other ceremonies and contests. Our team caught the ending song of in a Chinese musical being rehearsed as we walked into the auditorium. While we waited for everybody, we milled about waving flags that our various teachers had brought, including not only Taiwan’s flag but also flags of my school, thoughtfully brought by teachers who had volunteered. A little later our leader told us that all the leaders had discussed the matter during a meeting and decided that we shouldn’t bring any flags to the stage while receiving our medals, so we were going to have to make do with being patriotic and school-respecting off stage.

There were a few performances, including two aboriginal music performances and the musical we had seen rehearsed ealier, which was a fun rock musical rendition of some Chinese tale that seemed to have been sharply abridged, giving it the plot depth of a Wikipedia stub-article synopsis — a conflict, boy-meets-girl-and-falls-in-love, and a lamenting Aesop song conclusion with thrillingly vague general applicability. But the singing and counterpointing and atmosphere were good. I guess it was proportional to the relative importance of the performance to the closing ceremony. The program interleaved them with the long-awaited medal presentations: one round of bronze medalists, one round of silver, one round of gold.

Dum-dum-dum-dum, medals! The home team advantage was really obvious here; the cheering and the medal-presenter handshakes were both significantly more forceful for Taiwan’s medalists.

Naturally, after the normal medals had been exhausted, the three full scorers received bags with prizes that may forever remain unknown to my sorry self, as well as a standing ovation from everybody in the auditorium. The orchestra had been going through ABBA songs during the ceremony, and very considerately played “The Winner Takes It All” for this part. It was impossible not to mentally fill in the lyrics.

The winner takes it all
The loser has to fall
It’s simple and it’s plain
Why should I complaiiiiiiiin?

Speeches followed. Most were just average forgettable speeches, but Forster gave another speech that was somehow even better than the one he gave at the opening ceremony, with nonstop golden quotables such as:

Shamelessly getting unfinished business out of the way. Yup, that’s me.

Excursion Day 1. We traveled down to Yilan on a bus. I played guess-it with Paul.

1. Name a card and ask the other player if he or she has it. These questions must be answered honestly.
2. Guess the left-over card. The guesser wins if correct; the other player wins if not.

Guess-it is not trivial because sometimes you should ask the other player if he or she has a card that you already see in your hand; otherwise whenever you answered “no” to a query you’d immediately guess that the asked card is the hidden one. It is actually a solved game in the sense that the probabilities of the Nash equilibrium strategy for when to guess and when to bluff have been worked out already, but they’re not simple probabilities by any means and humans are terrible randomizers anyway. A few rounds of it sure beats rock-paper-scissors. I was very amused to lose almost all our games with 11 cards but win almost all of our games with 13.

Okay, no more gratuitous narrative excursions into game-theory. The first stop, National Center for Traditional Arts, was a very laid-back culture place with old-fashioned retro shops and streets.

We watched a 3D glove puppetry (布袋戲) video, in the same session as a lot of the leaders.

I started trying to sleep at 9 the night before the contest, tossed and turned in bed until 10, then fell asleep and got up at 3:35 in the morning. Blah. At that point, I went to the bathroom and applied some chapstick before trying to go back to sleep until 6. After breakfast, I grabbed a few minutes of sleep on the bus to the convention center where our contest would be, then slept on a sofa outside the actual contest hall alongside most of the rest of our team as we waited for a very long time until it was okay for us to enter. Competitions really mess with one’s sleep schedule.

Then, much too soon, we could enter. Day 1 of the contest was about to start.

The laptops were as yesterday, although they were protected with a white screensaver that indicated my name and ID as well as a countdown to the start of the contest. I was glad to see that my mousepad and all my writing utensils had survived without me. Somebody had the sense of humor to project an online stopwatch with an animated bomb fuse onto the screens to indicate the remaining time, which, once again, there was a lot of.

I conferred briefly with Paul (TZW (alphaveros (?))) about vim settings for a bit, but there were still fifteen minutes left or so. I idly stretched, practiced typing my .vimrc on an imaginary keyboard, and watched as the US dude two tables to my left unplugged his laptop’s mouse and rearranged absolutely everything on his table using the surface under his chair as swap space. (Well, that was how I mentally described it at the time, pending further revelations. (hint hint))

Then it began.

Okay, I guess it was really naïve of me to suppose that I could get any considerable amount of blogging done before the IOI ended. Onward…

We left off at the end of the practice session. As if somebody were taking revenge against us for not having to suffer through any airplane trips, we were served a cold airplane meal for lunch.

Seriously, the box had a sticker that noted its manufacturer as something something Air Kitchen and another translucent sticker that badly covered an inscription saying the same thing in much bigger letters. It contained a cold apple salad, a cold chicken bun, a cold flat plastic cylinder of orange juice, and a package of plastic utensils that was exactly like the utensils that came with every airplane meal ever. I was disappointed, but at least the salad tasted okay, and I ate an extra one because two of my teammates volunteered theirs.

To pass the time, we played an extra-evil ninety-nine variant. Apparently this is a very Taiwanese game because lots of student guides were teaching their teams the game, although our special cards differ from the ones Wikipedia lists in a lot of ways and our evil variant created more opportunity for sabotage and counter-sabotage and bluffing. 7s are used to draw your replacement card from somebody else’s hand, and that person cannot draw again and will have one less card; aces are used to swap your entire hand with somebody else, who also cannot draw a card; small-value cards can be combined to form special values (e.g. play a 2 and 5 for the effect of a 7) but after playing a combination you can only draw one replacement card; and later, to speed up the game, we added a rule where all 9s had to be unconditionally discarded without replacement but would still get shuffled back into the draw pile. Players lose if it’s their turn and they have no playable cards, including no cards at all.

While we were playing and repeatedly reveling in everybody ganging up to beat the winner from the last round, an instrumental version of “You Are My Sunshine” played on repeat in the background for literally the entire time. It wasn’t a very good version either. If you didn’t listen carefully for the fade-out and few seconds of silence at the end of each loop, you’d think that the loop was only one verse long.