Problem solving, programming, and research

Crash course on design - Stanford d.School

2011-01-08T17:14:00.000-08:00

One of my colleagues from WorkerExpress, Joe Mellin, invited me to join him for a design workshop being put on by the Hasso Plattner Institute of Design at Stanford. Joe is a former graduate of the d.School's masters program. I'm interested in design and I even taught principles of user-centered design for a Human Computer Interaction course at the University of Victoria, so I was keen to join him.

I really had no idea what the day would entail, I just knew to show up at 9am and I'd be done sometime around 1pm. Arriving at the workshop, I discovered there were to be over 100 people involved. We were instructed immediately that we'd be breaking up into three different groups. Once in those groups, we were told that we would be led through a full design cycle with a target demographic of potential users (see picture of design process below). Our goal was simply to design a new holiday experience for kids. The d.School had arranged to have approximately 80 students ranging from around 11 to 17 years of age to be our volunteer users.

After this brief instruction, we were put into groups of four, where we quickly introduced ourselves, and then had to come up with interview questions to ask the kids that would soon be arriving to talk to us. Each group was also assigned a "d.leader", i.e. a student at the d.School, to help guide us through the process.

One of the really interesting things about the d.School is that it brings together people from very diverse backgrounds to teach them how to become design experts. The workshop today was able to mimic that as each person in my group had very different backgrounds than myself. One was an MD now doing his MBA at Stanford, one was currently working in the medical school at Stanford, one works at Google, and finally there's me, a reformed academic now working at a start-up.

We only had about 5 minutes to prepare for the interviews, then we interviewed two different pairs of students for about 15 minutes each. We asked them about their holidays, what were their likes/dislikes, did they miss school during the holidays, what was their favorite holiday ever, were their family around during the holidays, and so forth.

Actually talking to users is always interesting and usually surprising. We had two very different groups of users. Our first group were two 12 year old boys. Their parents were generally quite busy with work over the holidays so family time was limited. They were basically left to their own devices. In contrast, our second group were two 12 year old girls that spent their holidays traveling all over the world with their families.

Here's a picture of the notes we took during the interviews. Although difficult to tell, the sticky notes are organized into four different groups: feeling, quote, thought, and action.

Following the interviews, all the groups came back together to be quickly introduced to the next part of the design process: defining our user, their needs, and the insight about the problem. Although the users from our interviews had very different holiday experiences, there were some common themes. For example, all of the students mentioned that they sometimes get bored during the holidays. They sometimes miss school because they get to see their friends at school, but not as regularly over the holiday. They also sometimes didn't seem to know what to do with their time following Christmas celebrations.

Taking these themes into account, we determined that our users were extremely bright, junior high students that needed interaction and socialization in a world where they did not know how to choose what activities they do during the holidays (or something to that effect, can't remember exact phrasing).

After our point of view was established, we brainstormed ideas for how to possibly address it (see picture below). We had crazy ideas like group travel for kids, city-wide laser tag, to more tangible solutions like a community center that organizes activities. We eventually settled on proposing an online application that was able to combine a lot of our ideas. The idea was to create a market place for kids to be able to express interest in participating in certain activities. Once enough kids expressed interest in a particular activity, all the leg work for actually making that activity happen would be handled by us, which could include transportation, equipment, some supervision, and so forth. Another way to think about it would be summer camp, but coordinated completely online and based on your personal interests.

Using this idea as a basis, we designed a prototype and then interacted with different students to test the prototype. This time we had three high school girls as our users. These girls were pretty incredible, one even stated, "this seems to add a level of complexity that's unnecessary". Only in Palo Alto, California would that statement be in a 17 year old females vocabulary!

All in all, it was an extremely fun and interactive workshop that I highly recommend if you get the chance. I'd love to have all WorkerExpress engineers participate in this workshop as they join the company. It's a great way to learn the basics of user-centered design.

Check out the video below. As an exercise to get us ready for brainstorming we played rock, paper, and scissors. Everyone starts as an individual competitor. When you lose, you become the winner's biggest fan. The video below is at the end of the day when there were only two left standing.

ACM ICPC Pacific Northwest Regional Competition

2011-01-03T10:08:00.001-08:00

Although I was not heavily involved in the ACM ICPC competitions this past Fall, I followed the Pacific Northwest regional quite closely. Several of my former students were competing for the University of Victoria team and of course my new university (Stanford) was also competing.

UVic had a great start to the competition, but ran into issues in the second half and ended up finishing in 9th. However, given that the university has only recently started competing in the ACM ICPC competitions, a 4th place finish in 2009 followed by a 9th place finish in 2010 is a pretty fantastic result.

The contest this year was quite interesting in a variety of ways. First, for the first time in a very long time the top team was not Stanford or the University of British Columbia. Second, although Stanford Red solved problem D at the 18 minute mark, there was 230 submissions for this problem, and only 3 were deemed correct. To anyone with much experience in these types of contests, this result looks a little fishy.

Rather than recap all the events and outcome, I'll point you to Brad Bart's (SFU coach) recounting and interpretation of the events: http://www.cs.sfu.ca/news/events/ACM/2010/.

I am personally not very happy with the way this screw up has been handled by the ACM ICPC. If you have an opinion, post it to the comments or better yet let ACM ICPC know what you think.

Semantic Search - For Reals?

2010-12-03T11:01:00.000-08:00

Recently a project I am involved in at Stanford participated and won the Semantic Web Challenge at the International Semantic Web Conference. The Semantic Web Challenge is a competition for Semantic Web applications. For the uninformed, the Semantic Web "is a group of methods and technologies to allow machines to understand the meaning - or 'semantics' - of information on the World Wide Web". Essentially, the Semantic Web hopes to move web applications beyond simple syntax to actually supporting the "meaning" behind content.

In the challenge, the focus is not so much on the technical or research aspects of the tools, but more on their usefulness for target users. The challenge helps demonstrate what semantic technologies can bring to society.

Our application, NCBO Resource Index: Ontology - Based Search and Mining of Biomedical Resources, is a semantic search application for biomedical researchers (check out the video below). I designed and developed the user experience and interface.

The application allows researchers in the biomedical sciences to perform "concept-based search" over 22 different biomedical resource databases. Thus, rather than a researcher typing in keywords, the researcher would type in concepts from their domain of interest, those concepts come from ontologies, the backbone of the Semantic Web. For the sake of simplicity, an ontology is a structured terminology that describes the terms within a specific domain, the properties of those terms and the relationships between them.

In terms of user interaction and searching, the behavior is quite similar to conventional search engines like Google. The difference being that when you select a term from the auto-completion drop down, that term comes from an ontology that was used to index elements within the various biomedical resources. I also included helpful tag clouds (see figure below) for visualizing related concepts to your current search query and I use color intensity to represent more relevant resources based on your current search terms.

The power of the search tool comes from how the index gets constructed. The National Center for Biomedical Ontology maintains a project called BioPortal. This project is an open library of more than 200 ontologies in biomedicine. Using the terms from these ontologies as our term-base, we automatically annotate or "tag" textual descriptions of the data residing within the elements of the 22 biomedical resources. These could be things like patient records, gene expression data, research articles, clinical trials, etc.

These annotations act as a link connecting an ontology term to a data element. The really useful part of this process and also where the semantics begin to play a role, is that we can use the structure of the ontology to expand these annotations. So, rather than getting a simple keyword like "breast cancer" mapping to a particular clinical trial, we also know any synonyms of "breast cancer" described in the ontology. We can also use the hierarchy of the ontology to link more general or specific terms to the resource like "cancer" or "melanoma". Finally, we can use mappings between multiple ontologies to discover other related terms.

This is truly where the power of ontologies can be seen and where a semantic approach to search can be very useful. For example, searching for the keywords "retroperitoneal neoplasm" within the Gene Expression Omnibus website will return zero results. However, the same search in our tool will retrieve relevant results annotated by the child term of "retroperitoneal neoplasm" from the NCI Thesaurus, "pheochromocytoma". Results are scored based on the distance of the matching annotation from a given search concept.

Another big advantage to our application is that the ontologies form a "semantic bridge" between very different biomedical resources. One search execution automatically gives you access to 22 different databases, allowing a researcher to explore relationships between things like gene expressions and clinical trials relevant to a specific concept. Without this, researchers are forced to open up multiple web pages and search each database independently.

Of course all these annotations take a long time to index and it results in a boat load of data. The current index is stored in a 1.5 terabyte MySQL database that contains 16.4 billion annotations, 2.4 million ontology terms, and 3.5 million data elements (stylized graphic below). Other members of the team have worked to figure out clever ways to do a lot of this indexing rather efficiently. You can read about it in Paea Lependu's paper Optimize First, Buy Later: Analyzing Metrics to Ramp-up Very Large Knowledge Bases.

We are working to include more resources in the index and also speed up the search support. If you're interested in playing with the application, check it out in the BioPortal integration.

Dinner with Thumbtack and Leaving Stanford

2010-11-18T10:04:00.000-08:00

Before I get into this post, I should first explain that I have decided to leave Stanford after January, 2011 for the wild and whacky world of industry. I will be joining WorkerExpress as the Chief Technical Officer.

Briefly, WorkerExpress is start-up in San Francisco co-founded by Joe Mellin and Pablo Fuentes. We offer a service for blue collar workers to both market themselves and provide them with work. Our customers are contractors that essentially "lease" employees from us. We help the contractors by automatically matching available workers to the specifications of a particular job. We also provide a certain level of quality control on the workers in terms of their skill assessment, reference checks, internal reviews, background checks, and so forth. We use a lot of SMS technology to provide flexible on-demand labor.

Another San Francisco start-up called Thumbtack is somewhat playing in the same space as us. While we provide on-demand labor for contractors, essentially a business to business service, Thumbtack provides a market place for local services (i.e. business to consumer service). Think Craigslist but less 1995.

Joe and Pablo know some of the brains behind Thumbtack and as a result we were invited to Thumbtack's "world headquarters" for dinner last night. The headquarters is in a three-story house in San Francisco. One floor is dedicated to development, another is a board room, and there's also a dining and kitchen floor. A few of the developers actually live in the house too (can't beat that commute).

I actually really like the idea of using a house for an office building. The advantage is that you generally have a built-in full kitchen along with a shower and even rooms to crash in after a long hacking session. I also think the rent is probably less expensive than an office building.

A potential disadvantage is that you basically may never leave your work. However, in a start-up environment, this is often the case and if I am going to be working crazy hours, I'd prefer to be able to prepare decent meals and catch a nap if necessary.

So, back to the dinner. I had not met any of the Thumbtack crew prior to the dinner. Joe and Pablo convinced me to bring along my wife, Theresa, claiming that this would be a social event and not about business. Of course, you stick me in a room full of other geeks/programmers, it's pretty hard to keep the conversation in a realm where someone without a computer science degree can actually participate.

Theresa had not suffered that kind of geek assault since she accompanied me to the 2003 ACM ICPC world programming finals. Things got even worse when I realized one of the Thumbtack developers had competed in the ACM contests during his undergrad. Luckily our intern and sales guy from WorkerExpress were there to chat about non-programming related topics.

Despite my concern for Theresa's boredom, I had a great time at the dinner. The team at Thumbtack seem to have the same kind of hunger to make a successful business as we do at WorkerExpress. They understand the kind of work environment that is necessary to work long hours.

I am extremely excited to be starting full-time with WorkerExpress. I plan to hire a couple of software developers early in 2011. So if you're interested or know someone that is, shoot me an e-mail or leave a comment.

Bad design or evil plot to prevent caffeine addiction?

2010-11-05T09:14:00.000-07:00

Above is a picture of the coffee maker we have at the Stanford Center for Biomedical Research. Can you figure out how to make a large coffee with light strength?

For the first month or two that I was at Stanford I did not know how to re-configure the coffee setting on this machine. I took whatever was the last configuration, so sometimes I got an expresso, sometimes a small coffee, or perhaps a large one, all at varying strengths. It wasn't until I finally observed someone that actually knew how to use the machine that I figured out how to change the coffee configuration.

So, the answer to my original question, "Can you figure out how to make a large cup of light coffee?" is that you need to press your finger against the lights at the top of the machine to adjust the coffee size and strength. Not only do you need to press down on the light, you need to do it for about a second. Thus, for a large coffee with light strength, you would first hold your finger against the large cup on the left-hand side, once that light switches, then hold your finger against the single coffee bean on the right, indicating light strength. (See picture below, I've circled the "buttons" you need to press.)

Is this poor design or am I just an idiot? Or perhaps I should have just asked someone about how to use the coffee machine? Well, first, I couldn't really ask someone because A) I'm a dude and B) I have a PhD in Computer Science preventing me from ever acknowledging that I don't understand something technical :-). So that option is out.

As for, am I just an idiot? My argument is of course, no, I am not :-). As further empirical evidence, I also know that I am not the only person that has struggled to use this thing. I was actually getting coffee recently and a guy that has been in the group for several years asked me how I was able to get two cups at once. Therefore, my argument is, it's a coffee machine for crying out loud, anyone should be able to use it. So, assuming that, what's wrong with the design?

The big big big issue with using what looks to simply be indicator lights as buttons to re-configure the coffee is that there is really no obvious feedback that the lights are something you can press. Not only that, but you have to press them for a period of time, so just running your finger over them, does not change their state. To toss out a Human Computer Interaction term, these lights have no pressing "affordance".

An affordance is "an actionable property between the world and an actor". That simply means that certain objects have physical properties that indicate specific actions. For example, a lever affords pulling or pushing, handles are for holding, wheels are for turning, etc. However, a light isn't really for pressing. On the coffee machine, the light is flat, there is no physical feedback to indicate that a pressing action or a change in the coffee configuration is about to occur when you place your finger on it.

The sad thing is, this is very easy to address. If the coffee manufacturer simply made the lights beveled or slightly concave like the iPhone's button and had them actually press in when you pushed your finger against it, I think people would figure it out.

Alas, that's enough harping on this issue. One of the problems with learning about design is that it's a tough skill to turn off. You'll constantly see poor design and be irritated by it. Welcome to my life of torture :-).

Visualizing your social circle - mashing up GMail and Facebook

2010-10-25T15:49:00.000-07:00

What's this? Another post? Yes indeed, two within a week of each other. My blog tends to work this way, my writing comes in waves. This post relates to data mining, visualization, and mashing up GMail with Facebook.

I attended a talk last week at the CS department at Stanford and the speaker mentioned that they were using the "TO" field in e-mails to perform hierarchical clustering to discover social groups. The intuition is pretty simple, you typically only include multiple people in an e-mail if they make up some kind of social group that you interact with.

I thought I'd try out this idea on my own GMail account. After digging through the GMail's API documents, I downloaded a Java example of how to connect to your account using IMAP and OAuth. I wrote a Java program to go through all my Sent messages since I first created my GMail account back in 2005 and construct clusters based on the TO and CC fields.

The algorithm is very basic. If an email was sent to more than one person, then I assume those people are somehow associated. So, assume I sent an email to people A and B. I would append person B to A's list of associations and append A to B's list of associations. I did this for 5 years worth of sent messages.

The data I was getting looked pretty reasonable. I had clusters consisting of different people I've worked with over the past 5 years, people I socialize with, and students I've taught.

There's a number of potential applications for this. One could be making suggestions for label groups in GMail. Another idea is to use this kind of mining to suggest groupings in something like Facebook. To experiment with that idea, I took the groups I mined in GMail and mashed it up with data publicly available on Facebook.

That is, for each e-mail in the list I mined, I used Facebook's API to search to see if that person exists within the Facebook universe. If they did, I then processed all their associations, looking those people up on Facebook via the search API. That information forms an adjacency list, linking people's Facebook profiles based on how I have interacted with them through e-mail.

For example, if I e-mailed people A, B, and C together and at another time, e-mailed C, D, and E, and assume all those people exist on Facebook, then I end up with a graph description like this:

A: [B, C]
B: [A, C]
C: [A, B, D, E]
D: [C, E]
E: [C, D]

So, that's kind of fun, but these graph structures would be a lot more interesting to look at if there was a way to visualize them. Well, I just so happen to be working on a JQuery graph visualization plugin that wraps a graphing library called FlexViz.

After a little more hacking, I made a nice little web page for browsing these mashed up social groups. One such group is displayed at the top of this post. I created the group by extracting all people directly and indirectly associated with my wife (Theresa Demont).

If you look at the picture below (same as at the top, but annotated), there's basically two groups here. One on the left and one on the right. The two groups are connected by a bridge between Nick and Colton. This is because the people on the right are all students I coached in programming competitions. Nick also helped out with coaching for a while, but Nick is also friends with Theresa, so he bridges my programming competition world and the social world I have with my wife.

Another interesting example is the graph structure defined by my CrossFit associations. Below, the graph on the left are the various CrossFit people I interacted with through e-mail before I moved to California, while the graph on the right is the CrossFit people I've interacted with since moving to California. It appears that I do not bulk e-mail nearly as many CrossFitters now. The truth is, most of my social interactions have moved to Facebook.

Most of this effort was just for fun to see what the resulting application would look like. However, it's also kind of interesting way to browse some of your own history that you record through e-mail. In my graph, it's easy to see the various changes in my work associations as I've changed companies and universities. I have a UNB group, UVic group, and Stanford group. It would be great to add in a timeline filter so I can hide people in the graph based on when I actually communicated with them. This could actually be animated so you could visualize the changing landscape of your social circle!

Finally A Post! CrossFit Athlete Popularity?

2010-10-19T12:59:00.000-07:00

It's been quite a while since I last posted. I have had lots of things to talk about, but just haven't found the time to write anything.

In this post, I am going back to analyzing CrossFit-related data, but this time I am taking a completely different angle. Rather than analyzing scores and comparing athletes based on their performances, I am comparing athletes based on their popularity and what the implications of popularity are within the CrossFit community.

The first thing I had to consider with this project was how can athlete popularity be measured and secondly, where can I find lots of data to actually measure this value? I decided to go with a rather simplistic model. To measure popularity, I decided to base it on how often a particular individual is discussed in the CrossFit community.

There's lots of potential data sources for this kind of information. I went with CrossFit.com. Any time an athlete is featured in an article, or has their results linked, or is discussed in the comments, I collected that information.

The technical details regarding how I did this is pretty simple. I got a list of all 2010 Games athlete's names, then I wrote a small PHP script to make requests to every article posted on CrossFit.com over the past year. I then tracked the frequency of how many times I encountered a name within the article's text and comments. I tracked this information for all articles occurring before the CrossFit Games and for all articles after the Games. I also added in a few popular non-2010 competitors, like Pat Barber, Dave Lipson, Josh Everett, Pat Sherwood, and Kelly Starrett.

There's some assumptions with this approach and as a result some data will be lost. There could be mentions that are not captured due to someone using a nickname or partial name or pronoun rather than the person's full name. Further, there's no image analysis, so I don't take the images from posts into account, which could potentially reference an athlete.

The goal with dividing the data into two categories: pre-games and post-games, was so I can look at how the games influences someone's popularity. Does doing well in the games make you more popular? Why is that important?

Using the two sets of frequencies, I normalized the values by the number of posts analyzed for each category (196 pre-games, 77 post-games). If you sort these normalized frequencies and plot them, one interesting thing is that they appear to follow a lognormal distribution. That is, very few athletes are mentioned a lot, and many athletes are mentioned occasionally. This is mostly interesting from a statistical perspective as many statistical tests assume the data is normal.

Below is a table displaying the most highly mentioned athletes pre-games and a table displaying the most highly mentioned athletes post-games.

Pre-Games Popularity
Name	NF
Rob Orlando	0.459
Pat Sherwood	0.316
Jason Khalipa	0.245
Dave Lipson	0.204
Chris Spealler	0.194
Josh Everrett	0.158

Post-Games Popularity
Name	NF
Pat Sherwood	0.714
Graham Holmberg	0.675
Rob Orlando	0.519
Chris Spealler	0.519
Dave Lipson	0.519
Austin Malleolo	0.312

You can see that there's some fluctuation in the order, plus some athletes that were not in the original set of highly mentioned athletes are now in the list, in particular, Graham Holmberg and Austin Malleolo. This makes sense, as both Graham and Austin did very well this year (1st and 6th respectively), but Graham was not in the top in 2009 and Austin did not compete at all. However, there was a lot of anticipation and expectation with regards to former games competitors like Josh Everrett, Jason Khalipa, and Rob Orlando. Following the games, only Rob remained in the top for highly mentioned athletes. It's also interesting that Dave Lipson is in the top for both categories, even though he does not have a strong games history.

To determine if there's a correlation between the measured athlete popularity and their finishing position in the games, I compared the athlete's post-games popularity scores with their games ranking. There was a statistically significant correlation between these two vectors. Note, I had to remove any non-games athletes from this analysis.

Following this, I compared the difference in popularity score pre and post-games for all athletes by subtracting their normalized frequency for the post-game category from the pre-game category. Athletes with large negative values indicate that their number of mentions increased greatly post-games, while athletes with large positive values mean the opposite.

Athlete Popularity Fluctuations
Rank	Name	Difference
1.	Graham Holmberg	-0.614
2.	Pat Sherwood	-0.398
3.	Chris Spealler	-0.326
4.	Dave Lipson	-0.315
5.	Austin Malleolo	-0.291
...
46.	Blair Morrison	0.026
47.	Josh Everett	0.041
48.	Tommy Hackenbruck	0.045
49.	Spencer Hendel	0.058

We can see from this table that Graham Holmberg's CrossFit.com presence increased dramatically after the games. His score is more than 4 standard deviations away from the mean. This is hugely significant.

Pat Sherwood was consistently popular across both data sets, but he also had a huge increase in visibility post-games. I think a lot of this had to do with his success as a commentator during the games.

So why should anyone care about any of this?

A big reason, I think, is because as CrossFit becomes more mainstream and continues to grow, there's more money and business opportunities. There's starting to be huge financial incentives for doing well at the games or atleast becoming a popular athlete. The financial incentives go beyond the money that you win at the actual Games, but extend to your own business. Many of the games athletes are coaches and affiliate owners. Surely, being a "web-lebrity" is going to help drum up business. Furthermore, some athletes (i.e. Rob Orlando) are getting into selling equipment. Being a name within the community is going to help establish your brand and establish your company.

Please don't think that I am insinuating that these athletes are competing solely for the money and business opportunities. But I think as the sport grows, visibility/popularity and establishing yourself as a "brand" is going to play a larger role. Similar to Olympic athletes, top-level CrossFitters may need sponsorship to allow themselves to have a full time training schedule. To entice sponsorship, even the most reluctant athletes may need to increase their presence in the community.

Why should you care if you will never be a Games competitor?

Well, I think from a business perspective, it's important to recognize how important this kind of visibility is. If you're a games competitor, you have a leg up on just about every other CrossFitter out there in terms of promoting your business. However, there are alternative means to increase your impact. Web Smith blogs about the importance of social mediums like Twitter and Facebook to help promote your business.

In California, there are tons of CrossFit gyms. There are three just in Palo Alto. How do you separate yourself and how do you get potential members to choose you over so many alternatives? Well, you can potentially take your chances and train for the games or increase you popularity/presence through other means: Twitter, Facebook, sponsoring local athletes, competing locally, blogging, having a useful website, and possibly search optimization for your site.

I am going to conclude this rather long post with my standard warning about this kind of data analysis. The intention is not to insult any athletes, but is merely a thought experiment for me. Also, there's many ways these results could be potentially analyzed. My interpretation and explanation may not be the whole story. Finally, I am making a rather large assumption here that popularity does lead to increased business. I do not know directly whether any of these athletes have had increased business at their boxes as a direct result of their web-presence.

CrossFit Scoring - Alternative Perspective

2010-06-13T09:48:00.000-07:00

This is my third foray into the world of CrossFit data analysis, this time looking at scoring. Recently, over at the CrossFit Games website, there was an article about Scoring CrossFit Competitions as well as one talking about Scoring Technology. I participated in a number of conversations in the comments section with regards to how competitions are scored. This post is going to be a bit of a summary of those conversations as well as a description of a new extension to the CrossFit Data Explorer that allows people to explore different scoring schemes for any given competition (i.e. alternative perspectives).

For those that are unaware, there are a variety of approaches to scoring competitions. I am not going to go into detail about these different metrics as they are described in both the articles I linked to above. The main thing to keep in mind is that each scoring system has certain "flaws" and depending on how an event is scored, there can be different outcomes.

I wanted to explore some of these different scoring schemes as well as allow others to play with these different metrics. To do this, I added a new tab to the CrossFit Data Explorer called "Scoring tables". Check out the screenshot below displaying data from the Men's Northwest Regional.

This view shows a table of the athletes, their results for each event, and it is sorted by the overall placement. On the left-hand side, you can choose how to score the athletes. The currently available scoring options are:

Ranked-based - each athlete receives points based on their ranking in a workout, 1pt = 1st, 2pts = 2nd, ..., 50pts = 50th. The athlete with the lowest overall score wins.
Proportional - Athletes receive scores based on their relative performance to the top scoring athlete in an event. Highest overall score wins.
Lowest converted points (LCP) - Timed workouts receive 1 point per second, all other results are subtracted from this score. Lowest overall point total wins.
Standard score - Athlete receives points based on the distance between their score and the population mean. Highest score wins.

The other feature supported by this new scoring component is that you can filter workouts from consideration in the ranking process. For example, if you thought, "Damn, if that stupid deadlift workout hadn't been in the regional, I would have made it." Well, now you can verify whether that's true :-).

Ok, time to dig into comparing some scores. Keeping with the Men's Northwest Regional, if we re-rank the athletes based on the four supported scoring systems, we get the following results (top three athletes made games from this region).

System	First	Second	Third
Rank-based	Chris Spealler	Jerome Perryman	Eric O'Connor
Proportional	Chris Spealler	Jerome Perryman	Eric O'Connor
LCP	Jerome Perryman	Jordan Holland	Christopher Dunkin
Standard	Chris Spealler	Jerome Perryman	Jordan Holland

As we can see, there's a certain amount of fluctuation in the results, especially for the LCP metric. In fact, with LCP, Eric O'Connor finishes 5th and Chris Spealler comes in 10th! (See screenshot below).

The major reason for this is the way the scoring system is designed. Each workout is scored completely independently from all other workouts, so a particular workout can completely dominate the final value. For example, coming in first in workout #1 at this regional gives you a score of 159 while coming in first in the second workout gives you a score of 10,908. That's a massive difference!

In fact, if we look at the correlation between the LCP ranking and the ranking based purely on the second workout result, there's a strong correlation of 0.45 (p < 0.01). In comparison to the actual official ranking results, the correlation between workout #2's ranking and the official ranking is only 0.37 (p < 0.01).

One really nice thing about the proportional, LCP, and standard score is that they "reward" people for being exceptional. For example, consider the Canada Men's Regional results. Erik Szakaly completed the Wall-ball/Pull-ups workout more than a minute ahead of the next fastest athlete. Check out the picture below, look at how far Erik's result is separated from all other athletes. Obviously this guy eats wall-balls for breakfast.

He received a low score of 1 point at the regional, but in the standard score system he would have received 2.17 points, almost a full point ahead of the next closest score (see below). This is a fairly significant margin in this scoring system.

Perhaps some kind of hybrid scoring system is needed. I think as CrossFit evolves, so will the scoring metrics, just as we see with other sports.

As fun as it is to play with all this data, there's a few things to keep in mind. First is that switching the scoring system and re-ranking athletes assumes that the athletes would perform the same regardless of the scoring system. However, that's quite possibly not true. For example, Garth Prouse won the Canadian Regional run quite easily and received 1 point for coming in first (rank-based system). However, if he knew that he was being scored based on one of the other three systems, he may have pushed his pace harder to give himself a larger lead.

Another assumption that is made is that the people that designed the workouts would include the same set of workouts regardless of the scoring system used. This may not be the case. For example, in the Northwest regional, perhaps the workout designers would have scored workout #2 differently if they were planning on using an LCP system so as to not bias the result in favor of performances in this workout.

The other thing to be aware of is my application has to make certain assumptions. It assumes that all workouts with a time-based result are ranked lowest to highest, and all other workouts go highest to lowest. In the Canadian Regional, the run did not have times recorded, so including this event in the score comparison leads to misleading results.

More CrossFit Data Analysis - This time you can play too!

2010-06-04T15:06:00.000-07:00

Don't care about my post and just want the good stuff, follow this link: CrossFit Data Explorer

My last blog post was quite easily my most popular post to date (although my Searchy-type problems post did receive a fair amount of attention). One former student of mine explained that my entry had, "the most practical findings for average people. Most of your posts even I have trouble understanding … you need a PhD".

Ok, so my blog isn't always for the faint of heart :-). Ah well. However, this time I'm going mainstream again. Well, not quite mainstream, but as mainstream as CrossFit is :-).

