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.

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

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

Sample Input:
1 2
2 3

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

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

- 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
- Specifically, their photo & video coverage
- Another link which I stumbled upon which has potential

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.


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.