Day 1: The beginning

27.7.15: Practice session and opening ceremony

We wake up early in the morning to realize that we have over an hour before our guide comes to pick us up for breakfast. While trying to contact Allan, we engage in various activities, some of which involved the playground:

IMG_7044

Breakfast involved some excellent milk, cakes and pastries. After that, we walked to the eventual contest hall, the Al-Farabi library, for the practice session. While playing cards, I inform the team about the IOI push-up challenge: pick a constant c, and for every point you fail to get at the IOI, you have to do c push-ups. I pick c = 0.2.

IMG_7049

At the contest hall, we settle into our seats and take a look around. To our left sits Macau, to our right, Moldova, and others in the vicinity include France and Germany. The screen was locked on a cover page showing our details.

IMG_7050

Someone in the contest hall counts down the seconds to the start of the practice session, and I get a glimpse of the tension that would be present tomorrow during Day 1. For now, I test out the keyboard, mouse and configure my system. I decide that the laptop keyboard is better, and I unplug the external one. The mouse works reasonably, so I won’t have to use my own. Then, I pull up Terminal and gEdit, and start to code out solutions to the practice tasks.

Although I had some time to think about them on the plane, I still only had partial solutions to divide and graph for 50 points each. Search was just trivial binary search. I code out all 3 solutions and submit, and they perform as expected. A small commotion at the entrance distracts me, and I notice that the leaders have arrived. Shien Jin and Mark come to my station a while later to make sure that my system is working fine.

IMG_7053

After they leave, I suddenly solve Graph. It was pretty simple after all: run a BFS initially to find a path P from S to T. Then run a DFS from each vertex in P in turn to record, for each node v, the first vertex u in P such that there is a path from u to v. Then flip P working backwards, keeping a count of the first vertex of P that reaches each vertex of P, which is sufficient to find all points that disconnects S and T.

After the practice session, we head for lunch, then to the opening ceremony at the Palace of Students. This was the first time I had ever arrived early to an opening ceremony: so early, in fact, that we were waved away by a petulant man at the entrance, so we seek shelter under some trees to wait. This was the venue:

IMG_7058

The opening ceremony was, in my opinion, bizarre. The performances were strange, including one where two dancers accompanied a man carrying just an unplugged guitar, synced to electronic music. Unlike the IMO, the IOI opening ceremonies just have the teams stand up in the hall instead of parading on the stage, which made for a speedy ceremony. It ended with the raising of the IOI flag, which failed on its first attempt. It was eventually raised, and the ceremony pronounced over.

IMG_7071

Outside the hall, we started playing cards. A few Kazakh locals approached us and asked us where we were from, showed us a card trick, and then taught us how to play Durak (‘idiot’ in Russian), a card game widely played in Kazakhstan. Because they weren’t very proficient in English, this took some time, but we eventually got it. We would then play lots of this game over the week.

We then headed to an early dinner, before going back to the hostel for quarantine. This was when the leaders and deputies were translating the tasks for Contest Day 1 tomorrow, so wi-fi access was cut off on our side. We played cards and chatted, and went to bed at 10, all a little nervous for the contest the next day.

Posted in IOI 2015 | Tagged , | Leave a comment

Day 0: Departures and arrivals

26.7.15: Flight to Almaty

At 3am, I dragged myself out of bed, gathered the final remaining things scattered around my room (toothbrush, retainer, laptop, phone, chargers), checked that my passport and wallet were with me, and set off for KLIA at 4am. Despite having to work at 9am, my father drove me straight to the airport, a 2.5 hours drive either way, while I slept snugly in the passenger seat.

I arrived at the airport, texted the group, and found out that Jen Khai was already there. I met up with him at a gate nearby, and said goodbye to my father. After a brief conversation, I suddenly remembered that I hadn’t yet had breakfast, so we head off to McDonald’s for a bite. After I get my food, Chris and Jia Jen arrive, and the team was thus assembled!

At 8am we meet up with Shien Jin and head to the counter for check-in. To our surprise, it was still not open, even though the flight was schedule to depart at 10:55 and it was already less than 3 hours before that happened. After some jokes about how this would be a precursor for Kazakhstan, we went to a dim sum place nearby for breakfast with Shien Jin’s parents, where the four of us spent the next hour trying to convince them that we’d already had breakfast and wouldn’t need much more food.