Due in part to the level of interest my last post generated as well as my own curiosity, I spent some more time looking at the CrossFit Games data. I've had some requests to analyze the women's data from the Canada Regional in the same way I analyzed the men's data. I haven't done that yet, but I think what I have done is pretty cool. And, more importantly, anyone can now interact and play with the data to discover their own interesting trends and results!

I decided to build a visual tool for interacting with the various data available on the CrossFit Games website. I started out building it as a standalone Java application, but that seemed soooo 1998. So, part way through development I abandoned the Java application in favor of a Web 2.0-style application, equipped with all the latest buzzword technologies (i.e. AJAX, jQuery, JSON, etc.).

I've made the application available online here, so feel free to play with it.

There's three different visualizations available that allow you to compare athletes based on different event modalities as well as athlete rankings across various events. It should work with any URL that resolves to an overall results page (example page: Men's Canadian Regional). I've pre-populated a drop down with all the regional results so you can select items from there or paste in an appropriate URL. The Men's Canadian Regional data is loaded by default. The application may not work with Internet Explorer, so I suggest Firefox, Safari or Chrome.

In the Compare events tab, you can set the graph axes to show results from different events. For example, using the default data, we can set the x-axis to be the first event, the 6.7 KM run, and set the y-axis to be the second event, the snatch complex. Comparing athlete values across these two events allows you to explore an athlete's strength versus endurance. If you look at the screenshot below, the tooltip shows that Garth Prouse was 1st in the run, but 30th in the snatch.

One interesting thing we can see in this view is how widely distributed the athletes are for various events. Consider the screenshot below where I plotted the overall placement versus the time for the double-under/burpee workout. Everyone is pretty closely clustered, but I've marked two distinct outliers. I'm guessing these two individuals must have struggled with double-under technique. Even those these two scores appear to be outliers, if you read my last post, there was little statistically significant difference between these athletes on this particular workout. In contrast, there is a lot of variance in the distribution for this workout when you inspect the women's data (second screenshot below).

In the Compare athlete rankings tab, you can inspect an athlete's ranking in each event as well as their overall ranking. For example, in the screenshot below I've selected only the top 6 athletes from the default data. We can see that three of these athletes (Erik, Nate, and Dan), for the most part, were pretty consistent across all events. On the other hand, DJ Wickham has an outlier on the run, while Garth and Michael have an outlier on the snatch complex event.

Finally, in the Event rank comparison tab, you can compare an athlete's ranking in a specific event versus their overall placement. This allows you to visually correlate how closely tied an event's ranking for an athlete is in comparison to how they did after completing all events. The screenshot below shows all athletes and their rank in the run versus their overall ranking. We see that Cam's ranking went from 25th in the run to 34th overall, while Jason Fleming went from 10th to 50th and in the other direction, DJ Wickham went form 38th to 6th overall.

For those with technical expertise or those just curious, the way the application works is I send the URL corresponding to the overall results for a sectional or regional competition to the server-side code. Taking whatever URL is provided, I make a server-side request to the URL, get the HTML contents and parse out the values of the overall results table using the PHP Simple HTML DOM Parser. I load this into a simple datastructure (a hashtable of hashtables), which describes the athletes, the events, and all the various results. This information gets encoded as JSON and sent back to the client (front-end).

On the client, I convert the JSON text into a Javascript object/associative array. Then, based on whatever tab is selected, the data is processed into a data series for each athlete. I use Flot to handle the rendering of the graphs. All the interactive behavior and some of the UI is built using jQuery.

The data is split into results for each event and overall placement. For each of these, the results are split into rankings and actual scores. For example, in the default dataset, athlete "Rogers, Dan", has both an overall rank of first as well as an overall placement score of 37. I do some simple things like recognize times, which for plotting purposes are converted into seconds.

Please post to any questions, suggestions, or general comments. Please let me know if you discover anything interesting :-).

CrossFit Meets Data Analysis

2010-06-01T10:17:00.000-07:00

It's been quite a while since I've updated. I've had lots to post about, but other things have taken priority. Today's update is going to be a little different, but I think it's pretty fun stuff.

Any of my readers that know me personally know that besides being obsessed with computers and research related things, my other passion is fitness and sports. In particular, I'm really into something called CrossFit. It would take an entire post to describe CrossFit in detail, so here's my very short explanation: it's the sport of exercise.

One of the cool things about this growing "sport", is that there is a global competition called the CrossFit Games. The games are kind of like the Olympics, but for CrossFit athletes. To qualify, you have to compete in two different levels of competition (sectional and regional), and place high enough to secure one of only 50 spots.

This past weekend, I had several friends competing in the Canada-wide regional event. Only six men and six women from all of Canada get to go. Unfortunately, none of my friends made it (full results).

While observing the events, I got this idea about taking the results from the various events and doing some data analysis on it to see how the different athletes compare. I've been doing something similar in my regular research work, but for entirely different data. I decided to experiment with applying a similar clustering and statistical analysis approach, but to the CrossFit regional data!

To start with, I wanted to try to classify athletes based on the similarity of their performances across the different events. Some athletes may be great runners, but may not be super strong. So there should be different classifications for athletes and each of these classes will have distinguishing characteristics.

To do this, I downloaded the data from the CrossFit Games site and wrote a quick Java program to clean it up a bit. For my analysis, I considered each of the 5 events as different features describing a particular athlete. For example, my friend Cam Birtwell would be described by the vector [25, 145, 793, 282, 776]. He placed 25th in the run (did not have times), lifted 145 lbs in the second event, and the last 3 numbers are his times in seconds to complete each event.

Once I had vector descriptions for each athlete, I then used the Weka data mining tool to perform K-Means Clustering on the data. K-Means tries to divide a given data set into K different clusters or classes. You have to choose K up front. Since I didn't know what a good K would be, I varied K from 2 up to 10, then used mathematical formulas to calculate the compactness and separation of the clusters I got. Based on these metrics, K=5, K=7, and K=8 appeared to be the best.

After some exploration of the data, I decided K=7 seemed the most interesting and made the most sense. This means that out of the 50 or so male athletes competing in the Canada Regional, I split them up into 7 different groupings.

Once I had this data, I wanted to know why a particular athlete, like Cam, was assigned to a particular cluster. To determine the distinguishing characteristics of each cluster, I performed multiple Analysis of Variance (ANOVA) calculations to determine the statistically significant features of each cluster. That is, for each of the five features/event, I performed ANOVA to check for statistical difference in that particular feature when compared across all 7 clusters.

For most events, there was statistically significant (p < 0.05) differences. The event with the least difference was event 4, the double-under, burpee event (p = 0.03). This was such a fast event, it seems like every male athlete was quite competent at these skills, so there was little variance.

ANOVA simply told me that there was statistically significant differences between clusters, but not where these actually occur in the clustering. To determine this, I used the Tukey range test, which compares all pairs of means for a given independent variable (i.e. the event scores). Using these statistically interesting differences, I summarize the cluster characteristics below.

Cluster	Characteristics
Cluster 1	Fast runner, not a strong lifter, slow through event 3 and 4, and average in event 5.
Cluster 2	Fast runner, average lifter, fast through events 3, 4, and 5. All around athlete, with speed focus.
Cluster 3	Average runner, heavy lifter, fast through events 3, 4, and 5. All around athlete, with strength focus.
Cluster 4	Slow runner, weak lifter, slow through events 3, 4, and 5.
Cluster 5	Average runner, low to medium lifter, slow in event 3, fast in event 4, and average in event 5.
Cluster 6	Slow runner, medium lifter, slow in event 3, fast in event 4, and average in event 5.
Cluster 7	Slow runner, average to heavy lifter, average in event 3, fast in event 4, and average in event 5. Strong, but needs to work on running.

The following table gives a break down for each cluster, the highest placement for an athlete within that cluster, the lowest placement, the average and the size of the entire cluster.

Cluster	Highest	Lowest	Average	Size
Cluster 1	24	45	35	4
Cluster 2	1	23	11	13
Cluster 3	6	15	10.83	6
Cluster 4	42	49	46.4	5
Cluster 5	13	43	28.6	9
Cluster 6	29	41	36.4	5
Cluster 7	20	40	30.3	7

That's the raw data, but is there anything interesting we can say about this? It turns out there's a number of interesting results.

First, the top 13 athletes all fall into cluster 2 or 3. Also, from the top 6 athletes (the ones going to the games), 5 of the 6 are from cluster 2, while one is from cluster 3 (DJ Wickham). Based on this, I'd guess that the 5 events favored an all around athlete with speed more so than an all around athlete with a strength focus. If you look at the events, most did not involve heavy weights. It could be that with a different balance in the events, for example, a 165 clean in jerk in the last event instead of 135, the cluster 3 athletes may have been more likely to dominate the top 6.

One very obvious result from this is that you clearly need to be a great all around athlete to crack the top 15. With 5 events, your weaknesses are going to get exposed. Everyone in this competition is most likely a great CrossFitter, so it's extremely difficult to come back from even one poor score.

I think it would be interesting to take this analysis further by looking at clustering data from other regionals and seeing the similarities between the athletes that made the games. It would also be interesting to use the analysis to compare the programming for the various regionals. What regions favor certain types of athletes?

Anyway, that's all I got for now. Hopefully some people find this interesting and I hope no one that was included in the analysis is offended by my categorization. There's some subjectivity to the whole thing, so don't take it too seriously :-).

OntoGraf Release

2010-04-12T11:22:00.000-07:00

I have put up an initial release on the OntoGraf visualization plugin for Protégé 4.1.

Also, I created a demonstration video. There's a high resolution one available here and I also uploaded a version to YouTube, which you can watch below. The YouTube one is a bit blurry unless you switch it to the 720 HD version.

OntoGraf - Visualizing ontologies

2010-04-06T09:17:00.001-07:00

This is my first post in a while. Unfortunately real life has been interfering with my blog updates of late.

On the research side of things, my Change Analysis plugin has been released for a while and I've been making minor updates. I also started working on a web-based version, which I have running locally, but have not released yet.

Recently I helped out at the Protégé short course. The short course is a three day course teaching the basics of ontologies, OWL, and how to use Protégé to create/edit an ontology.

The "students" learn about the currently three different flavors of Protégé. There's Protégé 3.4, which all of my ontology-related work has been integrated with. There is also Web Protégé, which was developed with GWT and is a light-weight ontology editor. Finally, there's Protégé 4, which was a complete re-write of Protégé 3.

I hadn't had much experience with Protégé 4 prior to the short course, so I actually learned a lot about its features and I am significantly impressed. It has a much cleaner interface and is a whole lot faster. Protégé 4 is built on top of Equinox, the Eclipse implementation of the OSGi spec. The plugin architecture is very similar to developing plugins for Eclipse.

As a developer, it takes a bit more work to get up and going with your Protégé 4 plugin versus Protégé 3, but I think the modularity that OSGi provides is worth the extra effort.

The other major difference between the two versions of Protégé is that Protégé 4 supports the OWL 2 specification. It fully supports the OWL API, and in my opinion there is a much clearer separation between the ontology-specific classes and the user interface.

That being said, Protégé 4 is lacking in plugins in comparison to Protégé 3, especially for visualizing the structure of the ontology. As a result, I decided to port and improve an old plugin I wrote for Protégé 3 to this new version.

The new plugin is called OntoGraf. The basic view shows the ontology tree on the left and a searchable interface to the right. The left and right panels are synchronized. The graph shown below is part of the Pizza example ontology. A radial layout has been applied and I have zoomed the graph out. When the graph is zoomed out, moving your mouse over a node will show that node at its normal size so you can read it (e.g. ThinAndCrispyBase below).

