Get Time
statistics_w  Match Editorial
SRM 383
Thursday, December 13, 2007

Match summary

SRM 383 came a mere 38 hours after the previous SRM, giving coders barely enough time to finish working through the problems in the practice room before being back in the arena for another match. Nevertheless, 924 competitors showed up for the main event, with another 74 competing in the TopCoder College Tour.

In Division 1, coders were greeted by an easy problem which was perhaps more straightforward than has been the case in recent matches. However, there were a few pitfalls to watch out for and a couple of tricky cases that weren't covered in the examples. A dynamic programming problem was next up for the medium, while the evil hard problem only tempted 2 coders to submit solutions.

The top-ranked coders brushed off the first two problems in no time, which lead to a number of very close scores going into the challenge phase. While Petr's position at the top of the division looked unassailable, few points separated the next 20 positions. There was a particularly interesting battle between gevak and marek.cygan, who were competing in the same room and had entered the challenge phase separated by less than a point. The system tests confirmed that Petr's hard solution was correct and it cemented his 34th SRM win. gevak had powered through the challenge phase, taking 175 points to take second position, while marek.cygan took the bronze medal.

In division 2, the challenge phase was somewhat less exciting, with none of the eventual top 5 gaining or losing any points. Newcomer quynhtrang212 lead from the start and won the division, while mohamad_jrs took second and yazhini took third.

The Problems

FloorLayout rate it discuss it
Used as: Division Two - Level One:
Value 250
Submission Rate 388 / 455 (85.27%)
Success Rate 359 / 388 (92.53%)
High Score tollek for 245.41 points (3 mins 54 secs)
Average Score 190.88 (for 359 correct submissions)

This problem simply required you to count the number of boards in the image. The trick was to scan over the whole image counting squares, but making sure that each board is only counted once. There were several ways to do this: some coders erased the entire floorboard as it was counted the first time; others only counted one end of each board, by checking if the previous square was also part of the same board.

C++ code implementing the second method follows.

