Monday, April 27, 2009

More pictures

Many of my pictures are uploaded onto Facebook.
If you don't have Facebook, let me know. Apparently there is something where one can share an album with non-Facebook members via an e-mail address. But that could just be a promo like: "create an account and you can see your friend's photos."

Tuesday, April 21, 2009

Competition, quick recap

We just have a few minutes break, so I'll try to recap quickly.
Our team went for a high-risk high-reward strategy. We looked at 4 problems, and tried to solve them all.
The problem with high risk strategies is that risk is a real issue (here's the actuary in me!). Sometimes risk is fine, sometimes it doesn't go so well.
That's what happened to us today. We submitted responses to 3 problems, and had a 4th one in the works. Unfortunately, we didn't get the right answer for any of them.
Two of them we ran out of time (i.e. our program took too long to compute the answer), and the third one had the wrong answers. If you have access to the problem set, here's how it went:
A -- many teams were getting this. I didn't think it was terribly easy, but I switched gears and tried to solve it. I got stuck and put it aside. Later, John tried his hand and couldn't get it.
B -- I spent most of my time on this one. I was matching the sample output, and there didn't seem to be any special cases for this one. However, I couldn't get a correct response.
? -- (The one with surrounding the trees by a fence.) Curt worked on this one. He had most of it worked out, but we ran out of typing-up time.
K -- John spent most of his time on this one. He had a good algorithm, but not many teams got this one correct at all. There was likely some really nasty judge data for this one.
We are trying to remain upbeat. It has been a good time, and we gave it our best efforts. If anyone wants to discuss these problems online (or in person), we would love to do so. Many of the other problems we had some idea on (I would have loved to try my hand at the house of cards game problem), but they didn't look as easy and we obviously struggled at the easier ones.
Thank you to everyone back home who stayed up to watch the broadcast. We really appreciate your support and are looking forward to seeing you soon!

Monday, April 20, 2009

Extra Credit Opportunity

Well, Mark has a couple ideas for extra credit:
1. Watch the competition online. Unfortunately, a professor broadcasting over the internet an encouragement to students to pull an all-nighter might be frowned upon in some societies. So, that wouldn't work.
2. Solve the last problem we did during the practice session. A summary of which follows. As with us, you aren't allowed to use online resources other than the Java API. (Though if you haven't had data structures, you might be allowed to look up more information on what a "tree" is.)
Ben's summary of the 4th problem during the practice session
A tree is a series of objects connected by lines. The objects are called nodes (or edges), and the lines are called vertices. You can think of this like cities (nodes) connected by roads (vertices). There is just one way to get from point A to point B (i.e. there are no cycles); in other words, if there is a road from A to B, there wouldn't be both roads from A to C and C to B. The roads go both ways (non-directed), so a road from A to B means there is a road from B to A.
You can break these trees up into subtrees. Each subtree is a tree. A tree (or subtree) can have only one node, but in this example, a tree (and subtree) cannot be empty (null). Here is an example:
Tree: Nodes: A, B, C; Vertices: A to B, B to C
Subtrees: A & B & C (A to B, B to C); A & B (A to B); B & C (B to C); A (no vertices); B (no vertices); C (no vertices)
A & C is not a subtree because there is no way to get from A to C without B.

Input:
You will be given a number "n" of nodes for a subtree. This will be followed by n-1 vertices, as per the sample input. The input will be terminated with n = 0. Do not process this case.
Nodes will be listed as numbers from 1 to n. Vertices will be two nodes, separated by a space, indicating a path between the two nodes.
(The sample input is the same case as explained in the above example.)

Output:
For each case, print the number of possible distinct subtrees possible from the given tree.

Sample Input:
3
1 2
2 3
0

Sample Output:
Case 1: 6

**The problem was of course was more detailed than this, and I apologize, especially for those of you new to trees. However, I need to get to bed at a decent schedule. Besides, this is extra credit for you (for us it was a practice to test the "system").
**For those of you not in CS courses (i.e. graduated), I'll send you a postcard or have something else for you if you solve this.
**Also, special extra bonus for those of you who can solve it in a more efficient algorithm than ours was (exponential time, for anyone who knows what that means).

It's almost here!

We are about ready to head out to the dinner event for tonight. In order to get a good night's sleep, this will probably be my last post before the competition. (Of course I'll keep you up to date should I find out more about the webcast.)
Overall, we are quite excited and ready to go. As Mike said, it's like an NCAA tournament and we are the mid-majors who nobody has heard about.
One fun aspect of the competition has to do with balloons. Whenever a problem is correctly solved, that team receives a balloon attached to their desk. (We are sitting directly opposite of a team from St. Petersburg who had the champion last year...)
Our (optimistic yet reasonable) goal is to solve 3-4 problems. That should hopefully place us (top 50 place), and possibly with 4 we could get top 30 or so.
Thank you for all your support!