At 9am, we meet Mark and try the check-in counter again, and get our boarding passes. We were extremely disappointed that we didn’t get adjacent seats. :(

IMG_7011

At the security checkpoint we took a group photo.

IMG_7013

We made our way to the gate and note that the plane was pretty small.

IMG_7014

Half an hour into the flight, Jen Khai comes over and tells me that there’s a vacant seat next to him, after which I promptly move. The flight to Almaty from Kuala Lumpur took 8 hours, but since it was a daytime flight, we didn’t get much sleep. Instead, we worked on the IOI practice tasks (divide and graph), discussed some IOI problems from 2014, watched a Russian movie, and looked at the pretty terrain as we flew past them.

IMG_7021

When we arrived, we breezed through customs because Malaysia was (surprisingly) one of just ten countries for which a travel visa was waived! At the baggage carousel, we saw some other teams, but only knew the Singaporeans. Outside, we met a few other teams, Taiwan and Hong Kong, while waiting for the bus to depart.

Upon arrival at Al-Farabi Kazakh National University, our host for the week, we were very impressed by the playground facing the dormitories. Apparently, see-saws and slides are of some use to university students. We checked into our rooms, and then headed off for dinner. Here’s a view from our room:

IMG_7028

Here was our first taste of Kazakh food. We had an interesting dinner trying to figure out what we were putting in our mouths, because this was also when we realized that there was a pretty substantial language barrier between us and the food servers. For instance, we didn’t know whether the meatloaf thing was chicken, beef, or…horsemeat? In any case, the food was better than I expected, and the same was true for the rest of the meals throughout the week. It was good.

IMG_7032

During dinner, we were asked by multiple people about our guide, which we hadn’t met yet. This spurred a few industrious, official-looking people to go around trying to get us a guide, while trying to tell us to stay in the dining hall, which wasn’t a problem since we were still eating. After a while, we meet Allan, our guide for the week. Allan asks us if we want to go and dance, but we decide to return to our rooms. We then register and get our goodies:

IMG_7035

When we first saw our rooms in the afternoon, we lamented the lack of air-conditioning and fans, but thought it would be OK because the weather was supposedly very cold at night. As it turns out, 20+ degrees Celcius isn’t actually very cold, and we go to bed in shorts and tees, sweating a little as our first day in Almaty drew to a close.

Posted in IOI 2015 | Tagged , | Leave a comment

Off to Kazakhstan

Tomorrow morning, I’m headed to the city of Almaty, Kazakhstan to represent Malaysia at the 2015 International Olympiad in Informatics. An 8-hour flight away from Kuala Lumpur, I’m relieved that the journey won’t be as taxing as those to all of the IMOs in the past 4 years. The time difference between the two countries is just -2 hours, at GMT+6.

The IOI program in Malaysia is still in its early years, pioneered by Dr Ong (our team leader) and Mr Suhaimi. Thus, training for the IOI is still independent and less structured, although we managed to set up a Mock IOI in KL last weekend. Here’s a group picture after the session:

Team Malaysia at the IOI 2015. From left: Kai Hsien (Chris), Jia Jen, Jen Khai, me, and Dr Ong Shien Jin.

Team Malaysia to the IOI 2015. From left: Kai Hsien (Chris), Jia Jen, Jen Khai, me, and Dr Ong Shien Jin.

I’m optimistic about the future of the IMO and IOI programs here, and I’ll definitely remain active in these programs in the future – no longer as a contestant, but I’m sure there will be some role I can play.

Packing my luggage in my room, I keep stumbling upon remnants of all the math and programming competitions I’ve been to all these years. I re-read my IMO scripts, went through the souvenirs we exchanged with other teams, looked through my old math notes…I even found a whole stack of scratch paper I used while preparing for the IMO in 2012. It has been a great privilege!

And it is with this feeling that I embark upon my last Olympiad as a contestant. Next year, I will be twenty and no longer eligible. Fingers nimble, mind sharp, and ready to have fun: let’s go to Kazakhstan!

(I will try to write in this space as the week progresses!)

Posted in IOI 2015 | Tagged , , | Leave a comment

(Kafka) on the Shore

If you remember me, then I don’t care if everyone else forgets.

I recently read Murakami’s Kafka on the Shore. I followed the precocious Kafka Tamura and his alter ego as he navigated life through the lens of a fifteen-year-old, running away from home only to have this distorted reality bring it along with him. Split into odd/even chapters, we also meet cat whisperer Nakata, dumb and useless, swept by the undercurrents of the same reality that he doesn’t yet understand.

Reading it gave me the reminiscent feeling I got when I first read Franz Kafka’s Metamorphosis. I remember first feeling bewildered as I read the final sentences of what still is a hallucinatory and creepy tale. I’m not sure what Kafka intended to convey through Gregor’s transformation and his eventual struggles, but it is evident from the first sentence (“he woke up and…found himself transformed into a horrible vermin”) and Gregor’s immediate acceptance of his fate that the story takes place in a different reality from the one we live in. The unsettling part of the tale lies in the otherwise utterly normal setting of the story: nothing else seems to be out of place.

Similarly, Murakami’s stories (though I have only read one other work of his, 1Q84) seem to take place in the regular world, but sparsely littered with unusual happenings. Nakata goes searching for a cat and ends up in a house with a man called Johnnie Walker, who eats hearts and forces Nakata to kill him. Fish and leeches rain from the sky. Kafka’s metaphysical romance with Miss Saeki. Perhaps it was the pace at which Murakami sets these events apart, but I found it difficult to constantly remind myself that Kafka’s world is different from ours.

For this reason, Kafka on the Shore was incredibly engaging for me. I’m not sure exactly why, but as we grow up, we seem to lose some of our ability to ask fundamental questions about the world we live in. Growing up, I loved Enid Blyton’s illogical realms of magic, talking trees, and other shenanigans precisely because so many of them stem from taking a normal property of the normal world and asking, “what if it wasn’t so?” I still remember such tales as the topsy-turvy town, the flying cottage, among others. Back then, it was so easy and delightful to accept the existence of such places, but now, I’m not sure if my imagination would still be as permissive to lead me to believe in such tales.

Although we still continue to enjoy stories about the Avengers, Thor, and the rest of the superheroes, do we still believe in them? I’m not sure. When I watch a movie and notice an illogical twist, I’m not sure if I can still believe it once it registers in my mind. Still, it feels that Murakami’s whimsical universe is more of a challenge than these usual tales of superhuman strength and wisdom. I constantly kept asking, “Colonel Sanders? Johnnie Walker? What?” Nakata’s conversations with cats are also strangely civil, seemingly taking place without them realizing the strangeness of it all.

Yet as the book progressed, I gradually eased into the psyche of this peculiar world. Our wide array of characters each have their own troubles: Kafka’s physical and psychological attempt to escape a prophecy he already believes is true, Miss Saeki’s disconnected existence after the pain of losing her only love, even Nakata’s innocence as he leads his life led by something he doesn’t yet know, “but will know when he sees it”. Without much fanfare, there is this huge undercurrent pushing the story along that lends a sense of urgency to their adventures – even when Kafka spends an entire week alone in the forest.

Miss Saeki’s request for Nakata to burn her memoirs draws the tale to an end, and she dies knowing that her memories are safe with Kafka. At the end of the book, I felt like I’ve been on a journey and that I now understood something. I don’t know exactly where I’ve been to and what I know now. Yet perhaps this isn’t very different from what I felt from all those tales of fantasy I read as a kid. What did I learn from them, other than to question and accept?

Posted in Writing | Leave a comment

The time I accidentally wrote the official solution

(Copied from Facebook. Remembered this fun story while taking a break from the past paper madness…)

In IMO final training last year we worked on this geometry problem, which seemed strangely familiar. After I found the solution I remembered that I’d solved it before on AoPS – Turkey’s problem 6 from 2012.

We then read the official solution from the booklet – hey, I used the same method! They even used Brokard’s theorem like I did. Wait…

Turns out, they printed the exact solution I posted on AoPS two years ago. :P

http://artofproblemsolving.com/community/c6h508906

I like this problem – the idea is similar to the geometry problem I wrote for the Junior Olympiad in 2013. Here it is, Turkey NMO 2012, Problem 6:

Let $B$ and $D$ be points on segments $[AE]$ and $[AF]$ respectively. Excircles of triangles $ABF$ and $ADE$ touching sides $BF$ and$DE$ is the same, and its center is $I$. $BF$ and $DE$ intersects at $C$. Let $P_1, P_2, P_3, P_4, Q_1, Q_2, Q_3, Q_4$ be the circumcenters of triangles $IAB, IBC, ICD, IDA, IAE, IEC, ICF, IFA$ respectively.

a) Show that points $P_1, P_2, P_3, P_4$ concylic and points $Q_1, Q_2, Q_3, Q_4$ concylic.
b) Denote centers of these circles as $O_1$ and $O_2$. Prove that $O_1, O_2$ and $I$ are collinear.