The plugin hasn't been released yet, but I plan to release it soon.

Repainting a JTree

2010-03-12T16:28:00.001-08:00

This is just going to be a quick little post about how to get around redraw issues when you need to repaint a JTree in Java. Sometimes when you force a repaint with a JTree, the nodes are rendered with a "..." at the end of the node text (see picture below). This happens when the text that needs to be rendered is outside the bounds of the Node object being painted. This really only happens when the text that needs to be rendered has changed between the last rendered state and the new repaint.

I've run into this issue a number of times due to all my various JTree hacking in projects like CogZ, ZoomableJTrees, and now again in my Change Analysis plugin.

Typically to force a JTree to repaint, you might do something like this:

myTree.invalidate();
myTree.validate();
myTree.repaint();

This code will force a re-rendering of the JTree object, but if the node sizes needed to be re-calculated, the tree will end up displaying as in my screenshot above. So, my trick to get around this issue is to actually change the JTree row size before I call the repaint, this will force the JTree to recalculate all the node size bounds.

// call setRowHeight to force the sizes to recalculate
myTree.setRowHeight(DEFAULT_ROW_HEIGHT);
// repaint this puppy
myTree.repaint();

It's a bit weird, but it works :-).

Digging into ontology change sets

2010-03-10T14:50:00.000-08:00

Lately I've been spending more time delving into some analysis of the changes being made to different ontologies by different editors and less time coding my change analysis plugin. One specific thing I have been investigating is how many times multiple editors actually modify the same artifact in an ontology and within that set, is there anything interesting going on with those potentially conflicting changes?

For the programmers possibly reading this, you can think of the ontology as a software project. The artifacts of interest would be individual files.

So far, in the three projects I've looked at, two of the three have very few multiple editors making changes to a single term. Unfortunately, I don't really have enough data to say anything conclusive yet about this observation. Once I have a longer history for a project, I'd like to see if is the general case. Also, I'd like to investigate what kind of roles people take on as editors. It would also be interesting to see what terms stabilize, with regard to their edits, over time, while I suspect others will perhaps be in constant evolution.

During my initial analysis, I did come up with another feature for my plugin. While using the concept change analysis view that I talked about in my last post, I found sometimes I wished I could see the global impact that a single author or a set of authors had.

To support this, I added a filter configuration dialog, which allows the user to filter the concept change tree to display only changes by certain authors or between certain date ranges. The date range feature will be very nice down the road when I have a longer history of changes. I'll be able to see where edits are taking place for specific time periods. I think, like software development, there will most likely be "hot spots" for changes over short periods of time.

Below is an example of applying the author filter. The first image shows the filter dialog where I've chosen two authors to be filtered. Once I apply the filter, all changes by these authors will be hidden and the change counts in the tree will update. The two side by side images show the before and after screenshots of the concept change view. As you can see when you compare the change counts in the tree between the two views, the two authors that are filtered are responsible for HUGE amount of changes in comparison to the others.

ChangeAnalysisTab Released

2010-03-05T11:04:00.000-08:00

The Protégé plugin that I have been working on, which I mentioned in my last few posts, has been released. It should be included in the Protégé build on Monday, but for now, people can download it from my website.

The original purpose of the plugin was really to help me with analyzing the changes being made to an ontology throughout the ontology's evolution. However, after showing some demos, people thought other Protégé users might be interested in also having access to this information.

One of the views I like the most is the one shown in the screenshot below. On the left it shows the normal class hierarchy for an ontology, except that I've extended the tree to show how many changes exist within a branch and for a given term. The values in bold represent changes that have been made to that term, while the values in gray represent the number of changes that have been made to all subclasses within that branch.

In the screenshot, you can see that there's been 2091 changes made within the "ICD Categories" branch (circled in red). However, what's interesting is that 73% of these changes or 1534 changes, have occurred all within the "Diseases of the skin and subcutaneous tissue" branch (also circled in red).

This is useful because it allows the managers of the project, or anyone that is interested, really see where the ontology's development is most active. In the future, I'd like to add in some controls for specifying a date range, that way you can see where the development is most active today, or say 6 months ago, or 2 years ago. I'm holding off a bit on this feature as all the sample projects I have with tracked changes are only starting their development so such fine grain control is unnecessary at the moment.

More fun with JFreeChart

2010-03-01T10:38:00.000-08:00

As mentioned in my last post, I've been developing a new plugin for Protégé and I've been using the JFreeChart library for some of the visual components. Last time I discussed some issues with JFreeChart enforcing it's column and row keys to be Comparable, but then not actually using the compareTo method. I think I have figured out what the intention was behind this design.

In some types of charts, the library will allow you to sort the domain axis, so I'm guessing it uses the Comparable for this functionality. Unfortunately, the DefaultCategoryDataset class that I am using to create my area charts does not support this, but I want my domain axis to be sorted by ascending date.

I spent some time looking at the internal code of the library to try to figure out if there's a way I could do this. It turns out that the DefaultCategoryDataset uses a DefaultKeyedValues2D class to store it's actual data and this class supports a sort row keys option. However the DefaultCategoryDataset initiates the internal object with this always set to false. There's no public methods to access to the internal data object, so I can't modify it at runtime.

Also, it doesn't appear that the code for sorting the key values really works as I would assume it should. Here's the internal code from the DefaultKeyedValues2D class:

row = new DefaultKeyedValues();
if (this.sortRowKeys) {
   rowIndex = -rowIndex - 1;
   this.rowKeys.add(rowIndex, rowKey);
   this.rows.add(rowIndex, row);
}

I would think that this sortRowKeys option should rely on the fact that the rowKey is Comparable, and should insert the new rowKey into the rowKeys list based on a comparison to the already existing keys. Instead all it does is insert the new rowKey at the beginning of the rowKeys list. This happens because of the line rowIndex = -rowIndex - 1. In this case, rowIndex will initially be equal to -1, the equation is -(-1) - 1, which is 1-1=0.

So, even if I copied the internal code for DefaultCategoryDataset into my own class, and modified it's initiation of DefaultKeyedValues2D to set the sort key option to true, it still wouldn't actually sort the keys properly!

In the end, I went with a somewhat hacky solution that I knew would work. While I process my data to display in the chart, I store all the unique dates that I encounter in a sorted set. Then, before I add all my values to the dataset, I make sure the first entry contains all the unique dates in the proper order. This forces JFreeChart's DefaultKeyedValues2D class to actually insert the row keys into its internal list in the proper order.

Here's the hack:

// get the first entry in the list
Entry<String, Map<Date, Integer>> firstEntry = 
    authorToChangesByMonthMap.entrySet().iterator().next();
   
// total hack to get the row keys to show up in sorted order
for(Date date : allDates) {
    // check to see if the key exists, if not, create it
    if(firstEntry.getValue().get(date) == null) {
      // dummy entry
      firstEntry.getValue().put(date, 0);
    }
}

As for the plugin, I am planning to include it in the Protégé release that is scheduled for this week.

Blog changes and a real update

2010-02-24T10:59:00.000-08:00

For anyone that actually reads this blog (yes, there is a handful), you may have noticed some changes. I decided to do a pseudo "re-branding" since I am now going to include posts about my latest academic work, and not just posts related to programming contests.

As I mentioned in my last post, I've now been at Stanford for almost two weeks. One of the projects I am involved in is with the next revision of the International Classification of Disease (ICD-11). Researchers/developers at Stanford have been collaborating with the World Health Organization to develop software that will allow members of the medical research community to collaboratively develop ICD-11 in a somewhat open, crowd-sourcing manner.

Members of Stanford's Protégé team have extended the web-based version of Protégé to help support this effort. For those unfamiliar with Protégé, it is a freely available ontology editor. If you don't know what an ontology is, for the purposes of this post, you can think of it as a taxonomy or hierarchy of terms.

Now, one of the big issues with this project is managing this collaborative effort. There could potentially be all kinds of simultaneous editing, conflicts to resolve, and issues with simply understanding the evolution of the terminology. What I have started doing is analyzing the changes that have been made to the ontology so far.

I have a bunch of researchy-type questions I want to answer through this analysis and at first, I thought I would just write some scripts to pull out the data. However, since this is so exploratory, I thought it might be more interesting and potentially useful to develop a tool that would allow me to explore the data. I started writing a Protégé plugin that provides different analysis views based on the tracked changes of a given ontology (in this case, the ICD-11 ontology).

For one view in the plugin, I wanted to display changes made to terms over time. This way I could visually see how a term has evolved over a certain time period. I wanted this view to be similar to the NameVoyager applet. To create the area chart effect that I needed, I decided to use the JFreeChart library, which I have used a few times in past projects.

Creating the view was reasonably simple, but I did run into one annoying technical detail that took a while to resolve. With JFreeChart, chart's use dataset objects to hold the data the chart is to represent. For my area charts, I used the DefaultCategoryDataset, which takes three parameters for adding new values; the actual numeric data value, a row key and a column key.

For example, in my case, I want to show term changes over time, so my x-axis is going to be months, y-axis the number of changes, and I want to have a different data series or category for each term. Thus, in my DefaultCategoryDataset, the row key is the term name, while the column key is the month and year.

The pesky technical issue was that I wanted my month and year to display like "July, 2009", but sorted along the x-axis based on a date comparison. The row and column keys can be any Comparable class, so I created my own DateKey class that implemented the Comparable interface. For displaying, JFreeChart simply calls the toString method on the row and column key objects, so in my DateKey class, I format the data object as I want in the toString method, but in my compareTo function, I call the Date class compareTo function.

Based on the JFreeChart API, I assumed this would work, but I kept getting multiple entries for "September, 2009" for each term displayed in the visualization. I quickly realized that the compareTo function is never called. Eventually, after looking through the JFreeChart source code, I found that they store their row and column keys in a list. To determine if the key already exists, they call the list's indexOf method. This method does not use the compareTo function, it performs a linear O(n) search using the equals method.

So, in order to make my DateKey work, I had to implement an equals method and hashCode function. JFreeChart's reliance on these methods rather than the compareTo function seems like a bug in their library. If compareTo is never called, then why must the row and column key's implement Comparable?

Here's a couple of screenshots of what the view turned out to look like.

Here's the final code for my DateKey class.


public class DateKey implements Comparable<DateKey> {
 private static final DateFormat formatter = 
      new SimpleDateFormat("MMMMM, yyyy");
 private Date key;
 
 public DateKey(Date key) {
  this.key = key;
 }
 
 public Date getKey() {
  return key;
 }
 
 public String toString() {
  return formatter.format(key);
 }
 
 public boolean equals(Object o) {
  return key.equals(((DateKey)o).getKey());
 }
 
 public int hashCode() {
  return key.hashCode();
 }

 public int compareTo(DateKey o) {
  return key.compareTo(o.getKey());
 }
}

So long UVic, thanks for the memories!

2010-02-22T13:59:00.000-08:00

It's been a few weeks, but my time at the University of Victoria has come to a close. Last Fall I accepted a job at Stanford University, which started February 8th. I've been in California, working in the Center for Biomedical Informatics Research Group for about a week and a half.

I plan to stay somewhat involved with the UVic programming teams. John Hawthorn and Tyler Cadigan have taken over the weekly meetings as well as recruitment. I've been helping through e-mail whenever I'm needed. In the Fall I plan to help facilitate practice sessions between UVic, UBC, SFU, and Stanford as was done last year.

I'm not sure what my plans are for my blog right now. I'm not sure whether I'll have that many programming team related updates now. I may start mixing in some discussion about the projects I am currently work on at Stanford. The coding I am doing here is more technical, engineering and research orientated, rather than specifically problem solving. However, it may still be of some interest.

BC Winter Programming Contest

2010-01-18T09:13:00.000-08:00

The BC Winter Programming Contest took place this past weekend, January 16th. You can check out the scoreboard here. It was an excellent competition, only one student, Jaehyun Park from Stanford, solved all 7 problems, and almost all students solved at least one. Brad Bart from SFU did most of the work to write problems, solutions, and organize everything. Sonny Chan (coach of Stanford) and myself made small contributions with some solution validation, test case generation and I wrote one of the problems.

There were 5 pairs of UVic students competing and one UVicer competing remotely while on co-op with Research in Motion in Waterloo, ON. The top UVic team was Dan Sanders and John Hawthorn with 4 problems solved. They finished 6th overall and were the 2nd overall amongst BC students. They were in 3rd or 4th about half way through the competition, but got stuck trying to debug wrong answers on problems C, D and F for the second half of the competition. In the last half hour, students from SFU solved their 5th problem and jumped ahead of them. Scott Porter, competing remotely by himself, was the second top UVic student, placing 20th overall.

Many of the UVic students that participated were completely new to competitive programming. They had really no idea what to expect, so I would like to congratulate all UVic students that came out and gave it a try. These competitions can be very intimidating and stressful the first few times, so I'm really proud of everyone that stuck it out for the full 3 hours. Hopefully you'll keep practicing and compete in the ACM competitions next Fall.

Problems:
A - This was the simplest problem in the set. You had to read in words and determine whether they were writable in Hawaiian. This amounted to determining whether the word contained only letters from the Hawaiian alphabet. The catch for some solutions was not properly handling the stopping condition. The problem states that the last test case ends with the exact string "Ahuihou". Some students matched against this word ignoring case, which is wrong.

B - In this problem you have to read in a number, up to 30 digits in length, and determine what bases it can be rewritten in such that it is evenly divisible by 7. If the number is never divisible by 7, you have to print "Always unlucky.". It turns out that you only need to test bases up to base 16. All other valid bases will be one of these bases plus Y*7 (Y >= 1). For example, if base 9 works, then base 16 works, 23, 30, etc. You can easily do this in Java using the BigInteger class. Python probably also has something equivalent.

C - This was the hardest problem in the set, and only one student managed to successfully solve it. You are given a grid of diamond shaped cells. You are also given a metal detector that can probe a gridsquare and give you one of 8 compass directions. Compass directions North, East, South, and West are only valid responses if the treasure you are hunting is located along that exact path. Otherwise, you get a direction like Northwest that simply narrows your search to a region of the grid.

You can solve this problem using dynamic programming or memoization. A sub-problem can be described by the grid size, m and n. However, there are some tricky conditions for the recursion for certain values of m and n.

D - This is the problem I wrote. The problem describes a game with colored marbles on two tracks, one horizontal and one vaertical. You can rotate either track to move marbles from one track to the other. You are given an initial configuration of the tracks and you have to figure out the minimum number of moves (i.e. rotations) such that you get all the blue marbles into the middle square. It turns out that there's not that many valid starting configurations.

One approach to solve the problem is to start by representing the winning condition as two bit strings of length 18, "111100000111100000" and "100000111100000111". Then using these strings as a representation of state, you can breadth-first-search across all possible valid moves to generate any potential starting position that takes one move to reach the winning state. Continue to do this for all of these states to get all configurations 2 moves away. Do this until you can't find any new states and store everything in a table. You can now simply look-up the answer based on the read in configuration. If the given starting configuration does not exist in the table, then it is impossible.

E - In this problem, you are told that two flat oranges rest at the bottom of a fruit bowl shaped like a parabola. You have to determine at what value of y the fruit's centers are located at. Applying some geometry, you can work out an equation to calculate y given some "guessed" value for x. To guess a value for x, we can use binary search and terminate when the high and low value become significantly close.

F - This problem describes a bad measuring device that is only precise within 1 foot. So any measurement has value V feet plus or minus 1 foot. The distance between floors in a building are measured with this device and you have to determine whether these measurements are consistent or inconsistent. Consistent means that the measurements are possible, inconsistent means that there's no way they could be right, there is some sort of conflict between two or more floor distances.

We can represent this problem as a graph. All floors represent nodes in a graph and two floors, a and b, have directed edges between them if there is some measurement d given in the problem input. The edge from a to b can be assigned weight 1-d (the minimum possible value) and b to a has weight 1+d (the maximum possible value). Once the graph is constructed, the measurements are consistent provided there are no negative cycles in the graph. To detect negative cycles, you can apply the Bellman-Ford algorithm.

G - This was the second easiest problem in the set. You are given numbers that represent the values of odd-indexed nodes in a full binary tree. You have to figure out the values to the even-indexed nodes. You can represent the tree using a one-dimensional array. Most people learn this in undergraduate data structures courses. Then it's just a matter of filling in the array, where you use the odd-indexed values to calculate the even-indexed values. Instead of an array representation, you could also implement your own binary tree with left and right nodes, and apply recursion to fill in the tree.

BC Winter Programming Contest Practice

2010-01-14T10:09:00.000-08:00

The BC Winter Programming Contest is coming up this Saturday, January 16th. I've been making the rounds to different classrooms, trying to encourage some new students to give it a try. Last night I held a three hour practice session and luckily a few new faces showed up to give it a go. I picked five problems from the 2009 Greater New York Regional programming contest. I picked this set as I knew a lot of teams solved all the problems, so I figured it would have some pretty manageable problems for complete newbies.

The students worked on problems A, C, D, H, and I. Most students solved A and D, and John Hawthorn was the only one to solve C.

Problem A is quite straight-forward. You need to read in a list of 10 numbers and print the 3rd largest value. Probably the fastest way to code this is to read in the 10 numbers, sort them and print the 7th number in the array. This should only take a few lines.


int P;
cin >> P;
while(P--) {
  int num;
  cin >> num;
  vector<int> t(10);
  for(int i = 0; i < 10; i++) cin >> t[i];
  sort(t.begin(), t.end());
  cout << num << " " << t[7] << endl;
}

The second easiest problem was problem D. In this problem you have to read in a list of numbers and for every odd-indexed number, print the current median of the list. The key here is to make sure your sort is fast enough to get under the time limit and to follow their output specification exactly. Most students made mistakes with the output format. The built in sort routines in C++ or Java should be fast enough for this problem.

Problem C is a little tricky to understand. The problem describes a scenario where you drop glass balls from different floors. The goal of dropping these balls is to determine what the last floor is that you could drop a ball from without having it break. In the classic version of this problem, sometimes involving eggs, you have to figure out the optimum strategy for this, which is a variation on binary search. However, in this problem they want you to figure out what the minimum number of drops is in the worst case. This means, if we choose the worst strategy, what is the best we can hope for?

To solve this, we can try to enumerate all possible scenarios given the number of balls we have and the number of floors we can potentially drop a ball from. We can enumerate these states through recursion over two variables, our current number of balls left and the number of floors left. We also need to use memoization to store our states so that we don't repeat states that we've already computed. Finally, we need to determine what the conditions are for this recursion. There is basically two cases, we drop a ball b from a floor f and the ball breaks leaving us with one less ball and knowing that we need to search floors below f, or the ball does not break, meaning we need to search floors above f. From these two scenarios, we want to keep track of the worst result, but the minimum overall value.


int rec(int balls, int floors) {
  if(balls == 1) return floors;
  if(floors == 0) return 0;
  if(floors == 1) return 1;
  
  // we already calculated this one
  if(memo[balls][floors] >= 0) return memo[balls][floors];

  int best = floors;
  for(int f = 1; f <= floors; f++) {
    // ball breaks on this floor, one less ball
    int r1 = rec(balls-1, f-1);
    // ball does not break, search above
    int r2 = rec(balls, floors-f);
    // keep track of the worst result
    int result = 1 + max(r1, r2);
    // keep track of the minimum for all worst cases
    best = min(best, result);
  }
  memo[balls][floors] = best;
  return best;
}

Problem H states that you need to find all lattice points contained within a convex polygon. All coordinates for the lattice points and the polygon vertices are integers. There's several ways you could solve this problem. One way is to do point in polygon tests to determine which lattice points are contained within the polygon. To do this, you can calculate all the potential lattice points by determining the maximum x-coordinate, maximum y-coordinate, minimum x-coordinate and minimum y-coordinate based on all vertices in the polygon. Then, you can loop from the minimum y to maximum y, minimum x to maximum x, and test each point.

Finally, problem I describes a puzzle with 7 positions, 6 of which contain a letter and one position is blank. A valid move is to move a letter from its current position into the blank position. The goal is to convert the game into the winning state as described by the problem statement. The problem states that given an initial configuration, print out the minimum number of moves along with the solution to reach the win state or print NO SOLUTION if it is not possible.

