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.