Posted in Stories | Tagged , | Leave a comment

Into the (slow-burning) fire

The next month promises to be an electrifying one. We’re on the brink of the most important exams of the year, and the atmosphere here in college is somewhat strung – gone are the days where people could (or wanted to) hide behind a veneer of nonchalance, it’s the A levels, darn it!

Exams have already begun, with our pioneers taking the first of the papers today (7 brave students daring the waters of Marine Science). For the rest of us, we’re waiting for the papers with the sort of anticipation one gets while waiting for trains in KL during rush hour – we know it’s going to be uncomfortable, but let’s just get it over with, shall we? My calendar is littered with scribbles about exam papers, most of them uncomfortably squeezed into the first few weeks of this hectic time of the year. Life for most of us nowadays revolves around (boring) past year papers, (re-)reading textbooks and notes, and at least for me, surprise existential crises (wait, what am I even doing in class?).

while (1) {
    c++;
}

I recently thought of stuff related to stress and sanity while writing code, and the phrase ‘code sanity’ floated across my imagination (metaphorically). I can see it on a motivational poster on some hacker’s dingy basement wall as the green-lit background on his text editor illuminates the freckles (probably acne) on his face. Code with sanity, perhaps – don’t go around getting the poor executable stuck on some infinite while loop or access memory out of bounds (shame).

