Changing of the guard

Curt and Mark were outside, walking around this morning. They heard a band playing, and they ran over to check it out. Following the band took them to the royal palace, where they witnessed the changing of the guards. It sounds like it was a fairly big ceremony.

(Mark says extra credit for students who respond to one of these blogs...)

Vasa Museum

One of the main attractions of Stockholm is the Vasa museum. It is to commemorate a ship which sunk about a mile into her maiden voyage. Basically, once a wind struck, she sank. However, the water was polluted enough that all the critters which typically eat away the ship were not able to survive. So the ship remained mostly intact underwater for 333 years. Once we had the technology, it was carefully excavated and is in quite good condition.
The museum was quite the place. It really is like traveling back in time -- you could see a ship that sailed over 300 years ago!

Pictures:
Top -- a model of the interior of the ship
Middle -- a model of the exterior of the ship
Bottom -- the actual ship

Competition reflections

Only four more days until the programming competition begins! The same event which has led to multiple articles in The Beacon, NWC's homepage, The Capital Democrat, and even a couple Sioux City papers. Also the same event which has been the subject of many conversations this semester.
At times I wish I would have prepared more. I didn't take nearly the time for this as I would with, say, an actuarial exam. For sure, I wasted time "procrastinating," which could have been used to work more problems. And this is a once-in-a-lifetime opportunity which I'll remember forever.
On the other hand, there will always be "the big thing" in my studying/career. Getting an FSA. Perhaps other exams (EA, CFA). Finishing "the big job." Getting the promotion. Demonstrating myself worthy of the promotion I received. All these will come, and all these will go. But they aren't what life's about.
Sure, I could have prepared more. And I really respect those who have done hundreds, even thousands, of problems. But I absolutely don't regret spending my time with friends and family. In fact, I would rather that procrastinating time have been spent with them.

But, it is always easy to look back and be self-critical. Now, it's time to take on the world!

Camera

So, I brought my camera and have taken many pictures in hopes some of them turn out well enough to post. Unfortunately, I forgot the connector cable. So there will be less pictures. Fortunately, Mark brought his cable, so he will be our official photographer!

Stockholm or Bust

We arrived in Stockholm this morning...barely. Our first flight was delayed, and we had to rush to catch the flight out of Newark just as it was boarding.

Stockholm! What a town of such beauty. In many ways, it is like a city in the U.S. -- rush hour traffic, many buildings, etc. It is also quite different though.
Since Pav's passing, I've been contemplating the legacy he shared with us. One of his distinctive mannerisms was intentionally not rushing through life, not being in a hurry. This relaxed attitude, a realization that life will go on without our being everywhere instantly, is manifest in Stockholm.
People are never in a hurry. Maybe not never -- I've seen 3 instances of people "hurrying." And one of those was a fire truck. Out of the thousands of interactions I have seen, from people driving, to walking down the street, to waiting in line, that frantic rushing just doesn't exist. If someone who wants to cross the street just misses the light, they will patiently wait for the next one. And it's not as though Swedes do not care about promptness; on the contrary, tardiness is a sign of disrespect for the other.
What a contrast from the rush we were in to catch our flight!

Almost time to leave!

Time has flown by so quickly. It is hard to believe that we will be leaving in just a few days.
We are mostly ready to go. Our primary goals from now until then are:
- finish other homework
- prepare team reference document (we can have a "reference document," which is basically a collection notes to use during the competition)
- practice, practice, practice
- listen to the rest of the (applicable) online MIT algorithms lectures
- logistics such as packing

Of course we really want to do well. However, we also are trying to be reasonable. Northwestern is an absolutely outstanding school. Unfortunately, many of its best characteristics(small, liberal arts, open to many) are the opposite of the ideal characteristics for preparing for this (many classes, tech, very high admissions standards).
I'm not blaming Northwestern by any means. I am so thankful for the college and would go to NWC all over again in a heartbeat. Rather, these characteristics of the institution are in many ways representative of ourselves. Because even among us, we have a broader scope than just computing. John is studying literature. Curt is majoring in math teaching. I'm an actuary. None of these will probably help us in the competition, but that is OK.
Also, we aren't exactly the favorites to win this. Looking at teams from our region in the past, they typically don't score at the top. And we are the 4th team out of 4 in the advancing group of our region.

Don't get me wrong, this is a really great team. In addition to a computer science major (which we all are getting), all of us are working towards a major or minor in the math department. Curt works hard and applies his keen mind to all of life. John is an expert in many technical aspects of computing. And my actuarial exams have to count for something, right?
That being said, we are thrilled to compete. Just being around 300 of the top young computer-minded minds in the world will be an experience. We don't have high expectations for ourselves, so every team we beat will be a thrill. Who knows, we just might finish in the top half and place.
Thank you all so much for supporting us. We are a few days away from one of the most memorable weeks of our lives.

UVa World Finals Warmup II

Yesterday we partook in the second part of the world finals warmup. Rather than a time-based recap, I'll do a question-based recap:
A, Convex Orthoganal Polygon -- this looks like quite an intimidating question. After playing around with it on paper for a bit, I realized that it wasn't as difficult as I originally thought. Given A0, An, and B0, we had to find n. (Not very descriptive, but I'm trying to be brief.) I thought it would be an O(An) at the minimum, but it turns out the problem can be solved in O(sqrt(B0)), which is quite fast. I coded it up and submitted it -- time limit exceeded (TLE). I made more optimizations and continued getting TLE. We never did solve the problem. After the competition finished, though John used an analyzer to look at the problem. It turns out the code to run this algorithm was taking almost no time. All the time was taken in reading the input and printing the output. So my code couldn't really have run much quicker -- it is just that there was such a massive amount of IO that Java was too slow with it.
B, Spanning Subtrees -- for this one, you have a graph of n nodes, and you must figure out the maximum # of ways they can be connected without any of the ways having the same vertex as each other. The number couln't be any bigger than n/2, and intuitively it seemed like n/2 would work, so we tried it. Success. Yay for reading the input and dividing by 2!
C, Optimal Segments -- this was fairly challenging and we couldn't figure out a trick to solve it other than brute-force (which would take far too long).
D, Triangle and Polynomial -- what was going on with this? We had no idea, and it looked fairly complicated even if we could figure out what the question was asking.
E, Masud Rana -- we actually forgot to print this one off. It is fairly challenging and we wouldn't have solved it in the amount of time of the competition. I'm still trying to find a solution, though.
F, Avoiding Overlaps -- Curt took this one. He did a good job with it. The jist with this is that you are given rectangles on a grid and you have to print them if they don't overlap with a pervious rectangle. He tried storing all the printed ones in a linked list, but that was too slow. So he changed it and just had a 2D array of bits representing the grid and toggled them when the rectangle was being printed. Sucess!
G, SMS for the blind -- is there any way to solve this other than brute force? And is there any way brute force could solve it within a reasonable time?
H, It's all about the bandwidth -- We need to practice some more on the maximum flow problems.
I, General Sultan -- this was a fairly complicated problem, which I didn't think was very solvable. John took it and made it into a Huffman-tree type problem (which I had a hunch would be part of the solution but had no idea how). He ended up not solving it in time because he had an error which would have required a significant re-write of his code.

Result:
2 officially (B & F), 1 unofficially (A -- I'm still quite unhappy that UVA had such a time constraint that I didn't have time for I/O.)