Competition Watching

For all you interested in watching the competition...
Good news and bad news

BAD NEWS:
- I am unsure of the details
- I am just going by what they tell me
- The websites don't really seem to reflect anything about it at all
- The live TV broadcast sounds like it is just in Sweden
- Of course the time is bad.

GOOD NEWS:
- They are promising a live broadcast over the internet open to all
- They have installed webcams in all the desktops
- They have everything in place here
- It sounds like it should be fairly interesting

So, hopefully something will be set up. Here is how I envision it working:
- If you want to watch it, first kudos to you. You really are a trooper.
- There will be commentators talking about the competition. They will probably introduce what is going on, and maybe discuss the problems. After teams are starting to submit answers, they will discuss the answers. Perhaps mention what teams are doing well. Also, there will likely be many incorrect solutions, and they might comment on why the solutions are incorrect.
- As I mentioned, they have webcams so they can watch us while we work. They also have camera people walking around the room. Additionally, they are able to view our computer screens, so they can show you the screen.
- Probably towards the start most of the submissions will be by teams solving problems quite quickly
- Around half an hour or so is likely when more of the teams will be running their first submission
- The last hour or two will likely be focused around teams towards the top, as they are trying to figure out who wins

So hopefully it will be worth your while. As mentioned, I am unable to find a like right now. However, there are a couple of hopeful possibilities:
- ICPC website http://icpc.baylor.edu
- Specifically, their photo & video coverage http://icpc.baylor.edu/dmt/
- Another link which I stumbled upon which has potential http://130.237.8.165/

If any of you find something (probably it will be more likely as the time approaches), please comment on this post to share. Also, feel free to use this post as a 'chat' during the competition, if multiple people are watching it. Finally, if I learn any more tonight, I will share it by commenting here.

Practicing

We just returned from the practice competition. It was quite difficult. The first question took about a minute, then 2 more minutes for the 2nd question. It took us about 40 minutes to complete them all...
(questions are abbreviated)
Question 1: We like to talk to the world a lot. However, the world doesn't ever have an opportunity to respond. Now it is taking such an opportunity. There is no input. Output should read, "The world says hello."
Question 2: The quickest sorting algorithm ever. You are given a set of cases, starting with n. n numbers follow in ascending order. You must sort them in ascending order. Sample output:
Case 1: Sorting...done
Case 2: Sorting...done
Case 3: Sorting...done

The last couple were a bit more challenging. But obviously not too much. It was a fun time.

Sunday, April 19, 2009

Opening Ceremony

Picture yourself in the Stockholm town hall. (You must go through this mental excercise because unfortunately I do not have any real images for you.)
You probably haven't seen it before, but you very well might have. That is because it is the same town hall that is used for the Nobel prize awards. (Not exactly the same room, but that's for the awards ceremony...)
So, it's a pretty amazing place. They have a great symphony going, and all. And, this is the place chosen for the opening ceremony.
I don't remember all the teams announced in order, but let me recall the start of the list of American teams being announced, walking down the stairway with pictures being taken...
California Institute of Technology
Carnegie Mellon University
Cornell University
Duke University
Iowa State University
Massachusetts Institute of Technology
Northwestern College

Need I say any more? It was quite the experience.

Saturday, April 18, 2009

Opening Ceremony

We just returned from the opening ceremony. It was quite enjoyable. The first event was registration. They approved our binders (thanks Mike for putting those together), then we completed a checklist of paperwork (such as turning in photocopies of passports and student id's.
Following registration was a buffet-style meal. It was very nice. Many food items which I probably couldn't appreciate as fully as I did. (Not that it was bad, but I'm not food expert.) My favorites were avacado/artichoke/tomato spread on a cracker and pasta with alfredo-type sauce and something seafood for meat. The primary dessert was coffee-flavored, and even that was good. Not that the coffee part was good, but that it was good enough to make up for that.
During the latter part of the mealtime, there was a karaoke time, for people to sing various songs in front of everyone, with a slide show of pictures from the night in the background. (Mike even got his picture up there!) Songs were sung in Russian, Spanish, and English. Probably my favorite was a beautiful rendition of Beauty and the Beast.
Overall it has been another great day. I even have been able to meet some people from all over -- Lincoln NE (UNL), Kazakstan (with Purdue University), Bangalore (North South University).
From a reputable source, the contestant officials want to make the ending a suspense. They don't post results with an hour to go, so there will be some suspense. Apparently, they sometimes go to the extent of not notifying you of passing a question (though they still notify of failures).

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

Friday, April 17, 2009

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!

Tuesday, April 14, 2009

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.

Monday, April 6, 2009

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.)