Match Editorial

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

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{
public:
  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;
  }
};

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)

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).

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

class Planks{
public:
  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;
  }
};

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{
public:
  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';
        else
          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 = Q.top().i;
      int j = Q.top().j;
      int T = Q.top().T;
      Q.pop();
      if (out[i][j]!=-1)
        continue;
      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 )
          continue;
        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 = Q.top().i;
      int j = Q.top().j;
      int T = Q.top().T;
      Q.pop();
      if (back[i][j]!=-1)
        continue;
      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 )
          continue;
        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);
  }
};

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{
public:
  int layout(vector <string> room){
    memset(mem,-1,sizeof(mem));
    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 )
      vertical++;
    
    // 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 )
      horizontal++;
      
    return mem[bm][j][i] = min(vertical, horizontal);        
  }
};

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.