This is a simple example of a "Searchy type problem" that I had blogged about before. The positions can be represented as nodes in a graph, edges exist between the nodes based on how the puzzle is described. You can then perform a breadth-first-search over the graph, where a new state for the queue is added for each valid movement of a letter to the current blank space. Also in the state, you need to keep track of the path you took to reach that state. Once you find the winning state, print the path and length.

How to setup and run your own programming contest

2009-12-17T09:20:00.000-08:00

It's been a couple of weeks since my last post as there's been less going on with the programming teams lately due to exams. This post is about how to run your own programming contest, but first, I thought I should mention that all the UVic team members were recognized and awarded Outstanding Leadership Awards last night at the computer science department Christmas party. There's also been talk about establishing some kind of yearly high school programming competition in BC. It would potentially be great for recruitment, be a good way to get young people interested in computer science, and hopefully keep the top BC students in BC.

Ok, now onto the topic: how to setup and run your own programming contest.

Before I get into the details, I'll just mention a few bad experiences I have had as a competitor. You may not think organizing a contest would be that difficult, but it can be quite a disaster if there isn't much care put into it. I use to compete in the Northeast North America regional. This is one of the few regions in North America that has preliminary rounds. Between all the contest sites, there is no consistency in the problem writing style or the submission software used. Year to year, the contest submission software changes and not always for the better.

In one particular preliminary contest, every team had to use a Windows system, but telnet into a Unix box, and use a single non-resizable terminal for coding and submitting. Even more surprising was that the problems were not printed for the teams before the contest and teams had to read the problems directly on the machine. We were told that we could print screen the problems piece by piece if we needed print outs.

Since only one terminal was supported, you would of course be forced to switch between your code editor back to the single terminal for compiling, running, and submitting. The submission software consisted of shell scripts, solution judgements were written into a file, which you would need to periodically check.

Many of the input files had been created on a Windows machine and ported to Unix, which led to strange end of line and end of file characters. Finally, there was a number of errors in both the judge's test cases and the problem specifications. Not surprisingly, over half the teams solved nothing, and we came in second with a grand total of three problems solved.

One of the other issues with the preliminary round was the problem writing inconsistency. This may have been due to lack of experience from the problem writters or lack of care from the organizers, but each problem would usually be formatted completely different. Some looked as if they were typed in Notepad, with no input and output specified, sometimes without any sample test cases. Others may be a PDF file, written in Latex. Usually if there was some description of the input and output, the constraints of the problem would not be specified.

Now that the horror stories are complete, as for running your own contest, there are several options and it's not really that complicated, but is perhaps a little daunting for those unfamiliar with competing. To start with my own experience, I've written problems for, acted as judge, organized, and ran about half a dozen contests, both at UVic and the University of New Brunswick (UNB). Probably the most difficult part, besides getting students interested in coming out for such an event, is coming up with the problem set, judge's inputs and outputs, all without major errors.

The goal with most ACM-style contests is to create a problem set such that every student/team solves at least one problem, no student/team solves all the problems, but all problems are solved by someone. This is very tricky to pull off. If the problems are too simple, then you may end up with a situation like this year's Greater NY Regional where nine teams solved all the problems. This is usually a sign of a poorly designed and potentially unfair contest. It potentially rewards the fastest coders for simple problems rather than the best problem solvers.

One of the major issues I've struggled with in any contest that I've run is the large variance in skill level between the few exceptional students I had access to and the less experienced students. You don't want the more advanced students solving everything in the first two hours, but you don't want to make the problem set so difficult that the majority of the students leave frustrated and embarrassed. I've been both successful and unsuccessful at achieving this balance.

For example, in the last contest I ran at UNB, the top two students solved 6/7 problems, two students solved 2, two solved 1, and everyone else solved nothing. I felt quite bad judging this contest, and many of the students left frustrated. However, the first UVic contest that I organized, had a much better balance (scoreboard).

In individual contests, I have usually tried to have between 6 and 7 problems, with at least one very simple problem to get everyone started on the right foot. I also usually organize the problems roughly from easiest to hardest, as a lot of inexperienced people will start with the first problem regardless of its difficulty. I also usually try to have the second or third easiest problem be something that is easy to understand conceptually, but may take some time to implement. My goal here is to give less experienced students something to work on and potentially solved, but it will keep them busy for a while. Finally, I try to mix in some shorter to code problems that require a bit of insight.

If you are simply trying to set up a contest environment for team practice, then you can probably skip the problem writing stage. If you go to the regional page on the ACM ICPC website and follow the links to various regionals, many will include their problem set, judges input and output, and solutions. You can use these files to create your own practice contest environment.

In all the contests that I've organized, I've used the PC^2 software for problem submission and judging. I recommend using version 9, as it's much better with firewall issues. PC^2 is quite simple to set up. The software is written in Java, so it runs on most platforms. It has several different programs, a server, scoreboard, judge, admin, and client. You start by running the server, and all other programs connect through the server. Configuration is as simple as modifying a config file to point to the server location. The administration control panel is used for creating accounts, inputting problems, and configuring how the judgements will run. Judging can be done automatically or semi-automatically.

I always create a judge's set of input and output, and configure PC^2 with that information for each problem. I also use automatic judging as a guide. If the automatic judge gives me an accept, I usually take it. If there's a different answer, I'll do a side by side comparison between the submitted program output and my judge's output just to make sure.

The client software is what the students or teams use to submit their solutions. They can select the problem to submit under, the language of the source code, and the source file. Submissions are put into a queue on the judge's side. The client software also supports clarification submissions, which are questions about the problem set that you can send to the judge.

The scoreboard is very simple, it writes the current scores into different html files. The summary.html is the best view. The admin software allows you to configure when the scoreboard should be frozen, typically for the last hour or half hour in a contest.

There are other contest systems out there. CodeChef, which I wrote about in my last post, will host contests for you. One of the advantages of using PC^2 is that it is the system used both at the world finals and at a lot of the regional level contests so it exposes your team to the system early. It is very simple to use, so it's probably not a huge gain, but it may help a bit :-).

How can I compete?

2009-11-30T20:07:00.000-08:00

I sometimes get questions from people asking me about how to get into competition programming, how to practice, how to use the various problem archive websites and so forth, so I thought I'd write a blog explaining how it all works. Most of the practice and competition sites out there have very good guides for this very thing, so this post will mostly give a short description of your various options, what I think of them, and it will hopefully be useful to those that are currently in the dark about this kind of thing.

Before I get into describing the various online options, if you're in university or high school there is two main competitions that you could potentially get involved in. For high school students this is the International Olympiad of Informatics (IOI). I've never been involved with this competition, so I don't know a lot about it. I do know that it is a world-wide competition and up to four individuals from a country can compete. There's typically a national round first in order to choose a country's four members. If you're in high school and have some programming skills it might be something to consider. I'd first try finding some information about previous competitors from your country and find out how to get involved.

University students can compete in the ACM Intercollegiate Programming Competitions (ICPC). This is the largest competition of its kind and the type of competition I've been primarily involved in as a competitor and coach. Participants compete on teams of three with a single computer for five hours. The teams that solve the most problems in the least amount of time win. Recently, the top 100 teams from around the world meet to compete against each other in the world finals.

To qualify for the world finals, you have to place high in a regional level competition. The world is divided into around 40 regions. In North America, usually you have to be one of the top two teams in the region to move onto the finals. If you're in university, find your region and see if your school has a team. If they don't, then I encourage you to get involved. You just need a faculty member to sponsor you and hopefully they can help you get whatever funding is necessary for travel.

Ok, great, you're sold on the idea of competing, so how to practice? There's several great websites out there that can help. Most of them follow a similar format; problem statement, with description of input and output formats, and several example test cases. You submit to an online judging system, usually through a form, and the online judge compiles your source and runs the executable against a hidden set of test cases. If you pass everything, you solved the problem. Be very careful when you start, you need to match the specified input and output formats exactly. Even if you are off by a period or whitespace, your answer will be wrong.

UVA Online Judge - This site contains thousands of problems and an online judging system. To use the site, simply register, then pick a problem, solve it offline on your own computer, and when you're satisfied, submit it through the UVA online submission form. You'll get an email indicating whether the problem was accepted (yay!) or if your code produced a wrong answer, time limit exceeded, runtime error, or compile error. The site also hosts online competitions, however, watch out for the timezone. One disadvantage of the site is that the problems are not really organized by problem type, so it's hard to practice certain types of problems. However, if you search the message board for say "dynamic programming" you can often find someone listing problem numbers of this problem type. The site supports C, C++, Java and Pascal solutions.

ACM Live Archive - This site is similar to UVA and run by, I believe, some of the same people. It contains previous problems from many of the regional competitions and world finals. Like UVA, you can submit solutions directly through a web form. There's also a message board for finding help, although it's not nearly as populated as the UVA message board. One major issue with this site is they only support Java 1.0, which basically means, they don't support Java.

Project Euler - I've known about this site for a while, but only recently started using it. There's several nice things about the site. The first is that the problems are listed in increasing difficulty, so problem 1 is suppose to be the easiest and the latest posted problem (currently 266) is the hardest. The other really nice thing is that you only submit an answer to a problem, rather than source code. This allows you to solve the problem in any language that you are comfortable with. It's a great way to experiment with learning a new language. The problems tend to often be math oriented. It's a great resource, but since it is a different style than the ACM or IOI competitions, it may not be as good a representation of how it is to compete in those particular competitions.

CodeChef - I just discovered this site after a friend sent me a link. It's a fairly new competition website, similar to the UVA online archive. They have a competition every month, where 6 problems are posted and competitors have 10 days to try to solve them. You earn 1 point for each solved problem. There's also team competitions, but I am not sure how often they are organized.

Problems are organized by easy, medium and hard. There seems to be a great community contributing to the site. The social aspects of the site are tightly integrated with the problem sets and contests in comparison to the older websites that simply have message boards. One other nice thing is that it supports a wide range of languages. Finally, if you do well, there's prize money :-).

TopCoder - This is one of the largest competition sites available. Anyone can compete, and there's typically two or three algorithm competitions a month (SRM - single round matches). Once you sign up, you can run the competition applet and try problems from previous competitions. There's several key differences in comparison to ACM style competitions.

First, there's two divisions, Division I and II, based on your membership rating. You earn points by competing, people with ratings less than 1200 compete in Division II, everyone else is in Division I. So, when you first sign up, you'll be in Division II. If you do poorly in a competition relative to other people with similar ranking to you, then your rating can actually drop.

Second, there's always 3 problems, each with different point values. The faster you solve a problem, the more points you get. There's an easy, medium, and hard problem, the more difficult the more points you can potentially get. Third, unlike ACM contests where after you submit you get a judgement about your problem, on TopCoder, submissions are not judged until after the competition. If you decide to re-submit, you lose 10% of your original point value. Unlike, ACM contests, you do not have to worry about writing input and output parses based on some described format. Typically, you are asked to write a specific class with a method that takes certain parameters and returns a certain parameter.

Finally, contests only last an hour and 15 minutes. After the coding part of a competition, there's a 10 minute break, and then a challenge phase. During the challenge phase, you get to look at other people's source code and challenge their solutions. If you make their code fail, you get extra points and they lose whatever points they would have potentially scored. Once this phase is complete, the judge's hidden input cases are run against all submitted programs. If you fail any cases, you lose whatever points you accumulated for that problem.

There's several great things about training on TopCoder. There's lots of competitions, so it gets you use to competing. Because you really only get a single submission, it can help you improve your accuracy. You can see other people's source code, so it can be a great way to learn how to solve a problem or learn a better way to solve a problem. There's also editorials after each SRM describing how to solve the problems. The problem archive is nicely organized and searchable based on different criteria like difficulty and problem type (DP, greedy, search, etc). Also, if you are very talented, you can earn a substantial amount of money competing on TopCoder. Many contests and tournaments are organized by companies as a way to recruit potential employees.

This post is already quite long, so hopefully that's enough to get any newbies out there pointed in the right direction. Next time, I'll post about how to run your own competition and provide some suggestions for how to get things going at your own school.

Searchy type problems

2009-11-26T11:11:00.000-08:00

A lot of problems in the ACM and TopCoder competitions can be solved using a general search technique like breadth-first search (BFS). Many BFS type problems are represented with an initial grid and you want to determine whether you can achieve a certain state or grid configuration, possibly in the minimum number of moves. These problems are very popular and can vary in complexity, however, the general problem solving principles remain the same.

You can usually determine whether BFS is the right approach for a problem of this sort by first checking the bounds of the grid. Most of the time, the grid will be less than 20x20. Secondly, you need to determine how to represent the current state of the problem. You can think of this state as a node in a graph. Finally, you need to determine if one state can be transformed into a subsequent and valid state through a move with a cost of one. You can think of these moves as edges between your nodes. Another hint is that many of these problems can be classified as single player game problems.

Let's consider an example. In the problem Traffic!, a simple game is described where are given an initial puzzle configuration consisting of blocks of varying sizes. The goal of the game is to figure out how to remove the white piece by moving the various puzzle pieces and repositioning the white piece so that it slides through the opening in the puzzle. In the problem you are asked to find the minimum number of moves to accomplish this task.

So, let's go back to our criteria for determining whether BFS is a valid approach. First, the grid is of size 6x6, so that's well within our heuristic 20x20 bound. Second, the state of the problem can be represented as a list of the current locations for each puzzle piece. A move in the game consists of moving a single puzzle piece any number of open positions horizontally or vertically. Horizontal pieces can only move horizontally and vertical pieces can only move vertically. Sliding a horizontal piece one spot to the right has the same cost as moving it two spots to the right, that is, it counts as one single move. Thus, we can transition from one state of the board to another with a cost of one. Finally, the problem even fits the format of being described as a single player game.

Once we've established that we can solve the problem using BFS, then the algorithm to actually solve the problem is quite straight-forward. A generic approach could be something similar to the following code:


int solve(State start) {
  set<State> visited;
  queue<State> q;

  q.push(start);

  while(!q.empty()) {
    State s = q.top(); q.pop();
    // skip states we've already processed
    if(visited.find(s) != visited.end()) continue;

    // we reached our goal, return moves
    if(goalStateReached(s)) return s.moves;

    // visit the state
    visited.insert(s);

    // try all valid moves 
    // and add them to our queue
    enqueueValidMoves(q, s);
  }
  // never reached the goal
  return -1;
}

In this case, State is going to consist of a list of the current block locations, the number of moves it took to achieve this state, and a less than operator for storing the state properly within our visited set. The enqueueValidMoves will loop over the positions in our state object and create a new state for any valid vertical and horizontal moves. We know we reached the goal state when the white piece is located in column 6.

There are a few simple tips for working on problems of this type or grid representations in general. First, let's consider a simple 0/1 matrix where from any cell i,j, containing a one, you can move east, west, north or south provided the move takes you to a cell containing a one:


110
010
111

So, the cell 0,0 can only move to cell 0,1 as this is its only neighbor containing a one. We could potentially perform a BFS where we check for valid moves as follows:


while(!q.empty()) {
  // queue consists of pairs of integers 
  // representing cell locations
  pair<int, int> p = q.top(); q.pop();

  if(visited[p]) continue;

  // process potential moves
  if(p.first-1 >= 0 && grid[p.first-1][p.second] == 1)  
    // enqueue item
  if(p.first+1 < rowCount && grid[p.first+1][p.second] == 1) 
   // enqueue item
  if(p.second-1 >= 0 && grid[p.first][p.second-1] == 1) 
   // enqueue item
  if(p.second+1 < colCount && grid[p.first][p.second+1] == 1) 
   // enqueue item
}

That will work, but all the bounds checking and if statements are kind of ugly and error prone.

To clean up this code a bit, one simple trick is to remove bound checks by padding the grid with empty cells. For example, our grid from above would become:

Now, our check just needs to verify whether a given cell contains a value of one.

Another simple tip when processing moves over a grid, like north, south, east and west transitions is to store these moves as x, y and possibly z deltas in an array. Thus, with those two simple tricks combined, our messy code above becomes:


int x[] = {1, 0, -1, 0};
int y[] = {0, 1, 0, -1};
while(!q.empty()) {
  // queue consists of pairs of integers representing cell locations
  pair p = q.top(); q.pop();

 if(visited[p]) continue;

 // process potential moves
 for(int i = 0; i < 4; i++) {
   int r = p.first+x[i];
   int c = p.second+y[i];
   if(grid[r][c] == 1) // enqueue move
 }
}

It seems like a pretty simple change, and I'm sure some will think it's not worth it, especially for this simple example where there's only four possible move directions, but once you start allowing moves along the diagonal you are up to having 8 if statements to write. The more code you have to write, especially with only slight modifications like adding one here and subtracting one there, the more probable it is that you will make a mistake that will cost you debugging time.

Other problems of this type:
439 - Knight Moves
841 - Snake
589 - Pushing Boxes
10793 - The Orc Attack

No Finals for UVic

2009-11-24T10:29:00.000-08:00

I received confirmation last night that we did not make the 2010 programming finals. The Pacific Northwest region only received two spots this year, instead of the three it received the last two years. Only one region in North America, East Central NA, received three spots. That region had over 100 teams, while our region only had 82. Also, the top four teams solved all 8 problems, whereas UVic was two problems behind Stanford.

Despite the sound reasoning behind the choice, it's quite disappointing, especially since our expectation was to make it. Goes to show these wild card spots are never for sure. I'm confident that the team will have a very good chance to finish in the top two at regionals next year. I believe both UBC and Stanford are losing some of their key members, while our team will be the same, but with one more year of experience.

The guys have taken the news incredibly well (far better than me). They are still fired up to keep practicing and get ready for next year. Unfortunately, this is my last official term working at UVic, so I won't be physically at the university next Fall to keep things going. I am starting a job at Stanford University (I know, the enemy) in February. I am going to attempt staying involved with the UVic teams remotely. I think I can still organize practices, pick problems, and help provide feedback on problems all from California. Also, if I'm involved with the Stanford teams, I can simply include the UVic folks in the practices.

Finally, despite not making the finals, both teams did incredibly well. We also managed to generate quite a bit of buzz at the university about the ACM ICPC competitions, which should help with funding next year. Hopefully more students will become interested and want to join as well.

Competitive Programming on TV?

2009-11-20T08:47:00.000-08:00

The UVic programming teams have recently been receiving some media coverage. Saanich News did an article on the guys and UVic released a small media tip about our performance at the Pacific Northwest regional competition a few weeks ago.

Also, at our last practice, A Channel News came and filmed some of the session as well as interviewed myself and some of the guys on the team. They put together a really nice piece on us, which aired last night. They took kind of a sports angle on the ACM ICPC programming competitions. Will competitive problem solving be the next big hit reality TV show? (umm, probably not :-)

I thought the piece was really well done. Jordan Cunningham put it together and did a fantastic job. A friend of mine was nice enough to record the broadcast and put it online. You can check it out below.

University of Victoria Computer Programming Team from Donald Peterson on Vimeo.

On the practice front, we studied a variety of dynamic programming problems at Wednesday night's practice and I've been organizing a fairly large practice for this Sunday. Stanford is hosting the competition and I've been coordinating with their coach about problems and various invited teams. I'm very excited about this practice as I actually managed to get some Eastern North American teams to join. McGill, University of Rochester, and St. Mary's have all confirmed that they are joining and I have sent invites to MIT, Dalhousie, UNB, and Mount Allison University.

2010 World Finals Preparation

2009-11-16T12:50:00.000-08:00

Still no word on whether the UVic Whites have made the 2010 ACM ICPC world programming finals in Harbin, China, but we're going to forge ahead with practices as if we have made it. Based on everything I could research, we have a very good chance. In the last two years, there's been 100 teams at the finals, and both times there's been three from the Pacific Northwest region. UBC^ was in the exact same position as us last year and they went, so I am confident we'll make it.

I gave everyone the week off last week, however the guys finished off all the problems from last week's regional on their own. Dan also re-coded his solution to problem D using a line sweep algorithm rather than the more direct but less efficient N^3 solution that he submitted during the competition.

As for world finals preparation, there's some key areas that the guys need to work on: dynamic programming, search problems, hard geometry problems, and coding speed. I've started compiling a list of these kinds of problems. We'll also spend some time going over previous world finals. I've also started compiling a list of algorithms and techniques that guys should learn.

