Match summary

Many competitors tripped on a tricky 500-point problem that was easy to get wrong, but not nearly as easy to get wrong as the 1000-pointer. In the end five coders got all three problems correct; Weiqi was one of them, and won with a comfortable lead. The other four followed in the rankings and deserve to be mentioned for great performances: tashin, i_bogatyi, TICKET_112022 and ilyaraz.

The Problems

BrickMystery

Used as: Division One - Level One:

Value 250

Submission Rate 201 / 227 (88.55%)

Success Rate 187 / 201 (93.03%)

High Score sluga for 246.94 points (3 mins 10 secs)

Average Score 199.32 (for 187 correct submissions)

Finding the 7-bit binary represnentation of an integer was the core of this problem. This can be done by repeatedly dividing the number by 2 and saving the remainders, which give the digits in reverse order. The rest of the problem is pretty-printing the values. Here's one Java implementation:

   public String[] createPattern(String message) {
      String[] ret = new String[2 + message.length()];
      ret[0] = ret[message.length()+1] = "x.......x";

      for ( int i=0; i<message.length(); ++i ) {
         ret[i+1] = "x";
         int x = message.charAt(i);
         for ( int j=0; j<7; ++j ) {
            ret[i+1] = ".x".charAt( x%2 ) + ret[i+1];
            x /= 2;
         }
         ret[i+1] = "x" + ret[i+1];
      }

      return ret;
   }

Armies

Used as: Division One - Level Two:

Value 500

Submission Rate 151 / 227 (66.52%)

Success Rate 87 / 151 (57.62%)

High Score Weiqi for 457.05 points (8 mins 52 secs)

Average Score 329.48 (for 87 correct submissions)

The rules in the problem statement don't give an explicit algorithm for determining the order in which the creatures attack. However, we can devise an algorithm that considers creatures that are left and selects the next creature to attack:

The next creature to attack has the highest might of all remaining creatures.
If more than one creature from different armies has the same highest might, we select a creature from the army that didn't attack last.
If there's still more than one choice inside a single army, select the creature that comes earlier in the input.

It can be verified that this algorithm generates an ordering that satisfies all three rules from the problem statement (the problem statement also guarantees that this ordering is unique). However, you need to be careful to handle all the tie-breaking rules correctly. For a clear implementation, see sluga's solution.

AdaptiveRouting

Used as: Division One - Level Three:

Value 1000

Submission Rate 17 / 227 (7.49%)

Success Rate 5 / 17 (29.41%)

High Score ilyaraz for 572.50 points (29 mins 42 secs)

Average Score 483.94 (for 5 correct submissions)

The behavior of the network is entirely deterministic and, since we're observing through an all-knowing perspective, simulation is the solution to this problem.

Each router maintains a copy of the network layout and runs its shortest-path algorithm on that graph (which may be different than the graphs in other routers). This means that, in our simulation, we need to keep a separate graph for each router. In addition, these graphs change over time as information about failed links reaches routers. The simulation needs to be time-oriented so that each router acts only upon information available to it at some moment in time.

The simulation itself can be implemented using a priority queue of events. An event describes the arrival of a packet at some router and needs to contain the following information:

The time at which the packet arrives,
The router at which the packet arrives, and
The packet itself – if it is the data packet or a control packet (if it's a control packet, we also need to know which link it is about).

To start off the simulation, we generate two events for each failed link – at time 0, a control packet is generated in the two points that the link used to connect. We also generate a single data packet at time 0, in router A. What is left is to process the events in increasing time order and:

When a control packet arrives at a router, relay it to all neighbors that don't know about the failed link yet, generating new events. (Alternately, send to all neighbors and have them discard information they already have.)
When the data packet arrives at a router, calculate the shortest path to the destination (passing solutions used Dijkstra's, Floyd-Warshall and even Bellman-Ford algorithms) and send the packet to the first router on that path (generating a new event). One trick is to run the single-source shortest path algorithm from the destination router for tie-breaking purposes.

When the data packet arrives at the destination, we're done and can return the time at which this occurred. If at some point a router calculates that there is no path to the destination, we can return –1 (because a new route to the destination won't magically appear).

The long and convoluted problem statement served as a hint that competitors needed to pay a lot of attention to the details while coding. Indeed, the problem offered plenty of opportunities to get the implementation wrong.

By lovro
TopCoder Member