class FloorLayout{
  int countBoards(vector <string> layout){
    int count = 0;
    for (int i=0;i<layout.size();i++)
      for (int j=0;j<layout[i].size();j++)
        if (layout[i][j] == '-'){
          if (j==0 || layout[i][j-1]=='|') count++;
        } else {
          if (i==0 || layout[i-1][j]=='-') count++;
    return count;

Planks rate it discuss it
Used as: Division Two - Level Two:
Value 500
Submission Rate 285 / 455 (62.64%)
Success Rate 123 / 285 (43.16%)
High Score ygge for 462.61 points (8 mins 12 secs)
Average Score 322.44 (for 123 correct submissions)
Used as: Division One - Level One:
Value 250
Submission Rate 465 / 469 (99.15%)
Success Rate 372 / 465 (80.00%)
High Score bmerry for 246.77 points (3 mins 15 secs)
Average Score 199.45 (for 372 correct submissions)

This problem was on the easy side for the Div I easy/Div II medium, but nevertheless had a couple of "gotchas" to catch out unwary coders. The basic strategy was to try every possible final length and see how much money we could make by cutting planks to that length. Consider cutting the planks to a common length of L. The number of new planks we can obtain from the plank with index i is given by integer division lengths[i] / L. The number of cuts is given by (lengths[i] - 1) / L. This was the first place where coders could slip up as only the last example contained a case where a board was an exact multiple of the optimal length (which is the only time that the number of new planks differs from the number of cuts).

Next we have to work out the maximum amount of money we can make at a given length. For a single plank, this is clearly

(L * number of new planks * woodValue) - (number of cuts * costPerCut).
However, it is important to notice that if this value is negative, then we should throw the board away instead. Many solutions failed because they cut as many smaller planks as possible at a given length, regardless of whether it was profitable to do so or not. Again, the last example gave a significant hint that this might be an issue, but didn't make the solution completely obvious.

We can then simply take the length that gives the best profit and return that value. C++ code follows.

class Planks{
  int makeSimilar(vector <int> lengths,int costPerCut,int woodValue){
    int bestProfit = 0;
    for (int newLength = 1;newLength <= 10000;newLength++){
      int profit = 0;
      for (int i=0;i<lengths.size();i++){
        int newPlanks = lengths[i] / newLength;
        int cuts = (lengths[i] - 1) / newLength;
        if (newPlanks * newLength * woodValue > cuts * costPerCut)
          profit += newPlanks * newLength * woodValue - cuts * costPerCut;
      bestProfit = max(bestProfit,profit);
    return bestProfit;

HillWalker rate it discuss it
Used as: Division Two - Level Three:
Value 1000
Submission Rate 30 / 455 (6.59%)
Success Rate 13 / 30 (43.33%)
High Score thocev5 for 683.71 points (21 mins 32 secs)
Average Score 501.34 (for 13 correct submissions)

This problem was simply a case of scanning over the supplied map and returning the highest point that we could reach. We can work out easily if we can reach a point on the walk, by checking if sum of minimum time to reach that point from the hotel and the minimum time to get back to the hotel is less than or equal to the amount of time we have for the walk. These minimum times can be calculated for all points using Dijkstra's algorithm.

Note that both the shortest path out and the shortest path back from all points can both be calculate using (0, 0) as the source: to get the return time, just swap the edge direction.

int di[] = {-1,0,1,0};
int dj[] = {0,-1,0,1};

// Utility class to use with our priority queue
struct state{
  int i,j,T;
  state(int i, int j, int T) : i(i), j(j), T(T) {};
  bool operator<(const state &other) const {
    return T > other.T; // Note the reversal, to get the smallest element

class HillWalker{
  int highestPoint(vector <string> landscape,int threshold,int timeToDark){

    int N = landscape.size(), M = landscape[0].size();
    vector <vector <int> > ht(N, vector <int> (M) );

    // First parse the map to a more useful format
    for ( int i=0 ; i<N ; i++ )
      for ( int j=0 ; j<M ; j++ )
        if (landscape[i][j] < 'a')
          ht[i][j] = landscape[i][j] - 'A';
          ht[i][j] = landscape[i][j] - 'a' + 26;

    // out and back will store the shortest paths;
    vector <vector <int> > out(N, vector <int> (M,-1) );
    vector <vector <int> > back(N, vector <int> (M,-1) );

    priority_queue <state> Q;

    // Do Dijkstra for the way out
    Q.push( state(0,0,0) );
    while ( !Q.empty() ){
      int i =;
      int j =;
      int T =;
      if (out[i][j]!=-1)
      out[i][j] = T;
      for ( int k=0 ; k<4 ; k++ ){
        int ni = i + di[k], nj = j + dj[k];
        if ( ni<0 || nj<0 || ni>=N || nj>=M )
        if ( abs(ht[ni][nj] - ht[i][j]) <= threshold )
          Q.push( state(ni, nj, T + time(ht[i][j], ht[ni][nj]) ) );
    // Now do Dijkstra for the way back
    Q.push( state(0,0,0) );
    while ( !Q.empty() ){
      int i =;
      int j =;
      int T =;
      if (back[i][j]!=-1)
      back[i][j] = T;
      for ( int k=0 ; k<4 ; k++ ){
        int ni = i + di[k], nj = j + dj[k];
        if ( ni<0 || nj<0 || ni>=N || nj>=M )
        if ( abs(ht[ni][nj] - ht[i][j]) <= threshold )
          Q.push( state(ni, nj, T + time(ht[ni][nj], ht[i][j]) ) );

    // Now find the highest reachable point
    int best = 0;
    for ( int i=0 ; i<N ; i++)
      for ( int j=0 ; j<M ; j++)
        if ( out[i][j]>-1 && back[i][j]>-1 && out[i][j]+back[i][j]<=timeToDark )
          best = max( best, ht[i][j] );

    return best; 

  int time(int from,int to){
    if (to <= from) return 1;
    return (to - from) * (to - from);

FloorBoards rate it discuss it
Used as: Division One - Level Two:
Value 500
Submission Rate 244 / 469 (52.03%)
Success Rate 117 / 244 (47.95%)
High Score vlad89 for 462.92 points (8 mins 10 secs)
Average Score 299.28 (for 117 correct submissions)

Experienced TopCoders will have seen the small constraints for this problem and immediately have started thinking of solutions that are exponential in one of the dimensions. This is indeed the way to proceed. Split the layout in two with a horizontal line, and consider the case where the upper part above has been completed and we need to work out how to complete the lower part to minimize the number of boards. This number of new boards in the lower part is of course the number of new boards considering it in isolation minus the number of those boards that are continuations of boards from the upper part. However, the number of boards that continuous between the two sections only depends on the state of the bottom row of the upper part. We can therefore construct a dynamic programming solution, memoizing on how much of the board we've already completed and the state of the bottom row.

There are several ways that coders could approach dividing the board. Coders could either step square by square in row-major order or step row by row. A recursive C++ solution considering the squares in row-major order is given below. The state is given by the i and j indices of the next square we're considering and a bitmask giving the state of the bottom row (bit k is set if the bottom square in column k is a vertical board and not set otherwise).

int mem[1 << 12][12][12];

class FloorBoards{
  int layout(vector <string> room){
    int ret = rec(0, 0, 0, room, room.size(), room[0].size());
    return ret;
  int rec(int i, int j, int bm, const vector <string> &r, int N, int M){
    if ( i==N ) return 0;
    if (mem[bm][j][i] > -1) return mem[bm][j][i];

    // If the current square is blocked, just keep recursing
    if (r[i][j] == '#') return rec( i+(j+1)/M, (j+1)%M, bm&~(1<<j), r, N, M );

    // Try adding a vertical board in the current square
    int vertical = rec( i+(j+1)/M, (j+1)%M, bm | (1<<j), r, N, M );
    // If the square above is not also vertical, this is a new board
    if ( (bm & 1<<j) == 0 )
    // Try adding a horizontal board
    int horizontal = rec( i+(j+1)/M, (j+1)%M, bm&~(1<<j),  r, N, M );
    // If the previous square is not also horizontal, this is a new board
    if ( j==0 || r[i][j-1]=='#' || (bm & 1<<(j-1))!=0 )
    return mem[bm][j][i] = min(vertical, horizontal);        

PyramidPuzzle rate it discuss it
Used as: Division One - Level Three:
Value 1000
Submission Rate 2 / 469 (0.43%)
Success Rate 1 / 2 (50.00%)
High Score Petr for 464.35 points (42 mins 49 secs)
Average Score 464.35 (for 1 correct submission)

A last-minute testing issue with the original division 1 hard problem lead to this backup problem from misof being used instead. While it is conceptually not too hard to see the solution here, the implementation is tricky to say the least and the problem elicited just two solutions with only a single one surviving the contest.

The overall effect of the set of tranformations that Juliet applies to the puzzle is to leave all the triangles in some permutation of their original positions. The question then asks what is the minimum number of times this set of transformations would have to be applied to return the shape to its original state. This is the same as asking for the minumum number of times we have to apply the permutation to itself before we reach the identity transformation.

This has been the theme of previous TopCoder problems such as NumPermutationOrders from TCO06 Round 1. The answer is in the cycle structure of the permutation and is given by the least common multiple of the cycle lengths. So, all we have to do is to work through the transformations to determine the permutation, find all its cycles, then determine their LCM modulo 987654319. It sounds easy, but actually calculating the transformations is almost impossibly fiddly.

The trick here is to work out a good order to store all the triangle positions and build of the transformations from simpler ones, such as swapping and rotating individual faces. For an example written during the competition, see Petr's code.

Calculating the LCM of the cycle lengths mod 987654319 is easiest done by factorizing all the cycle lengths. A minimal set of factors that contains all the cycle length factorizations as subsets can then be determined greedily and these factors can be multiplied mod 987654319. It turns out that this is actually unnecessary, as the numbers don't tend to grow very large anyway and none of the system tests actually cause the modulus to come into play.

By StevieT
TopCoder Member