Bounded-Error Log

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.

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.

Yes, I know day 1 of the contest already ended and is probably a more interesting topic to blog about, but I finished writing this last night just before the internet was cut off to quarantine the contestants from the leaders, who received the problems and began translating them. I didn’t know about this until it was too late, which is why I’ve been waiting since yesterday to post this.

To provide a counterpoint to the last post, one of the many, many advantages of entering an international competition is that you get to meet a lot more people you already know, so there’s less time spent being socially awkward. While waiting for stuff to happen, aside from all the expected time spent with the Taiwan team, I also talked to, played games with, and otherwise entertained a whole lot of people I already knew, including my schoolmates (no less than fourteen of them were volunteers) and some of the college students who had shepherded us around during olympiad training.

Which is a good thing, too, because there was a lot of waiting.

First I waited for my teammates; my parents had decided to take me to the hotel (Fullon Shenkeng) directly, since I had a lot of stuff, and I had arrived early. This took about an hour, after which we had lunch. Then I waited for the hotel to give us our room cards, which took about five hours, after which we had dinner. Finally, at night, I waited for the Codeforces system tests. Very nerve-wracking. But I’m getting ahead of myself.

Advantage #2 of being the home team: you can talk to all of the organizers and volunteers fluently, so you can get them to help you more quickly. Although we waited for our room cards for an obscenely long time, I got the volunteers to replace my pinyin-name-card with a legitimate one that said “Brian” on it really quickly.

Unfortunately, after I talked to a few more people, it looks like they aren’t going to change my name in the database. So if anybody reading this chances to look at the IOI live ranking and is unable to find me, look for the first name “Po-En”.

Indexing debates are boring. Especially when you can just flagrantly disregard all concerns about memory safety (because C++ never had any in the first place) and write int _array[100008], array = _array + 2; I do this alarmingly often; hence, the title. Hashtag firstworldanarchists. Three ± 1 cheers for Haskell arrays.

Anyway. One of the disadvantages of entering an international competition as the home team is a lack of time to completely absorb the idea that what is about to happen is a Big Thing. There was lots of time before the other international competitions I went to to spend uncomfortably on airplanes trying to adjust for the timezone difference.

Not so for a competition in one’s own country. Right up to the night before entering the hotel that marks the beginning of everything, I’m still at home, furiously refreshing the AoPS IMO fora and Facebook for news (!!!), lazily solving trivial Codeforces Div II problems with pointless point-free Haskell one-liners, and blogging. (There’s more, but I kind of want it to be a surprise.)

Anyway, let’s set the rules. Well, there’s only one, honestly:

Late post. As usual.

It started with an online competition — write programs, solve problems, get points. I wouldn’t call the problems easy, but they weren’t hard either. So I solved all of them. To make it even less impressive, only about twenty people submitted anything at all.

But the result was just what it was: I ended up with a free ticket to PyCon APAC 2014.

I’d prefer a conference about a more functional programming language, but I’ll take what I get. Another adventure!