Alternatively, it could be a way of saying that you’re so burnt out that you can only think logically in code, for instance, oh I don’t know, after staying up for 3 hours past midnight doing a programming competition on a school night. Yep, that happened this week. I wonder why I’m still on the laptop now typing this instead of clawing my skin out with shame and repent for the time I spent not studying.

Still, this particular round was quite a good one. It was Codeforces’ special round #300, because we like trailing zeroes in numbers. I ranked 336, made it to Master, and went to bed.

cf rank 1

Considering that I’m not participating in many math competitions this year, I’ve been doing lots more coding instead. It’s replacing the void left in my mind whenever I stop thinking about math and realize how boring the real world is. (I’m just kidding.) Code is much more petty and messy than math, because one bug, one misplaced letter can kill a program. When I started off coding in Form 4, I was put off when I searched 3 hours for this bug between about a hundred lines of C++:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; i++) {
        //magic
    }
}

But as you go along, you realize how important it truly is. You can’t tell a computer to do something if you enter the wrong keys. You can’t tell a compiler what to compile if you don’t declare <algorithm> before using min. You can’t tell me what to do if you don’t feed me good food. Then you join competitions and look at people like Petr blazing through 6 questions in this exact same round (#300) within half an hour – he did it without making a single bug, accepted on first attempt.

Coding is an art. You’re a mastermind controlling bits on a machine that is astoundingly dumb, and your job is to transfer your eternal wisdom onto it. No, the machine won’t know that you intended to type j instead of i in the code above. It won’t know that the segment tree you actually wanted to implement had size 4n instead of n (seriously, declare your trees with 4n nodes). It can catch little errors though, like when you stupidly declare a priority_queue and call .front() on it. Not much else.

error: 'cout' was not declared in this scope
error: 'class std::priority_queue' has no member named 'front'

Then I learned more about coding. I learned graph algorithms like DFS and BFS, and learned how to implement them quickly and free of bugs. After that, I learned about Dijkstra, Bellman-Ford, and various ways to walk on a graph. You also get to learn that strings can be turned into trees and you can fill tables from the bottom up or from top down. You start associating the name Graham with the convex hull algorithm instead of the crackers.

And then you start doing competitions, and you feel good when you write something like this in just a few minutes and know exactly how it’s going to work. It feels really good when you code without pausing, though perhaps only because I’m picturing how cool it must look on the outside.

if (tp) {
	if (h[u]%2) {
		if (adj[u].size() == 0) ans = 1;
		else {
			ans = MX;
			for (int i = 0; i < adj[u].size(); i++) {
				int v = adj[u][i];
				ans = min(ans, sz[v]-go(1, v));
			}
			ans = sz[u] - ans;
		}
	}
	else {
		for (int i = 0; i < adj[u].size(); i++) {
			int v = adj[u][i];
			ans += go(1, v)-1;
		}
		ans++;
	}
}

(This is an excerpt from the DP portion of the code I submitted for E in the Codeforces round above, full code here. I liked this problem.)

After a few years of coding, I’m pretty used to bugs and consider it part of the experience. Once you accept that yes, you might spend hours looking for silly bugs, you can start appreciating the hard problems. I recently spent a few hours implementing a (sadly doomed) O(N^2) solution for a problem before I decided to read the editorial – and found out that there was a pretty simple solution in O(n\log n) (using line sweeps, if anyone’s interested). This line sweep idea (but actually with some additional data structures) seems so simple, but it makes the difference between linear and logarithmic time. The difference is huge, just in case you’re not familiar.

I’m actually surprised that the little counter under the text box here is showing that I’m approaching 1000 words. I’m not sure why I started writing this in the first place. Next Saturday, I’m heading down to KL to participate in the 2015 APIO, and then return to this jungle of a college to continue my trudge through AS levels.

I guess if there was a point to this post, it would be this: writing code is keeping me challenged now, and I think I wouldn’t be able to function properly if I wasn’t. And now it feels appropriate and edgy to end this post with the quintessential example of basic programming:

int main() {
    cout << "Hello World!" << endl;
    return 0;
}
Posted in Writing | Tagged | Leave a comment

Halfway through, April

It’s halfway through April, I have 13 papers impending in the AS examinations next month and a couple of other exams to prepare for – it would seem that I should be, at least, slightly stressed out at the thought of the next two months. But strangely I’m feeling pretty good! Some interesting things this month:

1. UKM MEDebate 2015

We went to another debate tournament! Because it was the weekend right after our trial exams ended, the three of us headed to UKM to debate, unprepared, nervous and more than a little worried that we’d crash and burn miserably. It was a varsity tournament, for god’s sake, and we were the only A level team there. The tournament was themed ‘Medical Ethics’, something that unfortunately none of us knew much about, so we researched as much as we could the day before – reading up on the Hippocratic Oath, the vaccination controversy, issues about genetics and GMOs, etc – and hoped that our wit and whatever knowledge we had would pull us through.

We did our best anyway! We debated three preliminary rounds and won just one of them. We did, however, lose very narrowly to the eventual champions, so we felt slightly better about the result. Despite being the youngest team there (and probably the most inexperienced), we still ranked 5th on total speaks, and I finished at 12th on the speaker ranks!

KYUEM at UKM MEDebate 2015

KYUEM at UKM MEDebate 2015

Something I’ve noticed through debate is how persuasive speech can be – seven minutes of speech about an issue can be incredibly powerful. So whenever I go into a debate, I speak, keeping in mind that my opponents wield a huge amount of power when I hand over the floor. Conversely, I also recognize the fact that by speaking, I am also in a powerful position to repair and strengthen our case, to rebut every valid point the opposition has raised and turn the tides back in our favor.

It’s a far cry from math and code, where logic is definitive and words exact – logic here is infallible and binary. In language, it’s very hard to make general statements that are correct. It’s not true to say that “personal autonomy is the most important right”, because when your civil liberties trespass on other citizen’s rights, one might argue that one loses his/her autonomy there and then. But even here it’s subject to interpretation – why then do we allow people to smoke? Then we have to back up and fix the hole there.

This realm of debate is a much messier world, where words can be twisted, meaning warped, and logic bent. Still, I’m proud that I’m progressing and becoming more eloquent with speech. Words come more freely to my tongue now, and I’m looking forward to more next semester!

2. Code, code and more code

Despite trials taking up the bulk of last month, I found myself doing more and more coding as trials grew nearer. I did the Croatian Open the weekend before trials, and did two rounds of US Open the weekend between trials. These took up 13 hours in total, and I spent more time figuring out the problems I didn’t manage to solve during the contests. I got a perfect score on US Open silver:

usopen2015_silver2

usopen2015_silver

Full results here

The Silver problems this year frankly weren’t that hard. I still made a few mistakes – for P1 I initially thought that I could count the permutations for each word separately and multiply, and foolishly started to code it out before realizing the obvious flaw halfway through. P2 was pretty nice in my opinion, but quite easily solved once you saw that you could iterate over each bale and find the extreme at the other end in O(n) in one sweep. For P3, once you figure out that you could run BFS on each vertex to find the minimum distances, then a further O(n^2) DP finishes it off.  Promoted to Gold!

I also did SRM 655 and finished 3rd on Division 2. I then proceeded to do quite badly on SRM 656 and a CF round two days ago. While I’m looking forward to more rounds, I’m also reading algorithms and data structures – balanced binary trees, maximum flow, and a seemingly infinite number of other paradigms. I’m just excited that there’s still a lot more for me to discover.

//////

Classes were suspended (temporarily, sadly) during the two weeks of trials, and all of a sudden I remembered why I loved having time to myself in high school. I spent so much time doing things that were simply interesting to me, and I loved having the liberty and free time to pursue whatever I wanted. During trials, I became that self again – I coded a little, read algorithms, read math, listened to music, and then I studied. I was happy again! And this is how the rest of the year is going to be – let’s do some great things.

Posted in Updates | Tagged , | Leave a comment