For example:

Weighted matching, assignment problem, hungarian method
Linear programming, Pick's theorem
Advanced geometry techniques (line sweeping, convex hull, 3D convex hull)
String matching (KMP)
Number theory: primitive roots, extended euclid's algorithm, prime numbers

I plan to continue having two practices a week, Wednesday evenings and Saturday or Sunday. Wednesday's will be for skill development while the weekend practice will be for practice competitions, hopefully with some other Canadian teams. I will be away over Christmas to early January, so the guys will need to practice on their own then. Also, at least one of the team members will be in another city starting next term for a co-op so full team practices in January will probably be out of the question.

I plan to spend the next two Wednesday's working on the team's most obvious weak area: dynamic programming(DP)/memoization. They tend to shy away from these problems and have convinced themselves that they aren't very good at them. I think they just need more practice.

Many DP problems have very distinct patterns that give the solver clues about what to memoize or DP on. For example, recently in one of the team's practice competitions there was a problem where you had to figure out the minimum number of days that you could assign several different allergens for testing (see problem statement). An allergen can be assigned at 8am every morning and symptoms for the allergen can be detected by 8pm at night. However, if there is more than one allergen in the body, you can't uniquely identify the allergen causing the issue. Different allergens take different numbers of days to work their way out of a body, maximum of 8 days. You have to figure out how to assign the allergens (at most 20) such that all of them are detected, but such that the total number of days is minimized.

Let's take a simple example. Consider allergens that take 1, 2, 3 and 7 days. One solution could be to assign the allergen that takes 7 days first, then the one that takes 3, then 2, and finally 1. So, the first allergen is assigned and detected the first day. We can't assign the second allergen until the 6th day, and it will be detected the 8th day. Now we can assign the allergen taking 2 days, wait for it to run its course, and finally assign the last allergen. The total number of days is 11.

Alternatively, we could assign the allergen taking 2 days first, then the 7, 3, and 1, which only takes 10 days.

Just looking at the problem, it's tempting to perhaps try greedy, but as you can see from the simple example I just went over, it's not going to work. The other hint that greedy is probably the wrong approach is that there's only 20 allergens. If greedy worked, there could be 100 or perhaps 1000 allergens.

The fact that it's a minimization problem and that there are only 20 allergens are big hints that DP is the way to go. Furthermore, 20 is a curiously small number, which gives us a hint about a potential parameter to DP on. For DP, we want to compute optimal sub-problems and use those to figure out the solution to the whole problem. The sub-problem here is the minimum number of days for the assignment of X allergens. We can represent all allergen assignments in binary, where a number like 100101 means we've assigned the first, third, and last allergen so far.

When we apply a new allergen to an existing solution, we need to know how many new days we are adding to the existing solution. The only information we need in order to solve this problem is to know how many days in the existing solution the last applied allergen is active for. Together with our allergen assignments and the number of days the last applied allergen is active for, we can represent any potential solution. The solution would look something like the following (initialization code is not shown):


// allergens, D[0] is the number of days allergen 0 is active for
int D[21];
// DP array, all assignments by days last allergen is active
int M[1<<20+1][8];

// number of allergens in the current case
int k;

// try all possible allergen assignments
for(int i = 1; i < (1 << k); i++){
  // try assigning allergen j
  for(int j = 0; j < k; j++) {
    // only try j if it's not in the solution
    if(i&(1<<j)){
      // try all days active options
      for(int n = 0; n < 8; n++) {
        // days active for j
        int days_active = max(D[j] - n - 1, 0);
        // solution without j
        int t = i ^ (1 << j);
        // keep track of best answer
        M[i][days_active] = min(M[i][days_active], 
              M[t][n] + days_active);
      }
    }
  }
}

All the best solutions involving all allergens will be stored at M[1<<20-1][i] for i=0 up to i=8. You simply need to take the minimum one as your answer.

There are many problems that can be solved similarly. If you do enough of these DP problems, you start to see the tricks faster. I find sometimes drawing out the call tree or drawing out dependencies between sub-problems as a graph can be an effective means for seeing the overlap between sub-problems.

2009 Pacific Northwest Regional Programming Competition

2009-11-09T09:25:00.001-08:00

The 2009 Pacific Northwest Regional Programming Competition happened this past Saturday. The Pacific Northwest region consists of teams from universities in BC, Washington State, Oregon, Hawaii, and northern California. Approximately 80 teams took part this past weekend.

We left Friday afternoon to travel to Vancouver in a van that I rented. I felt a bit like a soccer mom, taking her 6 kids to a big tournament :-). We stayed at a hostel in a rather sketchy section of Granville Street. After a nice dinner and a horrible night of sleep, we were up at 7am Saturday morning to drive over to UBC for team registration. Everyone was tired and to make matters worse, the competition was delayed an hour.

I was extremely worried about our second team, Vikes Blue, because during the practice competition they were struggling with some basic input and output issues. Going into the competition, I had hoped that Vikes White would finish in the top 10 and the Blues would be in the top half. Both teams far exceeded my expectations and completely blew me away with their performances under pressure.

UVic's top team, Vikes White, consisting of second year students John Hawthorn, Scott Porter, and Dan Sanders finished 4th with 7 problems solved behind two teams from Stanford University and the winning team from UBC. The second UVic team, Vikes Blue, consisting of Tyler Cadigan, Tim Song, and Tristin Sturgess, finished 22nd with 5 problems solved. The final scoreboard is available here: http://130.86.76.240/pacnw09s/

This is only UVic's second time competing in the regional competition in recent years and only one student had competed before. The Whites were in 4th place after 30 minutes with two problems solved, however, quickly fell to 9th as other teams solved their 3rd and 4th problem. The Whites caught up by solving 3 more problems, and were tied with several teams in the top 10 with 5 problems solved by the 2 hour mark. At the half way point in the competition, UBC and Stanford were on top with 7 problems solved and all other teams had 5 or less.

Around this time, I could see my team high fiving and I got excited that perhaps they had submitted another problem. I kept hitting refresh on the scoreboard, but no submissions came up. I tried to look at their screen to see if they were submitting, but all I could see was Dan still working away. Shortly afterwards, they submitted.

The coaches receive the problem set at the start of the competition, and after reading through the problems, all the coaches agreed that problem D was by far the hardest problem. This problem involved computing reflections of a laser through multiple crystals. It was the only problem I really had no idea how to solve.

After the Whites submitted, the problem that came up on the scoreboard as under judgement was this very problem and I got extremely worried. I couldn't believe they were attempting D when several other easier problems still existed. The coach from SFU actually asked me, "Are your guys really gifted at geometry?" I replied by saying, "They're ok." They had never successfully solved a hard geometry problem in the past.

I kept refreshing like mad to see what the judgement was, but before the scoreboard updated, I saw my guys high fiving again and I knew they must have received an accepted on it. The scoreboard updated and they moved into 4th place behind two Stanford teams and UBC. I couldn't believe, I was blown away. At this point, they really had a chance to make the finals.

However, during the next hour and a half, the team failed to submit anything and SFU, U. of Washington and Berkeley all caught up by solving 6 problems. The Whites were still on top of this heap as they had received zero penalty minutes. I knew they would most likely need a 7th or possibly 8th problem in order to keep their position.

The scoreboard froze with one hour to go and during that time, unknown to the Whites and me, two teams from the University of Washington solved a 7th problem and moved into 4th and 5th. The Whites struggled to get a 7th problem and I watched anxiously from the coaches room. I could see them switching between Dan and John at the terminal and I was worried that they were trying to do too much. However, with 5 minutes left in the competition, I saw them high fiving again, and I knew they had solved a 7th. John moved onto the terminal immediately and was working away. He submitted in the last minute, but received a TLE.

We knew the team would probably be in the top 5, but they needed to be 4th behind the two Stanford teams and UBC in order to have a chance for the finals. After dinner they announced the top 7 positions, and UVic had indeed moved into 4th. They have a chance for a wild card position in the finals, but we won't find out until probably the end of the month.

They were very close on two other problems, and were one of only two teams in the top 10 to receive no penalties for wrong answers. They had accidentally typed in one of the input cases for B incorrectly and spent a long time debugging something that wasn't actually a bug in their solution. This cost them considerable time. They had solved G, but ran out of time to complete the implementation, which would have took them to 9 problems solved. This would not have changed their overall position with regards to consideration for the world finals. Luckily this lesson didn't cost them too badly and they'll hopefully not make the same mistake again.

I was extremely proud and ecstatic with both teams performance. I couldn't believe they both did so well. I knew they were capable, but you never know how things will go and our practices of late have not been as smooth as I had hoped. Both teams worked extremely well together and I hope we get the opportunity to go to the finals. I've already started planning our practices to get better at some of the team's weak areas.

Last practice before the regional

2009-11-04T17:07:00.000-08:00

We're having our last practice session tonight before the Pacific Northwest Regional competition happening this weekend. Our last few practices have not run as smoothly as I had hoped. After our moderate success in the ACPC competition a few weeks ago (see October 18th post), I had been hoping to try out some new team strategy ideas. However, students have been ill or have had other commitments so it's been difficult to have practices with everyone present.

Tonight I'm having the students work on the problems from last weekend's Rocky Mountain Regional. The University of Alberta won this event by solving 7 of 9 and the University of Arizona was second with 5 problems solved. I'm hoping in the 2.5 to 3 hour practice we have tonight that the guys are able to solve 5 problems.

We leave Friday afternoon for Vancouver and the competition starts at noon (PST) on Saturday at UBC. I'll be tweeting about the competition as it happens.

October 21st Practice Session

2009-10-22T10:07:00.000-07:00

Last night we had our weekly Wednesday night practice session. Based on results from previous competitions, I've noticed that typically our top performing team is one problem short of a top tier spot in the contest. Also, in the ACPC competition from last Saturday, UVic White solved 8 problems without any errors, but they had some large gaps between submissions. As a result, we decided to try to work on coding speed.

Everyone was given a set of 8 easy to medium problems selected from the last 2 years of ACPC. They had to work as individuals and try to solve them as quickly as possible.

Unfortunately, the UVA online judge was down, so I wasn't able to test their solutions until today. Also, unfortunately, the results were not great. There were quite a few wrong answers and time limit exceeded. Some of these issues were due to minor oversights, but a few were due to the use of incorrect approaches for the problems.

The one problem that no one successfully solved was Partitioning the Palindromes. This was the trickiest problem in the set.

In this problem, you are given a single string, and you want to partition it into subsets, where each subset is a palindrome and you want to do this such that the number of subsets is minimized. Also, a valid subset has to be a substring of the original string, you can't move letters around.

As an example, consider the string "aaadbccb". You could potentially partition this into individual letters {"a", "a", "a", "d", "b", "c", "c", "b"}. However, this leads to 8 subsets, you can do better by building larger palindromes, i.e. {"aaa", "d", "bccb"}.

To solve this problem, you could potentially do backtracking, but if you look at the contraints, the length of the original string can be up to 1000 characters, which means backtracking will be way too inefficient. This usually leaves one of two choices, a greedy approach or dynamic programming.

It's easy to see that greedy will not work. Consider the string "abbadabb". With greedy, you could choose the largest palindrome that you can make with the first letter, "abba". Then the next two letters must be in their own subsets and finally the "bb" forms the last subset. However, the optimal solution is to split the string into subsets {"a", "bbadaabb"}.

One way to start to think about this problem is to think about the palindrome subsets as nodes in a graph. For example, let's take the string "aaadbccb". Originally, starting on the left hand side of the string, we can form palindromes "a", "aa", and "aaa". Consider those as three different nodes in our graph. If we start with node "a", what nodes could we get to from here? Well, basically any palindrome starting with the second letter of our string, so this only includes palindrome "a" and "aa". We can do the same type of expansion for the original "aa" and "aaa" nodes. If we continue this expansion, we get a graph like the one below.

Notice how the shortest path through the graph represents the minimal subset of palindromes. So, we could possibly do a breadth-first search, adding nodes to a queue and stopping when we complete the string. However, this, like backtracking, will be too slow.

The key insight that you need is to realize that a lot of these branches are useless to process. There's a lot of duplicate construction, or overlapping construction, which generally means memoization or dynamic programming is a good approach.

The way you can use this idea in this particular problem is to keep track of the minimum number of subsets used to create a string of length L. You only process a particular node expansion if you can improve this cost, otherwise, you should cut the branch as you can't possibly do better than what you have already computed. You could do this recursively or do it BFS style with a queue. In semi-pseudocode, the BFS solution looks like the following:

// create array of min subsets, set values to infinity
int M[1001];
queue q;
  
int minSubsets(string s) {
  addNeighbors(s, 0, 0, 0);
  
  while(q is not empty) {
    Node p = q.dequeue();

   if(p.stringSize == length(s)) return p.subsetSize;
      
    addNeighbors(p.startIndex, p.stringSize, p.subsetSize);
  }
}
  
// add any palindromes that extend the current subset
void addNeighbors(int startIndex, int stringSize, int subsetSize) {
   for(int i = startIndex+1; i < length(s)+1; i++) {
      int stringLength = stringSize+i-startIndex;
      // make sure the new subset is better than a previous one
      // for the given string length
      if(M[stringLength] > subsetSize+1 
          && isPalindrome(substring(s, startIndex, i))) {

          M[stringLength] = subsetSize+1;
          Node n(startIndex, stringLength, subsetSize+1);
          q.enqueue(n);
      }
   }
}

There are many problems that can be solved using a similar method. For example, both of these problems from the 2007 Pacific Northwest Regional competition can be solved this way with a few other tricks added in: Pebbles and Bridged Marble Rings.

Alberta Collegiate Programming Competition

2009-10-18T09:16:00.000-07:00

The two UVic teams, Vikes White and Blue, participated in the Alberta Collegiate Programming Competition yesterday. The Whites team consisted of Dan Sanders, John Hawthorn, and Scott Porter, while the Blues had students Tim Song, Tristin Sturgess, and Tyler Cadigan. You can see the final scoreboard here.

It was a great competition and turn out, 37 teams participated. Vikes White was the top performing UVic team, finishing 9th overall with 8 of 10 problems solved. Vikes Blue finished 22nd overall with 3 problems solved. Stanford took first place, UBC second, and Waterloo was third, all with 9 problems solved.

Nick Matthijssen, a graduate student in the CHISEL research lab at UVic, and I also formed an unofficial team and worked on the problems. We solved 8 of 10 in about 4 hours and would have finished 5th or 6th.

Both teams had a good start, the Whites solved their first problem at 13 minutes while the Blues got one at 20 minutes. Things slowed down for both teams for a while, and eventually both had 3 problems solved and were stuck with getting a 4th. Eventually the Whites really stepped up the pace during the third and fourth hour, solving 4 problems in 70 minutes. The Blues got stuck with problem F, and were never able to figure out the cause of the wrong answers.

I was extremely proud of both teams. Waterloo, UBC, and Stanford will most likely be some of the top teams at the world finals this coming year, so to lose by one problem to those teams is certainly acceptable. It's good company to keep :-).

One of the most amazing things about the Whites team is that they received zero penalties for wrong answers. They were the only team that solved a significant amount problems to receive no penalties. This kind of precision could be a huge asset at regionals next month if they can solve some problems a little faster.

Since this post is already quite lengthy, I'll save the problem analysis for a separate post.

UVic Weekend Practice

2009-10-14T11:30:00.000-07:00

Last Saturday, the two UVic teams participated in a practice session with teams from SFU, UBC, and Columbia university. Columbia was first overall with 6 problems solved, and two individuals from UBC also solved 6 to claim second and third.

We had a bit of a rough start as some UVic team members were locked out of the building and arrived late. Also, the top UVic team was missing a member and the other team had one member that had never competed before. The top UVic team solved 5 problems and finished 5th overall, just being edged out by SFU's top team, that also solved 5 problems. The second UVic team solved 5 problems, but finished 10th overall.

A lot of teams managed to solve 5 problems, as there was 5 reasonably easy and short to code problems, and then 3 hard problems. Of the hard problems, all of the teams to solve 6 solved problem G from this problem set: http://cs.stanford.edu/group/acm/SLPC/problems.pdf

Problem G is identical to problem F, except that there are far more rectangles. You can solve F with a straight-forward N^2 implementation of the standard dynamic programming solution for longest increasing subsequence. However, problem G requires an NlogN solution as there are as many as 100,000 rectangles. There is a known NlogN solution for solving the longest increasing subsequence problem, however, none of the UVic students knew of this algorithm. It may also be possible to implement enough short-cuts in the N^2 solution to drop it down under the time limit.

The two unsolved problems were B and H. B is a geometry problem, where you need to figure out how many balls can fill a fruit bowl given the description of the fruit bowl and a description for how it should be filled.

In problem H, you have to find valid solutions to a 2x2x2 rubik cube. You are given an initial configuration and you can apply 3 different spins a number of times to try to get all sides to have a single color.

I'm not really sure how H can be solved within a standard 2 or 5 second time limit without breaking the standard memory constraints for a problem. It's possible to solve the problem using a bounded breadth first search algorithm, with efficient implementations of the spins and storing seen states, but this is still slow without relying on significant amounts of memory. It's also possible to pack the cube state into two integer values rather than a 6x8 char array to cut down on memory, but then extra processing time has to be spent on packing and unpacking the values for applying the spins.

The teams are competing this weekend in the Alberta Collegiate Programming Competition. There will be a lot of teams from Canada and the US competing, so it should give us a good chance to see how we will fair at regionals.

Finally, I am speaking today at a computer science event for undergraduates to try to generate more interest in the ACM ICPC contest.

October 7th Practice Session

2009-10-08T09:05:00.000-07:00

We had our first organized team practice session last night. I had Dan, Scott, and John work on problems from the University of Waterloo's local contest from September 27th, 2009, http://plg1.cs.uwaterloo.ca/~acm00/090927. while Tristan and Tim worked on four different problems requiring bruteforce solutions.

Dan, Scott, and John struggled a bit on the Waterloo problems. This was partly due to initially using an incorrect approach to a reasonably easy problem. The problem set consisted of 5 problems, two of which were quite straightforward, and two which were solvable but required careful implementation, and the 5th problem I am still unsure how to solve.

With Tristan and Tim, after explaining different bruteforce approaches such as backtracking, enumerating permutations, and so forth, along with how to determine whether a problem can be bruteforced, they solved all four problems that I gave them. The only problem they had was a time limit exceeded on their first problem, which was actually due to Java's slow Scanner object creation rather than an incorrect algorithm implementation. They were able to get around the issue by modifying the way they read in their input.

Both teams are competing in a practice competition this coming Saturday along with teams from SFU, UBC, and Columbia.

ACM Teams Qualifier I

2009-09-22T04:49:00.000-07:00

Simon Fraser University hosted an ACM Team Qualifier competition this past weekend for UBC, SFU, and UVic students. SFU had 30 students compete, UBC had 21 and UVic had 6. Dan Sanders from UVic finished third, while John Hawthorn, also from UVic, finished 13th. The complete final standings are here: http://www.cs.sfu.ca/news/events/ACM/090919/full.html

Dan jumped out to an early lead in the competition by solving problem A on the first try, 13 minutes into the competition. Both Dan and John fell behind when they got stuck trying to solve a second problem. Dan submitted D, but received a time limit exceeded response while John attempted B, but kept getting wrong answers.

Dan managed to catch up to the leaders and move into third in the last 30 minutes by solving both B and D. He did not have time to make an attempt on problem C.

The problem set is available here: http://www.cs.sfu.ca/news/events/ACM/

It was a pretty good set of problems. Below I give my high-level analysis of each problem.

A - The problem is to determine in what order to do your laundry based on the constraint that all laundry takes 30 minutes to wash, but varying amounts to dry. You only have one washer and one dryer, so you can't dry more than one item at a time. The key is to realize that the fastest way to do your laundry is always to handle the longest drying items first. This is a greedy approach, requiring a simple sort of the laundry items. The second part of the problem is to properly print the result. Many wrong answers were a result of improper digital clock formatting. This problem was the easiest problem in the set.

