Thursday, June 26, 2008 Match summary
TCHS SRM 51 was held at the same time as SRM 407 and was marked by the use of a common problem between the
two challenges. Unfortunately, this meant that coders could not compete in both of them. However, after a few issues
with double registrations were resolved, HS round 51 got off to timely and speedy start.
eagaeoppooaaa started things off with a submit on the easy barely three
minutes into the round. The next few minutes saw more submits on the 250 pointer. However, it was the ten minute mark
that saw the first submit on the medium, and the taking of the lead by
DaViDeX.
The ProblemsMissingDigitsUsed as: Division One - Level One:
This problem had two part, the first was to generate the forbidden numbers and the second
to check and see if they were present. Both these steps were considerably shortened if one knew some basic string
operations. public String isAllowed(int[] notAllowed,int roomNumber) { for(int i = 0;i < notAllowed.length;i++) { if((""+roomNumber).indexOf(("" + i) + notAllowed[i]) > -1) return "NO"; } return "YES"; }AuctionHouse Used as: Division One - Level Two:
The medium was another in which experience with strings and parsing helped. Algorithmically, the problem was not that difficult, the basic idea was to build a table with the items, update them according to the bids made and finally output the result in the required format. for(i = 0;i < bids.length;i++) { //Parsing and addition to table String[] tokens = bids[i].split("[ ]"); boolean found = false; for(j = 0;j < nitems;j++) if(items[j].equals(tokens[1])) { //update according to bids found = true; if(maxbid[j] < Integer.parseInt(tokens[2])) { maxbid[j] = Integer.parseInt(tokens[2]); bidder[j] = tokens[0]; } } //Addition to table if(!found) { nitems++; maxbid[j] = Integer.parseInt(tokens[2]); bidder[j] = tokens[0]; items[j] = tokens[1]; } } //Format and return the result String[] ret = new String[nitems]; for(i = 0;i < nitems;i++) ret[i] = bidder[i]+ " got " + items[i]; return ret;CheapestRoute Used as: Division One - Level Three:
As cost of teleport usage depends on number of teleports used before, number of a current cell isn't enough to define current position. So we will use a pair (a,b), where a is a cell number and b is a number of teleports already used, to define our position in the corridor. The weight of a move can be defined by a pair (a,b), where a is a cost of this move and b is time needed for this move. As we are looking for the cheapest route with as small number of moves as possible for such cost, the comparison for two moves will be defined as: (a,b) < (c,d) <=> (a<c) or ( (a=c) and (b<d) ). Now we can introduce the graph with vertices numbered as (a,b) (meaning of a and b is described above), representing our position in the corridor, and edges with weights given using pairs (also introduced above), representing walking and using teleports. Our goal is to find a path from vertex (0, 0) to vertex (n-1, i) (where i can take any value) with the minimum weight. This problem can be solved using any shortest-path algorithm. You can see the implementation of this idea here.
|
|