Saturday, May 15, 2004 Match summary Saturday competitions are slowly gaining acceptance and it is wonderful to see that over 350 contestants turned up. For many international competitors it is the perfect opportunity to gain some valuable TopCoder experience. Division 1 coders had little trouble completing their easy. Once this was out of the way, coders faced a puzzling medium. The medium turned out to be easy to code once the solution became apparent. As often Antimatter started the match in great style with fast submissions on the first two problems. He was closely followed by a hungry pack of reds. The challenge phase had its fair share of challenges. jshute picked up two successful challenges, which in the end, gave him his second SRM win. texel continued his assault of the top by finishing in a well deserved second place. The bronze went to Yarin who gained his target back and became a record 10th member of the elite group of "targeteers". Division 2 received a whole bag of incredibly fast submissions on the easy problem. The medium was generally well answered too. Nearly one third of coders attempted the hard, but only 6 were rewarded for their efforts. Icedawn finished on top. He was followed by decypher and Joker who were separated by less than a point. First timer Zis earned a respectable fourth and a healthy yellow rating.
The ProblemsSoccerUsed as: Division Two  Level One:
There were a few records broken on this problem. Congratulations to Sleeve for having the fastest solution for any problem ever! Just as amazing was the fact that only one coder failed this problem! The problem deals with the standard scoring system found in most soccer leagues. Teams receive 3 points for each win and 1 point for each draw. Thus the total score for team i becomes 3*wins[i]+ties[i]. The rest of the problem is simply a matter of memorizing the highest total. Here is the code: public int maxPoints(int[] wins, int[] ties) { int max=1; for (int i=0; i<=wins.length1; i++) max=Math.max(max,3*wins[i]+ties[i]); return max; }ThirtyOne Used as: Division Two  Level Two: Used as: Division One  Level One:
In the game of Thirty One, players aim to collect a hand of 3 cards in a way that maximizes the total value of the hand. The scoring system is very similar to that of Blackjack, with the exception that 3 identical cards produce a value of 30.5. A good way to start the problem is to write a function that evaluates each card: public int card(String card) { if (card.equals("A")) return 11; if (card.equals("J")  card.equals("Q")  card.equals("K")) return 10; return Integer.parseInt(card); }Note that we have assigned Ace to have a value of 11. The only time when Ace should be 1 instead of 11 occurs when the hand exceeds 31. Thus if our total is over 31 then we know that we have to subtract 10 to accommodate this change. One other case that we need to consider is when the total is 30.5. Many coders chose the safe path of having integer total and doubling 30.5 to 61. In this problem however, it is just as safe to use doubles. Geared with this knowledge, we can now go through the list of hands, evaluate each hand and keep track of the hand with the highest total: public int findWinner(String[] hands) { int pos=0; double max=1; for (int i=0; i<=hands.length1; i++) { String[] cur=hands[i].split(" "); double total=0; for (int k=0; k<=cur.length1; k++) total+=card(cur[k]); if (cur[0].equals(cur[1]) && cur[1].equals(cur[2])) total = 30.5; if (total>31) total=10; if (total>max) { max=total; pos=i; } } return pos; }For the complete implementation of this have a look at writer's solution in the practice rooms. DiskScheduler Used as: Division Two  Level Three:
Many coders falsely mistook this problem as an easy 1000. However as coders found out, initial looks can be deceiving. The problem cannot be solved by simply rotating the disk clockwise or counterclockwise until all sectors have been serviced. The optimal solution can involve rotating the disk in one direction and then rotating in the opposite direction. Since this is a Division 2 problem after all, we can expect to be able to solve this without the need of complex algorithms. We begin the solution by writing a function that returns the distance from sectorA to a sectorB depending on the proposed direction of traversal. Direction will be 1 for clockwise and 1 for counterclockwise: int dist(int sectorA, int sectorB, int dir) { int count=0; while (sectorA!=sectorB) { sectorA+=dir; count++; if (sectorA==101) sectorA=1; if (sectorA==0) sectorA=100; } return count; }We proceed by showing that the optimal solution will at most have one reversal of direction. Suppose there exists a path which is both optimal and has two reversals of direction then clearly within that path will lie a smaller path. All that we need to do now is try all sectors that could be our reversal locations. Finally, we must try going both clockwise and counterclockwise to reach those locations. Our final return is the minimum distance of all those combinations: public int optimize(int start, int[] sectors) { Arrays.sort(sectors); int min=Integer.MAX_VALUE; for (int i=0; i<=sectors.length1; i++) { int previousSector=sectors[(i1+sectors.length)%sectors.length]; int nextSector=sectors[(i+1)%sectors.length]; //go clockwise then counterclockwise int dist1=dist(start,sectors[i],1); //check if reversal is required if (dist(start,nextSector,1)>=dist1) dist1+=dist(sectors[i],nextSector,1); //go counterclockwise then clockwise int dist2=dist(start,sectors[i],1); //check if reversal is required if (dist(start,previousSector,1)>=dist2) dist2+=dist(sectors[i],previousSector,1); min=Math.min(min,Math.min(dist1,dist2)); } return min; }For the complete implementation of this have a look at writer's solution in the practice rooms. OddsAndEvens Used as: Division One  Level Two:
As Windrider exclaimed after the match: It's a puzzle! It's not a math question, nor is it a "remember the algorithm" thing, it's a puzzle! There were quite a number of ways for solving this problem. However, most solutions began with a loop that counts the number of odds and evens in both sums and products: for (int i=0; i<=products.length1; i++) { if (sums[i].equals("ODD")) oddsInSums++; else evensInSums++; if (products[i].equals("ODD")) oddsInProducts++; else evensInProducts++; }The total number of integers used could be calculated like so: int total=0; while (total*(total1)/2 != sums.length) total++;We notice that the only way we can get an odd result in products is by multiplying two odds. Thus the original number of odds must be some value x such that x*(x1)/2 = oddsInProducts. We also notice that the only way we can get an odd result in sums is by adding an odd and an even. Thus the original number of evens must be some value y such that x*y = oddsInSums. We now try all possibilities of original number of odds (x) and evens (y). If no possibility works then we return "IMPOSSIBLE". The final code looks like this: for (int x=0; x<=total; x++) { int y=totalx; if (x*(x1)/2==oddsInProducts && x*y==oddsInSums) return "EVEN "+y+" ODD "+x; } return "IMPOSSIBLE";For the complete implementation of this have a look at writer's solution in the practice rooms. IslandFerries By lbackstrom Used as: Division One  Level Three:
This problem boils down to finding the shortest paths in a directed graph
with weighted edges. The trick to solving it is to create the proper
graph, and then you can run a breadth first search, or Djikstra's
algorithm to find the shortest path from the start node to each of the
other nodes. From the problem, we see that we can be at any island, and
can be holding up to three tickets, none of which may be the same. From
this, we can construct the nodes in the graph: each node corresponds to
being at an island with a particular set of tickets. Hence, there are at
most 40 * choose(10,3) = 1200 nodes in our graph, a very manageable
number. Now, the next step is to construct all the edges in our graph. To
get from one island to another, we have to use up a ticket. These edges
have weight 0, since using a ticket is free. The other edges in the graph
are related to buying tickets. From each node, there is an outgoing edge
corresponding to each type of ticket not already held. That edge has a
weight equal to the purchase cost of the ticket. For example, we can
write down nodes as tuples whose first element is the island we are at,
and whose other elements are the tickets held, in order. For example
(7,0,1) indicates that we are at island 7 with tickets 0 and 1. If ticket
3 costs 164 at island 7, then we add an edge from (7,0,1) to (7,0,1,3) of
weight 164. If there is a leg from island 7 to island 4 on ferry 3, then
we add an edge from (7,0,1,3) to (4,0,1) of weight 0. initialize queue q initialize table best insert (0) into q while(q is not empty) tuple t = q.removeFirst() foreach (tuple t' which is reachable from t) int cost = best(t) + weightFrom(t,t') if(best does not contain t' or best(t') >; cost) q.insert(t') best(t') = cost end end end
The above code is pretty standard, and the trick is implementing it. The
queue can be implemented as a linked list, or just a really big array.
The table can be implemented in a number of different ways, depending on
your implementation of the tuples. If you are like me, and prefer to keep
things primitive, you'll use a bitmask to represent your tuples. Hence,
being at island i, with tickets j, k, and l can be represented as a
single integer (i<<12) + (j<<8) + (k<<4) + l.
This allows us to implement the queue as a big array of integers, and
best as an array with 40<<12 = 163840 elements. 