B - In this problem, you have to determine which players can reach the final of a tennis tournament. There is a maximum of 16 players, and you know which players will win when a given player faces off against another player. The key insight is to realize that since there are only 16 players, you can try all combinations, generating all possible tournament situations. This can be done in a number of ways, recursively is probably the simplest way. However, only four students managed to solve this problem.

C - I actually thought this was the second easiest problem to solve, but during the competition, it was the third most solved problem and no UVic student attempted it. The problem describes two languages and four rules for translating a word from one language to the other. When a word is translated from the first language to the second, and then back to the first, it's possible to generate a new word, that is a synonym of the original word. To solve the problem, you have to find all possible synonyms and print them in alphabetical order. The catch is that you may have to apply the translation rules multiple times in order to discover all the unique synonyms. I think perhaps this was not completely clear in the problem text, thus, some students were not sure how to solve the problem.

To actually solve the problem, the algorithm simply needs to apply the four rules, then apply the reverse rules, saving the list of synonyms. Continue this process on the newly generated list until no new synonyms can be created. Then print the complete list of words.

D - This problem is a classic computer science problem. You are given a large list of points in 2D space, and you need to find the line that contains the most points from the list. This was the second least solved problem, due to the number of points being as many as 400, thus a reasonably efficient solution was necessary. There are many ways to address this problem. One approach could be to calculate slopes and y-intersects between all points (N^2). Then find the points that share the most slopes and y-intersects. An alternative approach could be to calculate the angles between points x and y for all x and y, then count the number of points that have the same relative angle to x. To get this solution under the time limit, your code had to be reasonably efficient.

