|
Match Editorials |
TCHS SRM 27Monday, January 8, 2007
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.