Codejamming

I tried the Codejam Qualification Round a few days ago, and it feels pretty hard for my level. I managed to score 55/75, and the 20 points lost was because of a tiny error in my program for question C (at least that's what I believe should be the problem; I tried the new, fixed program on a test data and this time it worked).

If you want to see the questions, please go to Google Codejam. I can offer the solution for any readers (see note at the very bottom).

A. Saving the Universe
This one should've been really easy, but unfortunately I screwed a lot things up, and ended up submitted several incorrect entries before getting the right answer.

Here's how I solved this problem:
Go through every query, from beginning to end, and make the best switch that minimizes the total number of switches. Make sure a counter is used to keep track of how many switches are made.

The real question here is: what constitutes a "best switch"? Well, after some thought, I realized that the best switch was the switch that maximizes the number of queries processed before changing to another search engine. So all I had to do was to try switching to each search engine and check how many queries it can process before it has to switch to another search engine. That was easy: just a simple maximization problem.

B.  Train Timetable
While this is supposed to be a fairly easy problem, my solution kinda overcomplicated things, and it took me a whole day to figure out where the "bug" was.

Before I go onto the solution, I would like to note that a simple way to incorporate the "turnaround time", T, into the solution is to just assume that each train arrives T minutes later than what the schedule says (or equivalently, each train needs to depart T minutes earlier than what the schedule says).

My solution was to simply simulate all the trains as they go from station A & B and back. At every critical moment in time (explained later), the total number of trains that leave a station is counted. If somehow, the number of trains left at some station X is negative, then that means there's a deficiency in the number of trains. This deficiency is then added to the "required number of trains at station X" (this is what the whole question is asking for!) and the number of trains left at the station X is reset to zero. At the end of the day (when all the critical moments are processed/simulated), the "required number of trains at station X" is then output.

Note that I use the term "critical" to differentiate between moments of time that are uninteresting (e.g. when a train is mid-way/at a station, and nothing is happening) and those that are worthwhile to process (e.g. when a train departs or arrives). The simulator only needs to simulate critical moments in time.

C. Fly Swatter
This one was actually fairly easy, until I realized that I forgot to make a certain check to process the area. Okay, first things first.

This question simply asks you to find the ratio of the fly swatter area to a circular area of radius R... Oh wait, no: it says the fly is a sphere (of radius f), not a point! This might make things confusing. Since the fly is a sphere and not a point, it actually makes the fly easier to hit.

After some thought, I realized that an equivalent situation is when the area of the fly swatter has been extended by a distance of f, yet the fly is point-sized (positioned at the center of the spherical fly).

Now finding the fly swatter area is not easy. Instead of finding the area that is covered by the fly swatter, I decided to find the area of the holes in the fly swatter (which are either just squares or squares that are cut by circular arcs).

The side-length of each square is nearly the same side-length as the ones drawn in the Google Codejam diagram, but it must be subtracted by 2f. In order to find the areas of the squares that aren't perfect squares but cut by circular arcs (I call them "pseudo-squares"), you should set up a coordinate system and use integration. Now don't just do numeric integration (it'll take forever to get 6 decimal places), because an integral like:

can actually be simplified so that it's in terms of square roots and arcsines, which is less computationally intensive. In order to simplify calculations, don't bother calculating the area of the squares of the other quadrants of the fly swatter, since one quadrant is enough (it is symmetric, as the question states). Beware of cases when the width or height of the squares (or "pseudo-squares") is negative, which is often as a result of subtracting the actual height or width of the squares (or "pseudo-squares") by 2f. In such a case, make sure you check for this situation, and treat the square's area as zero.

After that, the rest is pure logic and iteration. Just be careful with the signs and how you get all those coordinates, and the rest should be pretty easy.

Feel free to ask me to email a copy of my code (in Python) for any of these 3 questions. (The code for question C has been corrected already, by the way.) I'm fairly confident that they are correct, but you can verify them with the Google Codejam Qualification Round practice questions just to be sure. You can put requests in the comments.