E - This was the second most solved problem. The problem describes how the Canucks hockey team has a certain probability of winning a game against another team. However, when they win, in the next game, they have a higher probability of winning, but if they lose, then they have a lower probability of winning the next game. Given values for this change in probability, you need to calculate the probability that the Canucks will win a best of 7 game hockey series. To solve this, all you need to do is bruteforce all the possible win and loss scenarios (there's not that many), summing the probabilities for when the Canucks win the series.

There is another competition coming up this weekend, but as I am out of the country right now, UVic may have to wait until Wednesday to attempt the problem set.

New ACM ICPC Season

2009-09-17T14:03:00.000-07:00

It's been quite a while since I posted, but the Pacific Northwest regional competition is coming up in about a month. As a result, beginning last night, I've started training UVic undergrads in preparation for the competition. I had all the newbies work on four different simple problems, mostly dealing with string processing.

Links to problems:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=96&page=show_problem&problem=585
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=96&page=show_problem&problem=1056
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=96&page=show_problem&problem=951
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=96&page=show_problem&problem=350

Everyone solved at least one problem and several solved a couple over the 3 hour meeting time. I had the more experienced members work as a team on problems from the 2002 Rocky Mountain regional. Working in a team of two, they solved 5 problems in about 2.5 hours. The problems in this particular regional were pretty straightforward, but it's still an encouraging start.

I'm becoming more and more convinced that Java is the better competition language for the ACM competitions, especially if you have access to Eclipse. With Java 1.6, the combination of the various collections, scanner class, and regular expressions makes it quite attractive over C++.

For example, one of the problems from the Rocky Mountain regional was to parse e-mail addresses out of a stream of ASCII text. Back in my competition days, using C++, I would have had to painstakingly encoded the various matching rules to parse the strings looking for the e-mail addresses. However, last night, one of the students quickly solved this problem with less than 10 lines of code using a regular expression for the matching in Java.

What in C++ would be an ugly set of methods, becomes the following regular expression in Java:

Pattern.compile("[A-Za-z0-9_-]
 (\\.?[A-Za-z0-9_-])*@[A-Za-z0-9_-](\\.?[A-Za-z0-9_-])*");

Also, using an IDE like Eclipse removes much of the tedium of dealing with some of Java's rather verbose syntax. I've seen experienced Eclipse users rapidly produce code through a combination of typing commands and hitting CTRL+space for term completion. Eclipse will also automatically compile, fix your imports, point out syntax errors, and has an integrated interactive debugger.

SRM 439 Div 2

2009-05-05T09:53:00.000-07:00

I competed on TopCoder last week. I submitted solutions to all three problems, but due to some pretty silly mistakes, only my 500 solution passed the test cases. Pretty shameful :-(.

The problem set was actually quite do-able. The first problem was, given a rectangular grid of integers, find the largest square that contains the same digit in all four corners. My solution was to loop through each element (i,j) in the grid, then through all elements to the right of the given element. If any element to the right matched the given cell (i,j), then I would check to see if the cell located in the bottom left and bottom right hand corners of the square also have the same number. If so, store the size of the square if it is larger than my current best.

int getMax(vector  data) {
 int ans = 1;
 for(int i = 0; i < data.size(); i++) {
  for(int j = 0; j < data[i].size(); j++) {
     int v = data[i][j]-'0';
     for(int k = j+1; k < data[i].size(); k++) {
       if(data[i][k]-'0' == v) {
         // length of square
         int d = k - j;
         if(i + d < data.size() && data[i+d][j]-'0' == v
            && data[i+d][k]-'0' == v)
           ans = max(ans, (d+1)*(d+1));
       }
     }
   }
 }
 return ans;
}

Unfortunately, I made a really silly mistake with my indices during the contest by accidentally checking if data[i+d][k] matched v twice rather than data[i+d][j].

In the second problem, you have N bottles, each with unlimited capacity, initially all containing 1 liter of water. You can pour one bottle into another provided the amount of water currently in the two containers is equal. You need to reduce the number of bottles to at most K. If it's not possible to do that with exactly N bottles, you can buy additional bottles. You have to return the minimum number of additional bottles that you must purchase.

This can be solved quite easily once you make a simple observation. First, given a number M, you want to determine how many bottles will be left over after you reduce the number of bottles as much as possible (that is, all possible pourings). Taking an example of M = 13, then initially you have:

1 1 1 1 1 1 1 1 1 1 1 1 1
After one round of pourings, you get:
2 2 2 2 2 2 1
Another round:
4 4 4 1
Last round:
8 4 1

So, you are left with 3 bottles after all possible pourings. This process of reducing bottles to the minimum number is very similar to the process of converting a decimal number into binary. To see this, let's take the same example again but convert M=13 into binary.

13 = 6 * 2 + 1
6 = 3 * 2 + 0
3 = 1 * 2 + 1
1 = 0 * 2 + 1
13 in binary is 1011.

Notice how the multiplier equals the number of bottles that perfectly pour into each other each round and the remainder is the bottle left over. Also, interestingly, the number of 1s in the binary representation is equal to the number of bottles after all possible pourings! Thus, to solve the problem, we can start at N, keep adding bottles and count the number of 1s in the binary representation and see if that number is less than or equal to K.

int getMinBottles(int N, int K) {
int cur = N;
while(__builtin_popcount(cur) > K) cur++;
return cur - N;
}

In the last problem, you are given a string s, and you must determine the minimum number of insertions, deletions, and changes you would need to do in order to convert s into a palindrome. There was also one other twist, you were also allowed to perform one swap operation.

The problem is actually pretty easy to solve if you are familiar with the standard edit distance dynamic programming solution. With edit distance, you want to know the minimum number of insertions, deletions, and changes to convert string s1 into string s2.

Ignoring the swap operation, we can intepret this problem the same way by thinking of our string s in two halves. Since we want s to be a palindrome, that means the substring for the first half of s needs to eventually equal the substring of the second half of s. Thus, still ignoring the swap operation, we can easily compute the minimum number of operations to convert the first half into the second using the standard DP solution for edit distance.

Ok, so we're almost there. Now, we need to figure out what to do with the swap operation. Well, the solution is actually pretty simple. Since we can only do the swap once, we can just try performing all possible swap operations. After each swap, check the edit distance calculation and store the minimum number of operations plus an additional one for the swap. The algorithm would be similar to the following:

int getEditDistance(string initial) {
 // compute distance from the two halves
 int ans = editDistance(initial);
 // try all swaps and recalculate distance
 for(int i = 0; i < initial.size); i++) { 
   for(int j = i+1; j < initial.size(); j++) {   
      swap(initial[i], initial[j]);   
      ans = min(ans, 1+editDistance(initial));   
      swap(initial[i], initial[j]); 
   }
 }
 return ans;
}

ACM ICPC Finals Problem Set

2009-04-27T09:02:00.000-07:00

I only read through the problems once and didn't spend too much time thinking about them, but here's my analysis based on my first impression. First, check out the problem set here.

A. This problem looks reasonably straightforward. Most teams solved it. There's only 8 planes, so you can try all 8! orderings and use binary search to compute the minimum time. After that, place all planes as close together as possible and keep track of the best answer.

B. I don't think there's anything particularly tricky about this problem. I believe you just implement the gates and simulate the execution. In the situation where you need to track down the bad gate, you can try making each gate bad and see which one results in correct answers. There's only 19 gates, so it should be pretty do-able.

C. This problem is very similar to a classic problem with an ant or spider on a cube. I actually received this problem during a job interview once. With the cube, you unfold the cube in every possible way and then compute the shortest distance in 2D. For an octahedron, the same process should work. It's probably a bit tricky to get all the details correct.

D. Only idea I have is to try all possible configurations.

E. Haven't solved it yet.

F. Doesn't look too bad and a lot of teams solved it. I think you can compute the convex hull between points and then extend that based on the margin. You can combine this perimeter with rounded segments based on circles enclosing the points. To figure out the smallest fence, use dynamic programming (DP) over the point subsets and fence lengths.

G. This is a two player game problem, but I think you can bruteforce it. You have to carefully implement the various rules of the game, but the number of possible states is reasonably small provided you cut branches that are bad.

H. This problem can be formulated as 2-SAT, which has a well-known solution using depth-first-search. To determine the result for a variable, you can fix the answer and run 2-SAT, checking if the formula is still satisified.

I. I need to read this problem again, but it looks like a simulation problem.

J. Not sure of the details yet. Looks like DP.

K. Looks like DP mixed with shortest-path. Haven't worked out the details.

Looks like a good set of problems. There was a decent spread of the teams, with most solving at least one or two, and no team solving them all.

ACM ICPC World Finals

2009-04-24T08:19:00.000-07:00

The ACM ICPC World Programming Finals took place a few days ago on April 21st. St. Petersburg State University of IT, Mechanics and Optics was first, Tsinghua University second, and St. Petersburg State University was third. You can check out the full standings here.

As usual, Waterloo was Canada's top competitor, finishing in the medals for the 6th year in a row with six problems solved. I am always amazed at how well Waterloo does. They are consistently in the medals regardless of their regional performance. At their regional this year, they finished 3rd behind two teams from Carnegie Mellon University, yet at the finals, they beat Carnegie Mellon. Of course, it's easy to have a bad competition or get stuck on a problem, but they always seem to bring their A-game at the finals.

UBC was the second highest Canadian team, finishing tied for 34th with four problems solved. The other Canadian teams (Alberta and McGill) both received honourable mention. This is not the strongest showing for Canada, but a number of typically good teams did not place (e.g. CalTech).

Russia and China dominated the medal positions. North America only claimed three spots out of 13, with MIT being the top North American team finishing 7th with seven problems solved. One surprising medal winner was Tbilisi State University from Georgia. At least, I cannot recall them ever being at the finals let alone in the medals. Of course, I could be wrong.

Stanford University was the top placing team from UVic's region, finishing 20th. UBC was next and then Berkeley. UBC was actually beat by Berkeley in the regional competition, so it's nice to see them get some kind of revenge.

I haven't read the problems yet, but I'll probably check them out soon.

Regionals date

2009-04-09T08:40:00.000-07:00

I am finally back from my almost month long vacation to Japan and China. The trip was fantastic. It was nice to take a break from programming and work for such a long period, but now I am back and trying to scramble to get caught up. I am teaching a third year course on HCI this summer, so I need to prepare for that. I am also starting as a postdoc in May and doing that until the end of the year.

While I was away, I received an e-mail from the Pacific Northwest Regional director. Apparently, the world programming finals for the ACM ICPC is happening a month earlier than usual next year, so regionals need to be complete by November 1st, 2009. Normally, the Pacific Northwest Regional takes place around the 20th of November, but this coming Fall it will be on the 31st of October. That means I'll have almost 3 weeks less time to prepare my teams.

Luckily, the programming club from this past term was pretty successful, so I should have some returning programmers for next year. I am hoping to take two teams this year and I think the top team should be reasonably strong.

PhD Defense

2009-03-12T17:05:00.000-07:00

This is not a very programming related post, but I had my PhD defense today. It went very well. My thesis is being nominated for the University of Victoria Gold Medal, which is the prize for the top PhD thesis at the university. It is probably a long shot as I'm sure there are plenty of good theses out there. Also, I don't know how any committee could compare a PhD from math with a PhD from philosophy and one from computer science. However, it is still nice to be nominated.

I am off to Japan tomorrow morning and on the 23rd I am heading to China so I won't be competing on Top Coder until some time in April. Hopefully I'll get in a little practice while I am away.

TCO09 Round 1

2009-03-10T08:45:00.000-07:00

I competed in the Top Coder Open 2009 Round 1 last Saturday after qualifying the previous week. My friends Nick and Oleg also competed. You had to finish in the top 720 to qualify for the next round, but only Oleg managed to do that out of the three of us. I was very close, but unfortunately an off by one error caused me to fail system tests.

The first problem was pretty easy. You were given a number N between 1 and 10^10 and another number L between 2 and 100 and you wanted to find a sequence of numbers of length at least L that summed to N.

I realized that candidate numbers would be close to N/L for L up to 100. So my algorithm tries all numbers and their sums within those ranges keeping track of the best one.


vector<int> sequence(int N, int L) {
   if(L > 100) return vector(0);
   vector<int> r, best;

   for(int j = L; j <= 100 ; j++) {
      int mid = N / j;
      // define an arbitrary range of numbers to try
      int start = max(mid - 1000, 0);
      int end = mid + 1000;

      // try all numbers
      for(int i = start; i <= end; i++) {
         int sum = 0;
         for(int k = i; k <= N; k++) {
           sum += k;
           r.push_back(k);
           if(sum > N) break;
           if(sum == N && r.size() >= L 
                 && r.size() <= 100 && (r.size() < best.size() 
                 || (!best.size() && r.size() <= 100)) {
             best = r;
           }
         }
         r.clear();
      }
    }

    return best;
}

I got the code implement pretty quickly and submitted for a pretty decent score. Provided I passed the system tests, with the one problem solved I would have been close to qualifying for the next round. Unfortunately, when I submitted my loop from k=i to k <= N was written as k=i to k < N. That simple mistake cost me the competition :-). There are nicer ways to solve this problem using the sum formula, but I still like my semi-bruteforce approach.

I got stuck on the 500 problem and glanced quickly at the 1000 out of desperation. I should have moved onto the 1000 point problem because I think it was easier than the 500 even though it required a lot more code. I solved the 1000 point problem yesterday.

In that problem, you are given the description of a new chess piece called a "Unicorn". It moves by choosing any of the 4 basic directions and moving more than 2 squares in that direction, then turning orthogonally in one of the two possible directions and moving more than 1 square in that direction. You are given a randomly generated chessboard of size up to 300x300 where each square or cell has a letter (A through Z). You are also given a word that can be spelled out on the chessboard by moving a unicorn piece. You have to determine how many possible ways you can generate the given word by moving a unicorn piece around the chessboard.

For example, consider the chessboard below:


ABCD
AAAA
AABC
AAAB

If we want to construct the word "AB", there's only two ways to do this. We place our unicorn piece in the top left-hand corner getting the "A". We can then move our chess piece 3 places to the bottom left-hand corner, turn orthogonally to the right, and move 3 places to the right to get a "B". We can also reach the bottom right-hand "B" by placing our unicorn in cell (1,0).

The key to solving this problem is to realize that assuming you arrived in a cell, there's a fairly small number of cells that you could not possibly have been at previously to reach this cell. You can keep track of the number of paths to reach a given cell by counting the number of ways to reach all previous letters and subtracting off the cells that you could not possibly have come from.

Moving back to our example from before, initially we can get to any cell with an A in one step. Meaning that you can travel to that cell one way, essentially place the unicorn directly on it. Represented as a matrix it looks like this:

Now we can consider any cells with a B. The first is cell (0,1). There's a total of 10 possible A's that we could have used to arrive at this B. We can cross off all the cells that we could not possibly have jumped from to reach this location. This includes B's row, column, previous column, next column, previous row, next row, and a few others.


XBXX
XXXX
XXXX
XXXB

We can count all the A's that were crossed off, which turns out to be 10 and remove this from the total number of A's, which is also 10. This means there are zero ways that this particular cell could be the second position in a valid path to form the word "AB". We can continue doing this. Once we reach cell (3,3), the crossed off matrix looks like this:


AXXX
AXXX
XXXX
XXXB

There were 8 "A"s crossed off, so there are 2 ways to get to this "B".

For longer words, the process is much the same. There's a few catches in the problem, like making sure you handle large sums appropriately as you can potentially get a very large number of paths. Also, there's a small trick to get the algorithm to run in O(N^2) rather than (N^3).

TopCoder Practice - SRM 254

2009-03-04T08:13:00.000-08:00

I participated in a TopCoder practice session yesterday with Oleg and a new student in our research group, Nick. It turned out to be my best SRM in quite some time. I think I submitted all three problems before Oleg and Nick had submitted their second solution. I was a little worried that I had messed something up since I finished so quickly.

I started looking at my 500 and 1000 point solutions to see if I missed something in the problem. I was pretty sure my 500 solution was correct. The problem involved string matching. You were given a string along with a potentially short-hand version of that string. For example, the string "capture" can be shortened as "cptr". You had to return the letters that could be removed from the first string such that the remaining letters matched the shortened version. In the previous example, the answer would be "aue". If no match is possible, return "UNMATCHED". I scored 481.63 points on this problem, which is probably my best score on a 500 point problem.

The solution is pretty straight-forward. The max length of the string is 50 characters, so you can use an N^2 string matching algorithm. I looped through the shortened version of the string, and had an inner loop that looked for matches on the larger string. On the first match, I break from the inner loop and add all the characters before the match to the string I will return. If I didn't find a match then I know I can't make this string.


// typed is the shorter string, phrase is the original
string probableMatch(string typed, string phrase) {
  string s = "";
  int last = 0;
  for(int i = 0; i < typed.size(); i++) {
     int j = last;
     for(; j < phrase.size(); j++) if(typed[i] == phrase[j]) break;

     // we found a match, so add the suffix to s
     if(j != phrase.size()) {
        s += phrase.substr(last, j - last);
        last = j+1;
     }
     else return "UNMATCHED";
  }
  s += phrase.substr(last, phrase.size() - last);

  return s;
}

The 1000 point problem was a really fun problem. You were given a description about how pigs choose a trough to eat from. The piglets attempt to choose a trough that will delay the time when they become sandwiched in by two piglets. After reading the problem, I realized based on the description that you could solve it using a greedy strategy. Each choice made by a piglet is a locally optimal decision, so you just need to process the choices in the correct order and return the first one that is available. Although I got quite a few points for the problem, I could have done it much faster by using C++'s built in string find rather than writing loops to do all the look ups. Both Nick and Oleg used dynamic programming for the problem, not realizing that greedy works.

It turned out that I was right about missing something in the problems, but it wasn't on the 500 and 1000 point problems, it was with the 250. I actually failed the system tests on the 250 problem. It's only the second time I've had that happen. I made a pretty silly mistake and didn't make use of a formula given in the problem. Instead I tried to figure it out with my own formula.

Despite this error, I still would have been second overall in the SRM and I beat both Oleg and Nick during the practice. Tonight Nick and I are participating in the 3rd qualification round for the Top Coder Open. Hopefully we'll qualify. Oleg has already qualified. The first official round is this Saturday.

Huh? No unsigned values in Java?

2009-02-26T09:39:00.000-08:00

I've been working on this program with my friends Dmitri and Oleg. The program computes permutations of reversible circuits (i.e. NOT gates, CNOT gates, etc.) for different numbers of inputs. The gates are simulated by performing bit operations on 64-bit unsigned integers. The details aren't that important, but what's interesting is that the number of permutations gets massively huge as the number of inputs increases. To store results for 8 inputs, you need an array of size (2^29)*8, where the 8 is for 64-bit unsigned integers.

Oleg developed a C++ version to do the calculations and after some tweaks and bug fixes we managed to get it to calculate up to 6 inputs in about 5 seconds. With 7 inputs, things get a little tricky because you need a table of size (2^26)*8, but we also use three other arrays of similar size. On our 2GB machines, this is too much. However, it's possible to calculate for 7 inputs if we do something hacky like make one special table that size and leave the other ones smaller at size (2^23)*8.

We want to calculate values for at least 8 inputs. This is beyond our 2GB machines, at least if we keep everything in memory. I originally worked on dumping our hashtables to files and merge sorting the files in the process when the hashtables get too large, but this is pretty slow. After this I decided to try dumping the tables into a database. I converted the program from C++ to Java and hooked in a MySQL database.

This is where I ran into the issue that Java does not support unsigned long values. I hadn't realized this, but of course, how often do you need a full 64-bit integer? Luckily, I was able to get around the lack of unsigned values by first realizing that bit shift operators in Java do not care about the sign bit except for the right-shift (>>). However, there's an unsigned version (i.e. >>>). The second problem was that you can't use less than and greater than operators because if you're using the sign bit, then a potentially large number will be negative. To get around this, I wrote my own comparison function, which is shown below.


/**
* Bitwise comparison of longs.  This is to handle the fact 
* that Java does not support unsigned longs.
*/
static int compareLongs(long p, long q) {
  if(p == q) return 0;
 
  for(int i = 64; i >= 0; --i) {
     long t1 = (1 << i) & p;
     long t2 = (1 << i) & q;
     if(t1 < t2) return -1;
     else if(t1 > t2) return 1;
  }
  return 0;
}

I had to make some other tweaks as well, like writing a clone function for our hash table as assignment in Java works differently than C++. Once I completed this, and the various bit shift changes, the Java version ran almost as fast as the C++ version.

For the database integration, I ended up doing a lot of MySQL configuration tweaks in order to get my bulk insertion speed faster. I also discovered some new MySQL specific SQL syntax. For example, you can use REPLACE INTO instead of INSERT INTO if you are going to potentially insert a record with a matching primary key. The replace version will delete the old version and insert the new one. I actually ended up using a similar SQL statement, INSERT IGNORE INTO, which does the same thing but does not delete the original record but simply ignores the new one.

I'm not sure how useful this Java version is going to be as I managed to get access to a server with 8GBs of RAM where I can allocate enough memory for the C++ version to work. Also, Oleg was able to calculate inputs of 8 values by dumping multiple files to disk and then using the Unix sort program to merge and sort the files. However, it was still a good learning experience and we can possibly use it for verifying our numbers. I'll post a bit about the C++ version next time.

I'm an idiot

2009-02-20T09:06:00.000-08:00

Last post I mentioned that I had not been able to come up with a decent algorithm to problem H from the Waterloo practice. Well, yesterday, while running, I figured it out. There's an N^2 algorithm that's pretty straight-forward.

The problem involves a bunch of planets and each planet has a certain political situation, 0 or 1. A planet is considered unstable if given some value R, there are more planets within R parsecs of the given planet with the opposite political stance than the with the same political stance. Your job is to find the minimum R such that the number of unstable planets is maximized.

The obvious bruteforce solution is to consider all distances between planets, and for each planet, compute whether it is unstable or not. However, this obvious solution is N^4 where N can be up to 1000. That's a big big number.

There's a slightly better algorithm than this, where you can compute and store all distances. Also, for every planet, store in one list the distance of all planets with the same political situation as you in sorted order and in another list the distance of all planets with the opposite political situation as you in sorted order. Then, when you loop over all possible distances and all planets, you can use binary search on the sorted lists to figure out how many planets are for and against you at the given distance. You can also do early outs when you can't possibly improve on the best score. If you only store unique distances, then there will be less than N^2 of these, but could be as many as N^2/2. Regardless of the optimizations, this algorithm is still way too slow, and has a big-Oh of O(N^3 log N).

The N^2 algorithm that I came up with involves computing all distances between planets and storing these in sorted order along with the indices of the planets used to make that given distance. Then, you can loop over all distances and use your previously calculated stabilization results to help solve for the current distance. Since the distances are sorted, results computed for smaller distances can be combined to help compute values for the current distance.

In C++, this could look something like this:


  int destab = 0;
  // m is a multimap where the key is the distance 
  // from planets with indices stored in the  pair values
  multimap<double, pair<int, int> >::iterator iter = m.begin();
  
  // loop over all distances
  while(iter != m.end()) {
    double d = iter->first;
  
    // go over all distances for all planets <= to this one
    while(iter != m.end() && iter->first <= d) {
      int i1 = iter->second.first;
      int i2 = iter->second.second;
      Planet * p1 = &planets[i1];
      Planet * p2 = &planets[i2];

      // if the political situation is the same, 
      // increase the stabilization factor
      if(p1->p == p2->p) {
          p1->c++;
         // planet became stable so decrease destab
         if(p1->c == 0) destab--;
 
         // make sure the second planet is 
         // different from the first
         if(i1 != i2) {
            p2->c++;
            // planet became stable so decrease destab
            if(p2->c == 0) destab--;
         }
      }
      else {
           // political situation is different 
           // so decrease factor
           p1->c--;
           p2->c--;

           // we switched to unstable, increase destab
           if(p1->c == -1) destab++;
           if(p2->c == -1) destab++;
      }

      iter++;
    }

    // keep track of best solution
    if(destab > best) {
      best = destab;
      bestR = d;
    }
  }

I also think problem D. Data Mining is pretty easy. It looks a bit intimidating because it has a bunch of math formulas. Your job is to find the minimum amount of memory that needs to be allocated based on a particular formula they give you. The formula has an A and B parameter, which is not given and you have to find. Everything else for the formula is given.

The key is to realize that since A and B are used as bit shift operators in the formula there is a limited number of valid A and B values. This is because you can only shift an integer to the left and right so much before you just end up with a bunch of zero bits. Thus, you can try all A and B combinations, plugging them into the memory formula and keeping track of the smallest number you can generate. That number is your answer.

Practice with Waterloo

2009-02-19T12:57:00.000-08:00

I had Dan and Scott join the University of Waterloo's online 5 hour practice session yesterday. John couldn't make it, so I helped out more than I normally would. I didn't write solutions to any of the problems, but I helped with debugging, reading the problems and some problem solving. The contest problems were taken from the Northeastern European Regional 2003.

The guys solved 5 of 11 problems and attempted 6. Not bad considering they were down a member, had never worked in a team before, and had some major technical difficulties at the start of the competition.

We weren't able to connect properly to Waterloo's contest software from UVic because of firewall issues. We ended up having to connect through VNC and transfer files for submission via scp. It wasn't until 80 minutes into the contest before the guys could submit the first few problems that they had solved.

It was a pretty good problem set. There were five relatively easy problems requiring simple implementation or some kind of bruteforce. The guys probably started on the second easiest problem rather than the easiest. Most teams started with problem A, which Dan eventually did in just a few minutes, but he didn't realize how easy it was at the beginning. Without the contest software connection issues, the guys probably would have had three problems solved in the first hour.

Things slowed down a bit after those first three as Dan tried a bruteforce attempt on problem H, which resulted in a time limit exceeded. He then went on to work on problem E and Scott coded problem G and had it accepted with about 10 minutes left.

There were a few other problems that looked reasonable. I wrote a solution to problem J this morning, which can be solved with backtracking and branch bounds when you can't possibly improve on your best result. A lot of teams solved H, but I have not been able to come up with an algorithm fast enough for the bounds of the problem. There were also two graph problems, which most of the top teams did.

Waterloo solved 10 of 11 problems, which is quite impressive. They are typically one of the best teams in the world, so it's not surprising. I hope I can get all three members of the team to compete in one of Waterloo's weekend practices before I leave for Asia in March.

Robocode and SRM 435

2009-02-13T08:54:00.000-08:00

I moved this week's programming club meeting to Wednesday so that I could compete on TopCoder on Thursday. This week at the meeting I introduced people to Robocode, which is an environment and API for developing little tank robots. You can control the robot tank's radar, gun, and movement. The goal is to program the best strategy such that you beat all the other robots.

I had played around with Robocode several years ago and programmed a few different tanks. I thought it might be a nice break for everyone to try another style of programming, rather than strictly problem solving.

After I showed everyone how to build a basic robot, I got the students to start building their robots based on tutorials available on the Robocode Wiki. Next week we will start the meeting off by having our various creations battle each other.

I've been working a bit on my own robot. It hasn't been as effective as I had hoped. I implemented a force directed graph layout to control my robot's movements. Bullets that I detect, along with enemies are forces that push my robot in certain directions. It's reasonably effective, meaning I can defeat all the sample bots, but the behavior is a bit erratic at times and doesn't always make sense to me. I may need to do some tweaking. I've also been working on using a different strategy for one on one situations.

Last night I competed in SRM 435 on TopCoder. I solved two of the three problems, however I was considerably slower than need be. I had some computer issues that slowed down my compile and run times, but I also made a number of silly mistakes.

In the first problem, when processing two strings consisting of digits (0-9), I forgot to convert the char representations into integers when performing my math calculations. It didn't take long to fix, but still cost me a minute or two.

The second problem was pretty simple. It boiled down to having the description of a binary tree, and you had to delete a single node and then determine how many leaf nodes are left. I represented the tree using a vector of vectors, then did a breadth first search starting at the deleted node and marking all visited nodes for deletion. Then I iterated over all nodes and counted how many didn't have children and that still existed in my graph.

I lost several minutes on this problem due to a stupid mistake. I misread the first sample test case, so when my program first ran I thought I was doing something wrong, but it was in fact working. I spent a few minutes debugging something that wasn't a bug! I eventually submitted the problem, but I should have been able to get more points for it.

In retrospect, it would have been less code to do this recursively and start at the root, not recurse on the deleted node, and return all leaf nodes encountered.

I had ample time for the last problem, but I wasn't able to come up with a decent algorithm. It was a probability problem. I tried a randomized algorithm after being stuck for intelligent ideas, but it wasn't accurate enough. The actual solution involved dynamic programming and I probably should have realized this.

The next TopCoder competition I will be competing in is on the 28th and is a qualification round for the TopCoder Open. I don't really expect to make it very far in this tournament, but it will be good practice.

Team Practice Session

2009-02-06T11:39:00.000-08:00

I tried doing a team practice session last night during our weekly PClub meeting. It didn't go as well as I had hoped. Several people had to miss practice for various reasons and some people showed up late, so I wasn't able to put together the teams I had planned.

I had one team work on problems from last year's Northwestern Europe Regional while the other two teams worked on the five easiest problems (numbers 4065, 4067, 4069, 4071, and 4072) from the 2007 Pacific Northwest Regional.

Both teams working on the five easier problems solved 4065, which is a simple game simulation for Rock, Paper, and Scissors. One of the teams also submitted 4072, which is another game simulation problem, but got a wrong answer on it. After I fixed that team's parsing, their code worked.

Meanwhile, the team working on the harder problems solved two and attempted a third. However, the team aspect of these "teams" didn't really work. All submissions were sent by the same coder and I'm not sure everyone really got the idea of writing their code out on paper first. It's really important to actually implement the code to solve the problem on paper first while someone else is using the computer.

This is probably somewhat difficult for most of the first years as they struggle with syntax issues and depend on the compiler to check their syntax. They were also struggling with coming up with correct algorithms for the problems, so things moved along slowly.

Next week we are taking a bit of a break from the problem solving stuff to do some Robocode. I'm planning on having everyone write the AI to their own tanks and the following week we'll do a little competition. It's just for fun. I may even participate.

First Annual UVic Programming Competition

2009-02-02T08:37:00.001-08:00

The First Annual UVic Programming Contest took place last Saturday, January 31st, 2009. The contest went extremely smooth. We didn't have any problems with the PC^2 software and only a few minor issues with the problem set, but everything was caught right away. There were 12 competitors in all. You can check out the problem set, scoreboard, solutions, and judge's inputs/outputs here.

There was some pretty exciting back and forth action between the top three competitors. Both Dan Sanders and Scott Porter jumped out to an early lead by solving the first problem at the 8 minute mark. Dan solved a second problem 12 minutes later and had the lead through the first three problems. John Hawthorn took the lead at 51 minutes by solving his fourth problem.

At this point, we were really worried that the top three competitors would solve all the problems in half the time meaning that we made the problem set too easy. We knew that the top competitors would probably solve the first three in the first hour, but they were going even faster than we anticipated.

Scott jumped into second place ahead of Dan by solving a 4th problem at the 86 minute mark, but Dan jumped back in front of Scott 15 minutes later by solving one of the hardest problems in the set. John beat everyone to a 5th problem by getting an accepted solution on the Gem Collector on his 4th attempt. Dan and Scott caught up, but with around 2 hours left in the competition John solved his 6th problem on his 8th attempt.

Dan caught up with over an hour left, but he needed to fix his Gem Collect problem in order to retake the lead. With approximately 50 minutes left, John submitted an attempt at G. I promptly took the scoreboard down for suspense and then went and judged his problem. He got a wrong answer, but 10 minutes later, he submitted again and had it accepted.

Both Dan and Scott attempted to get a 7th problem, but neither managed to get their solutions accepted. Everyone did extremely well. Only one person solved all the problems and everyone solved at least one. Most the competitors were in first year, so that's a fantastic result.

Below is a brief description of how to solve each problem.

A. [**SPAM**] Congratulations, You've Won!!!
Once you read the story, the problem boils down to finding the largest prime number less than or equal to some value N. The maximum value of N is small enough that just about any solution would be acceptable. One simple way to solve the problem is read in N and then test primality for all values less than or equal to N. Something like the following.


int i;
for(i = N; i >= 2; i--) {
  if(isPrime(i)) break;
}

print(i);

bool isPrime(int t) {
  for(int i = 2; i*i <= t; i++) {
     if(!(t % 2)) return false;
  }
  return true;
}

B. The Love Guru
The Love Guru was of similar complexity to the first problem. All that was required was to read in two strings, count the number of shared letters between the two strings (case-insensitive) and divide that by the total number of unique letters. If that value was greater than or equal to 0.4, then print "Get hitched", otherwise print "Part ways".


string getRecommendation(string n1, string n2) {
    // use a vector to check if we've seen a letter before
    vector<int> u(26, 0);
    int shared = 0, total = 0;
    // total up unique letters in first name
    for(int i = 0; i < s1.length(); i++) {
      if(!u[s1[i]-'a']) total++;
      u[s1[i]-'a'] = 1;
    }
   
    // total up shared and unique letters from second name
    for(int i = 0; i < s2.length(); i++) {
      if(u[s2[i]-'a'] == 1) { shared++; }
      else if(!u[s2[i]-'a']) total++;
      u[s2[i]-'a'] = 2;
    }

    // compute percent with truncation
    int perc = (int)((double)shared/(double)total*100.0);

    return ((perc >= 40) ? "Get hitched" : "Part ways");
}

C. You Sunk My Battleship
This was the third easy problem in the set, which we expected most people to attempt or solve. The problem was originally a bit trickier, where there were more ships on the board of varying sizes, but we decided to make the parsing easier. You had to read the description carefully and implement a single player game simulation for Battleship.

The main problem people had was not realizing that a hit to the same location more than once should print "Hit" multiple times but not necessarily sink the ship. You have to hit the battleship in all four locations at least once to sink the ship.

D. Great Ocean Views!
This was the first problem in the set that required a bit more insight to easily solve. Everyone that solved this problem got it accepted on the first try, so provided you were lucky enough to see how to approach the problem, the algorithm was easy to implement. The first key is to realize you can ignore the Z dimension. The second key is that since everything is a rectangle defined in integer space and the size is a maximum 50x50, you can define a matrix to store the window locations of all buildings. You "paint" the building rectangle onto this matrix and afterwards sum up all the overlapping windows. Something like the following.


int matrix[51][51];
// initialize all values to -1
memset(matrix, -1, sizeof(int)*51*51);

int x, w, h, z;
// read in and process each building
for(int i = 0; i < N; i++) {
  cin >> x >> w >> h >> z;
  // paint the building onto the matrix
  for(int j = x; j < x + w; j++) 
     for(int k = 0; k < h; k++) matrix[j][k]++;
}

// sum the windows blocked
int windowsBlocked = 0;
for(int i = 0; i < 51; i++) {
  for(int j = 0; j <51; j++) 
     windowsBlocked += matrix[i][j];
}

print(windowsBlocked);

E. Gem Collector
This problem describes a game in which you collect gems from a matrix. The gems have different values, and you want to determine what is the maximum value of gems that you can collect given that you can start in any location and collect from any cell adjacent to a cell where you collected a gem previously.

Several people had problems with getting an accepted solution. A lot of solutions didn't run under the time limit or gave run time errors. Also, some people seemed to misinterpret what was required to solve the problem. The gem matrix is a maximum 25x25, so it's possibly to try all starting locations and recursively collect gems, keeping track of the maximum value you can collect. See my solution for more details.

F. Vegas Baby!
Only the top three people solved this problem. The solution requires dynamic programming. It's a pretty standard dynamic programming problem, so if you were familiar with the concept, it was likely you would solve it. There was some ambiguity with the problem that caused people to get wrong answers. They weren't sure which value for the number of people to return if there were multiple solutions that cost the same. We wanted the number of people to be as close to K as possible.

To solve the problem, you can make an array or vector where each index represents how many people you can bring, and in each entry you store the minimum cost to bring that many people. To fill this array, you can process each university and for each existing entry in the array, combine that entry with the current university you are processing. Also, update all index values that are a multiple of the number of people from the current university.

The solution is something like the following, where we have a vector called makes initialized with INT_MIN, and the people and cost for a university are stored in arrays p and c.


// loop through our participants
for(int i = 0; i < N; i++) {
    // loop through our current combinations
    for(int j = 0; j < makes.size(); j++) {
        // check if we have a combination for j, 
        // if so, use it to figure out j + p[i]
        if(j + p[i] < makes.size() && makes[j] != INT_MAX) {
           makes[j+p[i]] = min(makes[j+p[i]], makes[j] + c[i]);
        }  // j is divisble by p[i], so we can make j
        else if(!(j % p[i])) { 
           makes[j] = min(makes[j], c[i] * j/p[i]);
        }
    }
}

G. Help Sean
The last problem, once deciphered, works out to be a pretty standard graph problem. Each city can be considered as a node in a graph, edges exist between cities provided the distance between the two cities is less than or equal to the distance you can travel with the car's gas tank. Then you need to calculate the shortest path between the start city (i.e. Victoria) and the end city (i.e. St. Stephen). This can be done using Dijkstra's algorithm or All-pairs Shortest Path or the Bellman Ford Algorithm.

There was also a bit of string parsing to read in the city names and you had to properly implement the given formulas for calculating the distance between latitude and longitude coordinates taking into account the spherical nature of the Earth.

Practice Sessions - Week 4

2009-01-30T06:55:00.000-08:00

Last night was the last practice session before the UVic undergraduate programming competition on Saturday. We had a decent turn out of 11 people and I heard from a few people that are coming to the competition but couldn't make it last night. I'm guessing we'll have about 15 people on the weekend.

I had the students do some old contest problems that Nathan Scott and I wrote back at UNB. There were five problems in total, both Dan and Scott solved three, a few solved two and everyone solved at least one. Dan got a fourth problem completed after the end of the practice.

The first three problems were pretty easy, but trickier than the easiest problems I've had the students do in the past. In the first, you have to simulate the process of determining who won a programming contest. This involved reading in people's names, the time it took them to solve a given problem and how many submissions it took. Then you needed a little logic to calculate their total problems solved plus time taken.

We had some unforeseen issues with this problem. It turned out there was a mistake in the judge's input where one case was larger than what was specified in the problem. This was causing a lot of people's code to either crash or run forever. Unfortunately, we didn't realize this until an hour or so of the student's spinning their heels trying to debug something that wasn't a bug.

The second problem was actually probably the easiest to code in the bunch. It had several scary math formulas in the description, which scared most people off. However, if you take the time to read the problem carefully, all you need to do is implement the last formula that is described. This involved reading in a bunch of numbers, multiplying them together, seeing which one was largest, and printing it out with 5 decimal places. Eventually, several of the students realized this and solved it quickly.

The third problem was a simulation problem. You had to read in a list of book inventory and then process orders on a first come first serve basis and print how much the store made through the sales or a line indicating that they could not fulfill the orders. Understanding what is required in this problem is reasonably straight-forward, but the problem requires some delicate string parsing to read in the book titles. Also, the inventory list has to be read into some kind of data structure and stored for look up during the ordering phase.

A simple way to do this is to create a Book struct or class that contains the name, current quantity and price of a given book then store these in a vector or perhaps a map.


struct Book {
 string title;
 int q, p;
 Book(string title, int q, int p) : title(title), q(q), p(p) {}
};

vector<Book> books;

The number of books is small, so all books can be stored in a vector and look-up can be an O(n) call. In my opinion, the solution to this problem is much easier to code in C++ or Java, as both have dynamic data structures built into the language like lists, vectors, maps, etc. Also, I think the input parsing is easier in those languages.

The next problem was about magic squares. A magic square is an arrangement of numbers from 1 to n^2 in an n*n matrix, with each number occurring exactly once, and such that the sum of the entries of any row, column, or main diagonal is the same. Here is an example of one:

8	1	6
3	5	7
4	7	2

Other magic squares exist for larger numbers, although the numbers are still consecutive within the square. In the problem, you have to attempt to complete a square given a partial configuration. For example:

24	X	X
X	X	23
20	25	X

There is more than one way to go about this problem. The completely bruteforce way is to realize that you can try all possible sequences of 9 consecutive numbers that fit within the given numbers in the square and all permutations of these. This is going to be proportional to 9! = 362,880, which will get under the time limit.

A less bruteforce approach is to observe that all larger magic squares can be computed based on the 1 to n^2 example. Consider the following magic square:

19	12	17
14	16	18
15	20	13

All values (i,j) in this square are equivalent to the original square cell values (i,j) + 11. This is true for all magic squares, they all can be derived from the first by adding some constant factor. Also, the original square has multiple configurations, which can be generated by rotations or flips of the original matrix.

Thus, to solve this problem, you can try all rotations and flips of the original matrix, check that the given values minus the original matrix values are equal, add this difference to all unknown cells and check if the matrix is a magic square. The easiest way to do the rotations and flips to compute all permutations of the array 1 through 9. We can easily do this in C++ in a few lines. The solution for magic squares would look something like the following.

Assume the unknown matrix is stored in an array of chars called matrix[]. Also, assume we have a function called isMagicSquare that will check whether a given array is a valid magic square configuration.


char matrix[];
int v[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
do {
 if(isMagicSquare(v)) {
   int diff = (matrix[0] - '0') - v[0];
   int i = 1;
   for(; i < 9; i++) {
     if(matrix[i] != 'X' && diff != (matrix[i] - '0') - v[i]) {
       break;
     }
   }

   if(i == 9) {
      printSolution(v, matrix);
      break;
   }
} while(next_permutation(v, v+9));

The last problem was called "Building teams". Dan eventually solved this problem after the practice session was complete. After you decipher the problem, it boils down to graph coloring with at most four colors. Each clique of students is a node and a node is adjacent to another node if the clique's dislike each other. You have to attempt to color the nodes such that adjacent nodes do not have the same color. Since graph coloring with more than two colors is NP-Complete, this should give you a hint that an inefficient backtracking algorithm should work. Even though there are at most 30 nodes, the colorings prune quite quickly as many of the 4^30 possibilities are equivalent.

Assume we have an array called nodeColors, which we will store all our colors in. Also assume we have a function called validColoring, which makes sure a given color assignment is valid, that is no adjacent nodes have the given color. Then we can color the nodes recursively doing something like the following.


// our node colors
int nodeColors[30];

// recursive function to assign colors, currentIndex is the current node
// maxColors is the max colors we are going to try
bool assignColors(int currentIndex, int maxColors) {
 if(currentIndex > N) return true;

 // try assigning all colors
 for(int i = 0; i < maxColors; i++) {
    // make sure this is a valid coloring for this node
    if(validColoring(currentIndex, i)) {
       nodeColors[currentIndex] = i;
       if(assignColors(currentIndex+1, maxColors)) {
          return true;
       }
       nodeColors[currentIndex] = -1;
    }
 }

 return false;
}

Next, call this function with maxColors equal to 1, 2, 3, and 4. The first one that returns true is the number of teams, if none return true, then you can't build the teams.

Knowing your libraries

2009-01-28T13:09:00.001-08:00

Since I've started competing on TopCoder the lesson of knowing your libraries has been really hammered home for me. I was, of course, never against this, but often I would write my own functions to check alphanumeric values, parse integers and doubles, format output, and so forth. These don't take that much time to write, but it's still time away from writing the actual solution to the problem. Also, there's always a chance you'll make a typo or logic error, which can be costly.

I worried less about this when I use to compete in the ACM competitions because since it's 5 hours, it's almost more like a marathon than a sprint. However, on TopCoder, you generally know that the top people are going to solve all 3 problems, the only way to beat them is by being faster.

This can be true for the ACM competitions as well. This year at the Pacific Northwest Regional, something like 10 teams solved 7 problems, but only one of those teams qualified for the world finals. Because UBC was at the top of that heap, they are off to Stockholm for the finals.

Recently, in a practice competition on TopCoder I did a problem where you're given a string and you need to return a vector containing two substrings of the original string. The first substring has to have the same number of a's as the number of b's in the second substring.

This is pretty easy to solve. I did something like the following:


vector getSubstrings(string str) {
  string x, y;
  x = str;

  while(1) {
    int c1 = count(x, 'a');
    int c2 = count(y, 'b');
 
    if(c1 == c2) break;

    y = x[x.size()-1] + y;
    x = x.substr(0, x.size()-1);
  }

  vector ans;
  ans.push_back(x);
  ans.push_back(y);

  return ans;
}

The key here is the "count" function. I actually wrote my own count function. Sure, it's just a for loop, but it's an extra 4-5 lines of code. There's actually a count function built into the C++ STL. The fastest solution for this SRM used this function. With this function, my loop above could be something like this:


while(count(x.begin(), x.end(), 'a') 
        != count(y.begin(), y.end(), 'b')) { ... }

I scored something like 245 points on this problem, but by using a few language built-ins, I probably could have had 247 or 248. Oleg and I have actually had practices where we were separated by this small a margin, so every little bit helps.

Another library I've recently opened my eyes to is the C++ istringstream. It's great for parsing input for certain types of problems. For example, if you had to read in a list of comma separated doubles like "-234.34, 324.234, 3243.22232,876.435", you can quickly parse this with istringstream. It works similar to cin.

Example:


string s  = "-234.34, 324.234, 3243.22232,876.435";
// replace commas with spaces
replace(s.begin(), s.end(), ',', ' ');

istringstream ss(s);
double d;
while(ss >> d) {
  cout << d << endl;
}

You could of course do this by processing the string character by character, but that can be messy and error prone.

The stringstream class is also useful and works similar to cout. One use is to convert doubles into strings.

Example:


// create a double
double d = 1.22423;

// create a stringstream and put our double into the stream
stringstream ss;
ss << d;

// convert our stream into a string
string s = ss.str();

TopCoder Practice - SRM 308

2009-01-28T10:53:00.000-08:00

I did a practice SRM on TopCoder this morning with my friend Oleg. It was SRM 308 Div 2. It went reasonably well, we both got 2 out of 3 accepted. Oleg submitted the 1000 point problem but made a simple mistake by calling the min function rather than max function in one place. I didn't end up submitting the 1000. Oleg beat me by about 20 points as he finished the second problem faster than me.

The first problem was probably one of the easiest 250 point problems I've done on TC and I got it submitted faster than any problem I've done before (249.30 points). The problem was given a vector of integers, return the median or -1 if no median exists. I simply sorted the vector, if the size of the vector was odd, return v[v.size()/2], otherwise return -1.

The second problem was with decoding strings that were encoded using Huffman codes. In Huffman codes, characters in a string are replaced by bit strings. A Huffman code has the property that no bit string representation of a character is a prefix of another bit string. So, for example, the following are valid codes: A="00", B="10", C="01", and D="111", but A="00", B="0010", C="01", and D="111" is not because the encoding for A is a prefix to B.

Using the valid codes above we can encode the string ABACD as "00100001111". In the problem, you're given the codes plus the encoded string and you have to decode it.

This is pretty straightforward. You can loop through your encoded string, loop through your dictionary and try to match the dictionary word with the corresponding substring in your encoded string. If they match, then that's the letter you want. Save that letter and move your current index in your encoded string ahead by the length of the dictionary word. Continue this until your current index is greater than the length of your encoded string.

The third problem, which I didn't have time to complete, required a combination of dynamic programming (DP) with greedy. You have a bunch of treasure items, which have a cost value and weight value. You want to maximize the total cost of collecting items but not collect more than W amount of weight. This is a pretty classic DP problem. The catch is that in this problem, some treasure items can be divided into smaller pieces. For example, you could take 10% of an item or 30% or whatever.

I didn't read the problem as carefully as I should have so I immediately coded the DP part. Then I tried to retrofit this to accommodate the case of using only partial amounts. That didn't go all that well :-). I was getting some of the sample solutions, but not all. I eventually realized I needed to consider the full and partial items separately, but it was too late to finish that.

The solution is to use DP with all items that can't be divided. You do this by making a cost array, where the indices represent the weights. You store in each index the maximum cost you can get for the given weight.

This is calculated as follows:

Assume we have an array of non-divisible item weights called w and costs called c.


for i = 0 to size(w) 
  for j = 0 to W
     cost[j + w[i]] = max(cost[j + w[i]], cost[j] + c[i]);

The second part is the greedy section. You sort all divisible items by their weight to cost ratio. Loop over your cost array and for each weight you've succeeded in making previously, loop over all divisible items. For each divisible item, calculate the cost of adding that item to your current weight provided the combined weight is less than W. After this inner loop, update your best cost if the cost you just made is better than any you've seen previously.

It should look something like this:

Assume we have an array of divisible items weights called wd and costs called cd, which have been sorted by their ratios.


bestCost = 0;
for i = 0 to size(cost)
  if cost[i] != 0
     currentCost = cost[i] 
     weight = i;
     for j = 0 to size(wd) 
         weightDiff = min(W - weight, wd[j])
         currentCost = cd[j] * weightDiff / wd[j]
         weight += weightDiff;
         if(weight >= W) break

     bestCost = max(bestCost, currentCost)

Despite not getting the third problem, Oleg and I both would have been in the top 30 for this SRM.

Contest preparation

2009-01-26T09:35:00.001-08:00

I posted this week's problem of the week challenge on the UVic programming club website. You can check it out here if you're curious. It's based in part on a problem I did years ago at one of my first contests. It's not a really challenging problem, although some people may struggle with the parsing and this is in part why I chose this problem. The students main hurdle at the moment is with knowing how to best read in input, so hopefully this problem will give them a little extra practice.

The actual undergraduate competition that I am organizing is less than a week away, January 31st. I still have a fair amount to do, like print off all the problems, instructions, login information, and organize it into envelopes. I also need to get all the sample input files, links to APIs, and program submitting software (PC^2) on all the contestant accounts. I plan to set up a scoreboard in the lab where we're hosting the contest using the projector and screens available.

One of the instructors at UVic is organizing the prizes and pizza for after the contest. I plan to pick up some munchies in the morning on the way in so that people will have something to munch on prior to the competition.

Unrelated to this. I submitted my solution to the 500 point from the TopCoder SRM 433. Passed with flying colors. Ugh, depressing :-(. (Check out my post from Jan. 21st for details).

Practice Sessions - Week 3

2009-01-23T10:00:00.000-08:00

We had our third week of practice last night. Approximately 10 people were there, so the numbers are staying consistent. I'm hoping that we'll have about 15 for the competition on the 31st.

Ian Bull showed up at the beginning to talk about the Google Summer of Code project. He participated last year and is possibly mentoring this coming summer. We both thought the club members might be interested in the opportunity.

At the meeting we first went over last weeks problems. I did this rather quickly, so I'm not sure whether everyone followed my discussion. I decided to have a little mini-contest last night. In previous weeks, I've been splitting people up into experienced and newbies, where the experienced people work on harder problems, but this week everyone worked on the same set of four problems.

I told everyone that the person that solves the most problems would win a prize. The extravagant prize turned out to be a Snickers bar! I mocked up a scoreboard on the whiteboard to keep track of everything.

Dan Sanders ended up winning with three problems solved. He solved the three in about an hour and fifteen minutes, but was stuck on the last. I eventually told him to move onto solving the problem of the week instead. Unfortunately, most of the other experienced guys either had to come late or leave early, so Dan didn't have any major challengers. Two others, Tristin and Kevin, solved two problems each, and everyone solved at least one.

The four problems came from a mixture of problems I had used at old contests I ran at UNB.

The first problem was a very simple problem where you need to determine whether a car is speeding or not, based on different speed limit zones and the cars speed through that zone. Everyone solved this one.

The second problem was a card game simulation called "Beat the Devil". It's not too devilish (sorry, bad pun), but it requires a bit of input processing and logic. You to read in a deck of cards and simulate the logic of the game.

The third problem was a geometry problem. The break down of the problem is that given a bunch of points, you need to find the largest triangle that can be made from the set of points that does not contain any other point. I give the area formula for a triangle in the problem and a hint about how to easily detect if a point is within a triangle. To do that, you can form three triangles between the given point and the vertices of the triangle. If the sum of the area of those three triangles equals the area of the original triangle then the point is within the triangle. There are other tests, like using dot products to see which side the point is relative to the lines of the triangle or using the general point in polygon test.

The last problem was the hardest one. In the problem you have pennies, nickels, and dimes and you want to buy X candies, each of which costs 8 cents. If you put more than 8 cents in, the machine gives you back change using the least number of coins. In the problem, you must buy the X candies using the least number of coins possible.

Initially, the problem looks easy and it looks like you can solve it by using the largest coins first (greedy algorithm), however, this is not necessarily optimal.

For example, if we consider the case of wanting to buy 6 candies where we have 3 pennies, 10 nickels, and 0 dimes, then the greedy algorithm gives us the following answer:

Pennies	Nickels	Dimes	Candies	Coins used
3	10	0	0	0
5	8	0	1	2
7	6	0	2	4
9	4	0	3	6
11	2	0	4	8
13	0	0	5	10
5	10	0	6	18

That's 18 coins used. The optimal only requires 16 coins. In the optimal, we pay for a candy with 3 pennies and a nickel when we can, that way we save a nickel and don't end up having to use 8 pennies at the end.

Pennies	Nickels	Dimes	Candies	Coins used
3	10	0	0	0
0	9	0	1	4
2	7	0	2	6
4	5	0	3	8
1	4	0	4	12
3	2	0	5	14
5	0	0	6	16

This often happens with greedy algorithms, it turns out they are wrong because the locally optimal decisions made don't necessarily translate to a global optimal.

You have to use dynamic programming to solve this problem. In my solution, I recurse on every way that you can buy a candy using your current coin configuration and store the minimum number of coins used to reach a solution in a table so that I can prevent recalculating answers I calculated earlier.

This is the essence of dynamic programming or memoization. You can cut off recursion branches where you've already calculated the solution to a sub-problem. However, it's not always obvious what the recursion is.

TopCoder - SRM 433

2009-01-21T10:50:00.000-08:00

I competed in SRM 433 on TopCoder this morning. It didn't go all that well. I solved the first problem quickly, although I could have been a little faster.

The problem was to minimize an expression S = A1*B1 + A2*B2 + ... AN*BN, where A and B are vectors of integers and you can re-order A in anyway you choose. The solution is simple, sort both vectors, one in ascending order and one in descending, and then multiply the two vectors together. The small numbers from A end up being multiplied by the large numbers of B, which gives you the smallest possible S. I wasted a bit of time writing an operator to sort in descending order, when I could have just sorted both A and B in ascending and multiplied the values of A starting at 0 through N-1 against B starting at N-1 through to 0.

When I first read the second problem, I realized that it would probably involve using C++'s next_permutation algorithm from the STL and basically bruteforcing an answer. However, I wasted a lot of time trying to understand exactly what was asked in the problem. Frustrated by the problem, I went and looked at the 1000 point problem for a bit. It looked reasonable, but I abandoned it as I felt with the time left, I should probably try to fix my 500 point problem.

When I finally got my 500 point solution to come out with the right answers, it was too slow on the larger test cases. Just as I fixed it to run under the time limit, the contest ended, and I couldn't submit. If I had have had 30-60 more seconds, I would have had it in. So, now I have a complete solution sitting on my laptop that I didn't even get to submit. Very frustrating.

I think only one person solved all 3 problems from the competition, so I could have been possibly in the top 50 or so if my second problem was submitted. Unfortunately, I ended up 195th, so my TopCoder standing hardly changed.

My friend Oleg competed in Div 1. The Div 2 500 point problem was the 250 point problem in Div 1. Oleg had similar difficulties with the problem, so his standing also hardly moved.

I'm somewhat happy I didn't move into Div 1 right now as I would like a chance to redeem myself in Div 2 before moving on. My next chance will be Feb. 7th. Why is it that practice sessions always go better than real competitions? :-)

First post! Becoming the coach.

2009-01-20T10:17:00.000-08:00

Through 2003 to 2005 I participated in the ACM ICPC university programming competitions for the University of New Brunswick. I made the world finals in both 2003 and 2005. Participating and training for these competitions are some of my most vivid and fun memories from my undergraduate years. I learned more about algorithms, data structures, language syntax, attention to detail, and problem solving during these years than I ever did in my classes.

In the Fall of 2005, I moved from New Brunswick to Victoria, BC to start my PhD and I "retired" from the ACM ICPC programming scene. However, in Fall 2008 I was approached by some UVic faculty to be involved with starting a team. The university hadn't had a team in close to 20 years. I originally promised my wife that my involvement would be minor, as she still clearly remembers my programming obsessed years of 15+ hours of practice a week, but once I started talking about the contests again, it was difficult to stop. I was quickly sucked back into the world of programming contests.

I agreed to be the coach for the UVic team and I spent 3-4 weeks trying to get the team up to speed. In November, 2008, I took them to Vancouver, where they competed in the Pacific Northwest regional, placing 30th out of 82 teams.

The guys could have easily been in the top 20 with a little luck and more experience, as a simple mistake on their second problem cost them close to 2 hours in debug time. However, I was extremely proud of their effort and how they came back after that initial set back.

Following the regional competition, I started a problem of the week challenge as an attempt to recruit other undergraduates that might be interested in participating in the competitions. Each week I post a new problem. Based on the difficulty of the problem, a solution is worth different amounts of points. I keep track of what people solve and I help the students either with solving the problem or debugging their code. You can check out the problems on our website: http://www.csc.uvic.ca/content/contest/?q=node/8

As a consequence of becoming the coach, I also ended up getting back into contest coding and competing myself by participating on TopCoder. I also convinced my good friend Oleg Golubitsky to compete and I now think he's more obsessed than me :-).

As another strategy to get students involved, I decided to organize a programming competition for undergraduates in the Spring of 2009. This contest is set to happen in less than 2 weeks on Jan. 31st. While at UNB, I ran several such competitions, and they were always a great experience. Myself and another member of my research lab, Ian Bull, wrote the problems and Oleg wrote alternative solutions to help us verify our judge's solutions. We plan to have prizes for best 1^st, 2^nd, 3^rd, and 4^th year student along with best overall and perhaps some door prizes.

I also started weekly practice sessions and myself plus an instructor (Jason Corless) at UVic recruited students for this by going around to classrooms and telling people about the contests. We've had two practice sessions so far and they have been going reasonably well. The first week there were about 15 students and the second week there were 9 or 10. Many of the students solved one problem the first week and the second week everyone solved at least one. Last week, I offered a prize to the first person to solve two problems. Ryan Petty ended up winning a Coffee Crisp for his effort :-). I'm hoping I can keep the numbers up so that we can send 2-3 teams next year to the regional.

This brings my programming competition story up to date. I'll be continuing to chronicle this experience as well as discuss solutions to various programming problems.