Our plan going into the world finals was to slow down for the first hour so that we would tackle the correct problems in the problem set. We had not done that well at problem selection on the last couple of practices. The goal was to get 5 problems (the best CMU has ever done is 4), but I thought we were capable of 6 on a very good day.
We started out as we always do, Celestine (the fastest coder) reading A-C, I get D and every other after it (D,F,H,J) and Alan gets E and every other. Celestine recognized that A was pretty trivial very early on. He talked it over with me and we came up with the algorithm which he coded and got correct on the first submission. Already we had started out better than at regionals.
From there we didn't have an immediate next problem. I started working on F, and eventually got a rather crude algorithm for it. I talked it over with Celestine and he started to code it. After a few minutes he noticed a cool property that allowed the code to be significantly simpler (basically taking all the computational geometry except convex hull out of the problem). While he coded that up I talked over B with Alan, and started coding it out on paper.
Celestine got F correct, so I hopped on the terminal to type up B. Alan was working on E on paper while Celestine scavenged for another problem. My first two attempts at B were incorrect, but after some help debugging from Celestine we found the bugs (not implementation problems but a small misunderstanding of the problem). We finally got B done and Celestine went to code up I. I talked over E with Alan and we got an algorithm working that we thought was correct.
Celestine turned in I and got it wrong the first time. We found a small typo resubmitted and got it wrong again. We fixed another few bugs over the next hour or so, but we still didn't have it correct. Alan started typing up E while we finished up I. Celestine was still debugging I, when Alan turned it in and got it back wrong. I looked over it with him, and after a few minutes we were both confident in the implementation. It took a few more minutes before I found the counterexample. We quickly found a fix that would still reuse most of the old code. In the meantime I told Celestine to go from int to double math and to do another stupid fix just in the off chance one of those is our bug. We ended up having integer overflow so that fixed I. Alan quickly fixed E and we were finished with 5 before the scoreboard was frozen.
From there we went looking for more problems. Alan recognized that H is basically the 2-sat algorithm. He coded that while I watched, in the meantime Celestine looked at the other problems trying to find the next easiest one. Alan quickly finished H (whenever we pair program the debug time seems to be nearly instant) and got it right. We were a little worried about some parts of the algorithm, but I think that if I had more of a grasp as to why 2-sat works, not just the algorithm it would be easy to show that ours is correct.
At that point we had 6 problems left with about 35 minutes on the clock. We selected D as the next easiest problem, but despite our best attempts we didn't get too far on it. I think at the end we had some good ideas on how to solve it, but we were probably 30 minutes to an hour away from getting it.
With the contest over we milled about waiting for the results. It was really nerve wracking for us, we were in roughly 16th place when the scoreboard froze without a very good time penalty. We knew we had a shot at a medal, but it didn't seem like a good shot at the time. Eventually the scoreboard went final and our tiebreaker was good enough to put us ahead of most of the teams with 6 problems solved and in 12th place for a bronze medal.
Saturday, April 25, 2009
Monday, April 20, 2009
ACM World Finals Days 1 and 2
We arrived in Stockholm on Saturday, and went straight to the Grand Hotel where we stayed. Despite the jet lagged we managed to get out and see the Nobel (prize) museum which was very interesting. The day ended uneventfully with registration and some food in the hotel.
Sunday started very early with a trip to Vaxholm's fortress at 7:45am.We arrived to see a castle on an island which looked very interesting. If you did not know, Stockholm is on an archipelago.
I was fully expecting a tour of the castle, but instead we were shuffled into an auditorium. We got to listen to IBM talk to us about how they are making the world smarter and saving the world. I guess if you pay for everything you get to
give the group a presentation. The presentation was down right terrible. The lecture was a high level view of a bunch of projects that IBM are involved with that are helping save the world. The audience is a bunch of incredibly smart, and very technical people. Tell us about the interesting technical details. One of our coaches remarked is that a good measure of how smart you are is how fast you fell asleep at the lecture.From there we were divided into groups to do a scavenger hunt. My first thought were math and logic puzzles. It ended up being a bunch of team building type exercises. Games where you have to work together to do something. For example the game pictured on the right. Everyone holds a rope to help control where the ball goes.
You need to drop the ball into the cylinders and based on which lights turn on you determine the order of the cylinders. Then you drop the ball into the cylinders in that order for bonus points.Celestine's team ended up winning the scavenger hunt and winning some well deserved viking hats. We returned to the hotel for a few hours before taking a short walking tour of Stockholm on the way to city hall for the opening ceremony. The opening ceremony recognized a number of volunteers who make this event happen. It must take an immense amount of time to coordinate an event of this side. Just helping make the problem set for our local contest took quite a bit of my time.
The rescheduled TopCoder SRM was during the opening ceremony so ACRush and all the other great TopCoders here missed it. That probably made it a much easier contest than a normal SRM.
In general the first few days were interesting, but a lot of waiting around. I'm really ready to go and start the contest. I'm doing being nervous, lets just get on with it.
Monday, April 13, 2009
Pretty Bad Practice
Today we had another practice (with Purdue and Duke), we got 3rd getting only one problem. Purdue and Duke both managed to get two. I think we did poorly versus what we could have done on the problem set.
Alan dove into a simulation problem that he probably should have planned on paper more. That basically took his entire five hours. Celestine and I worked together on H and got it. On D I thought I had it but didn't manage to solve it. We didn't put much work into problems we could have gotten, and a lot into problems we didn't have a chance on.
I think that this is a good time to have this learning experience for us. Going into world finals we can't change which problems we will be able to solve and how long it will take us to solve them, but we can change how we play the game. I think that we will go in with a focus on playing the game correctly.
This also really helps because we know what it is like to get our asses kicked by a problem set. We aren't going to just get frustrated by how many other teams are solving.
I am still worried about what sort of mind set I will be in during the actual contest. I think the key is really in the first 30-45 minutes. We need to get started with the correct problems in the correct direction. The first problem we start on needs to be the easy problem, and we need to knock it down. In soccer it is always important for the goal keeper to get a good touch on the ball early in the game, we need the exact same thing.
The one thing we can't really simulate is the intensity at an actual competition. You really want to go full steam ahead, but we need to slow down and get things right. It isn't about saving 5 minutes of console time here and there. Our one and only goal should be to not make the huge mistakes, like miss reading problems, trying a hard problem, or jumping into a simulation too early.
I'm ready to be in Stockholm and not have to worry about any of my homework for a few days. CMU is great, but the workload coupled with lots of 5+ hours practices is really draining.
Alan dove into a simulation problem that he probably should have planned on paper more. That basically took his entire five hours. Celestine and I worked together on H and got it. On D I thought I had it but didn't manage to solve it. We didn't put much work into problems we could have gotten, and a lot into problems we didn't have a chance on.
I think that this is a good time to have this learning experience for us. Going into world finals we can't change which problems we will be able to solve and how long it will take us to solve them, but we can change how we play the game. I think that we will go in with a focus on playing the game correctly.
This also really helps because we know what it is like to get our asses kicked by a problem set. We aren't going to just get frustrated by how many other teams are solving.
I am still worried about what sort of mind set I will be in during the actual contest. I think the key is really in the first 30-45 minutes. We need to get started with the correct problems in the correct direction. The first problem we start on needs to be the easy problem, and we need to knock it down. In soccer it is always important for the goal keeper to get a good touch on the ball early in the game, we need the exact same thing.
The one thing we can't really simulate is the intensity at an actual competition. You really want to go full steam ahead, but we need to slow down and get things right. It isn't about saving 5 minutes of console time here and there. Our one and only goal should be to not make the huge mistakes, like miss reading problems, trying a hard problem, or jumping into a simulation too early.
I'm ready to be in Stockholm and not have to worry about any of my homework for a few days. CMU is great, but the workload coupled with lots of 5+ hours practices is really draining.
Sunday, April 12, 2009
Simulation Problems
Recently when we designed the problem set for the CMU Spring Invitational the topic of simulation problems came up. We had 10 problems, and not a single one was a simulation. It took us about 45 seconds to dismiss the concept of a simulation problem. Our team and coaches are all fervently against simulation problems.
The reason is really quite simple, simulation problems aren't interesting problems. They don't require any insight to solve them. All that is required is to accurately translate a set of (usually very complex) rules into code. The solutions tend to not be elegant. The console time needed to solve them is terrible. They are usually very long, and have enough special cases to force more than a couple of resubmissions.
While I think a majority of people will agree that simulation problems are not very interesting, we still have to deal with them. My view has shifted recently, I think that simulation problems are interesting because they are problems from world finals or regionals. We are going to have to compete with this problems, so we need to get better at them. Which of course begs the question, how can you get better at simulation problems?
I have yet to really try and get better at these, but that won't stop me from throwing around a few ideas. I think that solving a bunch of simulation problems will help, but not that much. Simulation problems are rarely similar to other problems, so solving one won't really help you in another one down the road.
Alan came up with, what I think is, a much better way to practice these problems. Assign one problem to your team/coaches every week. Everyone individually solves the problem (while attempting to still write code on paper and minimize console time), then everyone gets together and talks about how the implemented in and what cool tricks they used, and what tripped them up.
For these types of problems we don't need to get together to figure out how to solve them, but we can still get value out of seeing other people's ideas. I think what we will see is that most simulation problems, while lacking an elegant solution, have some solutions which are significantly easier to code and debug than other solutions.
I'm interested to see how much better we can get at simulation problems by putting some time in to practice on them. If anyone has put in a tone of time I would love to hear from them about how much better they are. My best guess is that we won't save too much on the amount of man hours it takes to solve the problem, but that we can cut the console time the problems take down significantly.
The reason is really quite simple, simulation problems aren't interesting problems. They don't require any insight to solve them. All that is required is to accurately translate a set of (usually very complex) rules into code. The solutions tend to not be elegant. The console time needed to solve them is terrible. They are usually very long, and have enough special cases to force more than a couple of resubmissions.
While I think a majority of people will agree that simulation problems are not very interesting, we still have to deal with them. My view has shifted recently, I think that simulation problems are interesting because they are problems from world finals or regionals. We are going to have to compete with this problems, so we need to get better at them. Which of course begs the question, how can you get better at simulation problems?
I have yet to really try and get better at these, but that won't stop me from throwing around a few ideas. I think that solving a bunch of simulation problems will help, but not that much. Simulation problems are rarely similar to other problems, so solving one won't really help you in another one down the road.
Alan came up with, what I think is, a much better way to practice these problems. Assign one problem to your team/coaches every week. Everyone individually solves the problem (while attempting to still write code on paper and minimize console time), then everyone gets together and talks about how the implemented in and what cool tricks they used, and what tripped them up.
For these types of problems we don't need to get together to figure out how to solve them, but we can still get value out of seeing other people's ideas. I think what we will see is that most simulation problems, while lacking an elegant solution, have some solutions which are significantly easier to code and debug than other solutions.
I'm interested to see how much better we can get at simulation problems by putting some time in to practice on them. If anyone has put in a tone of time I would love to hear from them about how much better they are. My best guess is that we won't save too much on the amount of man hours it takes to solve the problem, but that we can cut the console time the problems take down significantly.
Friday, April 10, 2009
ACM ECNA Regional 2008
I never wrote a blog post about how the regionals went down, so here goes. We came in as the B team from CMU. We had only practiced a couple times with the A team and they beat us both times, once by a narrow margin and the other by a big margin. I thought we were getting more practices in, but either way we were the underdogs.
I started the contest off really nervous. I started by reading problem C which was a pretty trivial problem. I was scared about accidentally jumping on too hard of a problem at the start, but after I few minutes I went for the terminal. The problem was pretty simple and I submitted it, only to get it back with a wrong answer. In the mean time Celestine who was assigned problems A and B started working on B, probably not what he should have started working on but it was a doable problem. Alan started on D and also got back wrong answer. 45 minutes in we had two wrong answers already, and no correct submissions.
Alan and I helped each other out debugging code while Celestine started on B. Eventually I fixed my bug and got our first correct answer 50 minutes in, and Alan followed with his problem 6 minutes later. Alan went for E, while I helped Celestine with B and started looking at the last few problems. Alan finished E pretty quickly while Celestine was having problems with B. I worked with Celestine to get B wrapped up and get the significant figures worked out. We turned in B and somewhat surprisingly got it right the first time.
I'm not sure when, but I think about now we decided that we weren't going to get all 8 problems, so we canned A and just went for seven. I wrote up my somewhat hacked together program for F, it worked first time but I really didn't think that it was going to. After we got it right we checked the scoreboard and saw that we were in the lead (which I think is a bug because looking at the submission times we were never actually leading). Celestine identified G has brute force (despite by disbelief) and he went to work on that. In the mean time I worked on H with Alan. We started with a pretty simple solution, but we found some counter examples and had to make it more and more convoluted. Thankfully the bounds on the problem were so small that an extra factor of n in the runtime didn't hurt.
Celestine submitted G and got it wrong. While he was debugging Alan went to type of H, and I helped Celestine debug. We found Celestine's bug which I think was something small like swapping his is and js in some nested for loops. We had fifteen minutes left to finish off H. The scoreboard was locked with an hour to go and the top 3 was us, the other CMU team, and Waterloo, all with 5 problems solved. Our tiebreaker was pretty horrendous with 4 wrong submissions and a really slow start. At that point I thought we had no chance of winning the contest.
Alan debugged his code while I watched him and Celestine worked on some test cases. The clock was slowly ticking down and we couldn't even pass the example test cases. With one minute left on PC^2 (which means less than 2 minutes actually) we finally passed the example test cases and turned in the code. We didn't bother typing up the example test cases until after. We put them in and everything seemed to work. The contest ended and we still hadn't gotten a response back. At this point Alan was shaking uncontrollably. I thought that even with the seventh problem we would be in second or third because of our tiebreaker.
Eventually we got our submission to H back correct. The other CMU team came in and asked us how many we solved (the scoreboard was still frozen) we had seven, they had six. At that point whether we won the regional or not we were going to the world finals. I was still pretty sure we hadn't won overall. When we got to the coaches area the scoreboard was up and CMU had gotten first and second. We were the only team to solve seven.
I have been wondering how lucky we got to win the contest. After the fact Waterloo challenged the fact that their submissions to B were wrong claiming that it was a round error. They used ieee rounding instead of the normal rounding. The problem should be setup so that doesn't matter. The other CMU team said their submission to H would have worked if they had gotten the tiebreaker right for which path to pick. Our submission to H could have easily gone the other way, but it all seemed to work out in our favor.
In the end there was a big chunk of luck that helped us, but I think out team strategy was more of the deciding factor. The decision to not even attempt A was pretty crucial to us. We didn't waste any man power on it, while the CMU team (and maybe the Waterloo team) spend some time trying to figure it out. I think out use of console time was done really well, we didn't do much debugging on the console, lots of team debugging on paper.
On the other side our problem selection was pretty horrendous. We got E (one of the 2 easiest problems) two hours into the contest. We started B as one of our first problems (which only two teams ended up getting). In the end though if you solve seven problems and no one else does it really doesn't matter how you solve those seven problems. This is also an example of how for a team solving most of the problems at a regional problem selection can't hurt you that much. Sure our time penalty got hit pretty bad, but it didn't make us solve fewer problems. If a team who was only going to solve 4 problems went after B as their first problem they will probably only end up solving 2 or 3 problems.
With that win we are off to Stockholm in a week. After a winter of practicing I think it is going to give us a trip to the next world finals. The previous CMU A team hasn't been practicing much at all. For them to compete with us at next year's regionals they are going to need to put in a ton of work. Thinking back if the regionals go the other way and we don't put in the practice over the winter we could have effectively lost this year's regionals, and next year's.
I started the contest off really nervous. I started by reading problem C which was a pretty trivial problem. I was scared about accidentally jumping on too hard of a problem at the start, but after I few minutes I went for the terminal. The problem was pretty simple and I submitted it, only to get it back with a wrong answer. In the mean time Celestine who was assigned problems A and B started working on B, probably not what he should have started working on but it was a doable problem. Alan started on D and also got back wrong answer. 45 minutes in we had two wrong answers already, and no correct submissions.
Alan and I helped each other out debugging code while Celestine started on B. Eventually I fixed my bug and got our first correct answer 50 minutes in, and Alan followed with his problem 6 minutes later. Alan went for E, while I helped Celestine with B and started looking at the last few problems. Alan finished E pretty quickly while Celestine was having problems with B. I worked with Celestine to get B wrapped up and get the significant figures worked out. We turned in B and somewhat surprisingly got it right the first time.
I'm not sure when, but I think about now we decided that we weren't going to get all 8 problems, so we canned A and just went for seven. I wrote up my somewhat hacked together program for F, it worked first time but I really didn't think that it was going to. After we got it right we checked the scoreboard and saw that we were in the lead (which I think is a bug because looking at the submission times we were never actually leading). Celestine identified G has brute force (despite by disbelief) and he went to work on that. In the mean time I worked on H with Alan. We started with a pretty simple solution, but we found some counter examples and had to make it more and more convoluted. Thankfully the bounds on the problem were so small that an extra factor of n in the runtime didn't hurt.
Celestine submitted G and got it wrong. While he was debugging Alan went to type of H, and I helped Celestine debug. We found Celestine's bug which I think was something small like swapping his is and js in some nested for loops. We had fifteen minutes left to finish off H. The scoreboard was locked with an hour to go and the top 3 was us, the other CMU team, and Waterloo, all with 5 problems solved. Our tiebreaker was pretty horrendous with 4 wrong submissions and a really slow start. At that point I thought we had no chance of winning the contest.
Alan debugged his code while I watched him and Celestine worked on some test cases. The clock was slowly ticking down and we couldn't even pass the example test cases. With one minute left on PC^2 (which means less than 2 minutes actually) we finally passed the example test cases and turned in the code. We didn't bother typing up the example test cases until after. We put them in and everything seemed to work. The contest ended and we still hadn't gotten a response back. At this point Alan was shaking uncontrollably. I thought that even with the seventh problem we would be in second or third because of our tiebreaker.
Eventually we got our submission to H back correct. The other CMU team came in and asked us how many we solved (the scoreboard was still frozen) we had seven, they had six. At that point whether we won the regional or not we were going to the world finals. I was still pretty sure we hadn't won overall. When we got to the coaches area the scoreboard was up and CMU had gotten first and second. We were the only team to solve seven.
I have been wondering how lucky we got to win the contest. After the fact Waterloo challenged the fact that their submissions to B were wrong claiming that it was a round error. They used ieee rounding instead of the normal rounding. The problem should be setup so that doesn't matter. The other CMU team said their submission to H would have worked if they had gotten the tiebreaker right for which path to pick. Our submission to H could have easily gone the other way, but it all seemed to work out in our favor.
In the end there was a big chunk of luck that helped us, but I think out team strategy was more of the deciding factor. The decision to not even attempt A was pretty crucial to us. We didn't waste any man power on it, while the CMU team (and maybe the Waterloo team) spend some time trying to figure it out. I think out use of console time was done really well, we didn't do much debugging on the console, lots of team debugging on paper.
On the other side our problem selection was pretty horrendous. We got E (one of the 2 easiest problems) two hours into the contest. We started B as one of our first problems (which only two teams ended up getting). In the end though if you solve seven problems and no one else does it really doesn't matter how you solve those seven problems. This is also an example of how for a team solving most of the problems at a regional problem selection can't hurt you that much. Sure our time penalty got hit pretty bad, but it didn't make us solve fewer problems. If a team who was only going to solve 4 problems went after B as their first problem they will probably only end up solving 2 or 3 problems.
With that win we are off to Stockholm in a week. After a winter of practicing I think it is going to give us a trip to the next world finals. The previous CMU A team hasn't been practicing much at all. For them to compete with us at next year's regionals they are going to need to put in a ton of work. Thinking back if the regionals go the other way and we don't put in the practice over the winter we could have effectively lost this year's regionals, and next year's.
Thursday, April 9, 2009
Prepping for World Finals vs. Purdue
The last two Mondays the world finals team scrimmaged against Purdue (who just barely qualified for world finals with a correct submission at the 300 minute mark). The first week was a synthetic set made up of 7 IOI finals problems. The problem set was incredibly hard. Normally when I start a hard problem set there are a few problems where I have some ideas of where to start working, on this set I had nothing. I think the key was getting people assigned to the right problems. Alan gave me a fun DP problem, and I gave him a DP problem on trees (just like an assignment he had just a few days before). That helped us break open the problem set a bit.
We managed to get four problems in five hours, which seems like a decent accomplishment. Purdue got 2 in 5 hours, and a third in the thirty minutes after the contest. I think we should have gotten a fifth, but I'm not complaining about four. I think partially IOI is a different type of set (the bounds are a lot larger on most problems), and partially it is simply a very hard set. I am clueless how some high schoolers knock down three of these problems in five hours.
We practiced by ourselves the next friday on another IOI set. Again getting four problems, but this time out of only four on the problem set.
This Monday it was back to practicing with Purdue, this time on a problem set with 11 problems from various European regionals. All of the problems were the hardest 2 or 3 from their regional. I had about the worst contest I have ever had. I had 5 submissions on problem J. The first was a simple swapping i/j which caused a runtime error, second was a few more implementation bugs, third was a bad assumption about the problem, the fourth was a worse assumption, and the fifth was correct. The other problem I got was a simple max flow, which I managed to mess up once.
Overall we got 6 of 11, as did Purdue, but we did so with a better time penalty. I think on a better day we really should be solving 8 problems on that set. We had a problem done with 10 minutes left that just had a stupid implementation bug in Dijkstra, and a bruteforceable problem we never got to.
These types of days scare me, because one bad day at world finals throws out all the practice you did. Just like running (my other big sport) being in the right mindset seems to be key to this. I think today I was too focused on speed and not enough on correctness, especially on my max flow submission. I have a shot at redemption next Monday when we add Duke into the practice. Individually I think we are a little better than Purdue, as a team I think we are a good bit ahead. I have no clue how good Duke is, but regional results and their lack of a larger number of high ranking TopCoder members suggests they aren't that good.
We managed to get four problems in five hours, which seems like a decent accomplishment. Purdue got 2 in 5 hours, and a third in the thirty minutes after the contest. I think we should have gotten a fifth, but I'm not complaining about four. I think partially IOI is a different type of set (the bounds are a lot larger on most problems), and partially it is simply a very hard set. I am clueless how some high schoolers knock down three of these problems in five hours.
We practiced by ourselves the next friday on another IOI set. Again getting four problems, but this time out of only four on the problem set.
This Monday it was back to practicing with Purdue, this time on a problem set with 11 problems from various European regionals. All of the problems were the hardest 2 or 3 from their regional. I had about the worst contest I have ever had. I had 5 submissions on problem J. The first was a simple swapping i/j which caused a runtime error, second was a few more implementation bugs, third was a bad assumption about the problem, the fourth was a worse assumption, and the fifth was correct. The other problem I got was a simple max flow, which I managed to mess up once.
Overall we got 6 of 11, as did Purdue, but we did so with a better time penalty. I think on a better day we really should be solving 8 problems on that set. We had a problem done with 10 minutes left that just had a stupid implementation bug in Dijkstra, and a bruteforceable problem we never got to.
These types of days scare me, because one bad day at world finals throws out all the practice you did. Just like running (my other big sport) being in the right mindset seems to be key to this. I think today I was too focused on speed and not enough on correctness, especially on my max flow submission. I have a shot at redemption next Monday when we add Duke into the practice. Individually I think we are a little better than Purdue, as a team I think we are a good bit ahead. I have no clue how good Duke is, but regional results and their lack of a larger number of high ranking TopCoder members suggests they aren't that good.
Subscribe to:
Posts (Atom)