Match Editorials

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.

Although there were more submits for the medium DaViDeX stayed in the lead until half an hour into the round when newcomer and andrei.12, having skipped the medium, put in a surprising 828.56 point submission for the hard and became the top scorer. The other coders went through the easy and medium problems quicky but were stuck on the hard.

By the hour mark, the contestants seemed to have gotten a hang of the 1000 pointer and the submissions started rolling in. At the end of the challenge there were a large number of submits across the board. The subsequent challenge phase was quite lively, it proved to particularly fruitful for neal_wu who racked up 4 successful challenges and took over as the top scorer. On the other hand andrei.12's lightning quick submit on the hard proved faulty and saw him drop out of contention.

The system test phase did not throw up too many surprises and the challenge ended with neal_wu from the United States taking the win, DaViDeX picking up second and victorj third. The best newcomer was 5^th place finisher nahnhnahk from Vietnam.

The Problems

Value	250
Submission Rate	61 / 70 (87.14%)
Success Rate	46 / 61 (75.41%)
High Score	eagaeoppooaaa for 247.47 points (2 mins 52 secs)
Average Score	189.70 (for 46 correct submissions)

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.

In the solution, ("" + i) + notAllowed[i] is used to generate the forbidden numbers and (""+roomNumber).indexOf() is used to check if they are present.

    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";
    }    

Value	500
Submission Rate	46 / 70 (65.71%)
Success Rate	37 / 46 (80.43%)
High Score	DaViDeX for 481.20 points (5 mins 39 secs)
Average Score	362.06 (for 37 correct submissions)

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;

Value	1000
Submission Rate	20 / 70 (28.57%)
Success Rate	6 / 20 (30.00%)
High Score	neal_wu for 644.19 points (24 mins 7 secs)
Average Score	478.92 (for 6 correct submissions)

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.