Match Editorial

Match summary

This Saturday more than 1,500 coders logged into the arena to compete in the first round of this year's TCO. With 900 places for advancers, the strategy to advance was clear: slow and steady. In the end, the number of coders with positive scores was a bit lower than 900, and thus everyone with a positive score advanced to the next round.

Of course, not every participant decided to go for the slow and steady approach. Some of the higher-rated coders went for fast and steady :-)

A bug in the room seeding algorithm forced the admins to prepare a fix during the coding phase, and then fix everything during the intermission. This was kind of like watching a Formula 1 in the pit stop: in a short amount of time, many things had to happen to allow the competition to proceed. Luckily, everything went smoothly, and the only effect the coders could see was that the intermission was 10 minutes longer.

Of course, that was not necessarily a bad thing. While many coders spent part of the time chatting, some were glad to have ten more minutes to prepare challenge cases for greedy solutions of the 250, and incorrect or slow solutions of the 500 and 1000.

The round went to Petr after his spectacular performance in the challenge phase. His 11 correct challenges (and not a single wrong one) gave him an almost 550 point lead before the rest of the coders. Second place went to SkidanovAlex. Looking at his rating graph, soon we'll have a new target. Another TopCoder veteran, tomek, finished third, even with a resubmitted easy problem.

The Problems

Value	250
Submission Rate	1392 / 1507 (92.37%)
Success Rate	586 / 1392 (42.10%)
High Score	gawry for 243.99 points (4 mins 28 secs)
Average Score	183.30 (for 586 correct submissions)

There are up to 2⁵⁰ possible ways to buy the shoes we don't want. In two seconds it is not possible to try all these ways to find the best one. We have to find something that will help us prune the search.

One such observation: Suppose that we have two shoe models that give us the same discount. Clearly, we should prefer the cheaper of these two.

The other observation we need is that the problem statement promised us that there are only three types of discounts.

What can we do now? Take all the models, and split them into three heaps, one for each discount type. Now, within each heap we can order the models according to their price.

What did we gain? Suppose that the optimal solution involves buying A models from the first heap, B models from the second heap, and C models from the thid heap. We now know that those must be the A (or B or C) cheapest models from that heap.

All that remains is to find the right values A, B, and C that give us the best total price. Each of these values is at most 50, and thus we can simply examine all triples (A,B,C) and pick the best one.

C++ code follows.

  double minimumPrice(vector <string> discounts, int price) {
    vector<int> disc[4];
    int N = discounts.size();
    for (int i=0; i<N; i++) {
      int x,y;
      stringstream(discounts[i]) >> x >> y;
      disc[y].push_back(x);
    }
    for (int i=1; i<=3; i++) sort(disc[i].begin(), disc[i].end());
    double res = 1e30;
    for (unsigned a=0; a<=disc[1].size(); a++)
    for (unsigned b=0; b<=disc[2].size(); b++)
    for (unsigned c=0; c<=disc[3].size(); c++) {
      double now = 0.0;
      for (int i=0; i<a; i++) now += disc[1][i];
      for (int i=0; i<b; i++) now += disc[2][i];
      for (int i=0; i<c; i++) now += disc[3][i];
      now += price * pow(0.99,a*1.) * pow(0.98,b*1.) * pow(0.97,c*1.);
      res = min(res,now);
    }
    return res;
  }

Value	500
Submission Rate	796 / 1507 (52.82%)
Success Rate	667 / 796 (83.79%)
High Score	NauCoder for 474.06 points (6 mins 43 secs)
Average Score	313.93 (for 667 correct submissions)

We can easily find out that after each move the game board will have the following shape:

XXXXXXXX
XXXXXXXXXXXXX
XXXXXXXXXXXXXXXX

More precisely, the state of the game can be described by three integers A ≤ B ≤ C, giving the length of the top, middle, and bottom row, respectively.

Note that C≤100, thus there are roughly 10⁶ states. In each state, the number of possible moves is equal to the number of remaining cells. It follows that the number of possible moves is never greater than 300.

(Exact values: There are 176,851 valid positions, and we have to examine a total of 26,527,650 moves.)

This makes it possible to search the entire state space, and for each state (i.e., position of the game) compute which player wins. The algorithm for this is described in rasto6sk's tutorial on games.

This algorithm uses the following idea: A position is winning (for the player to move), if there is a move that leads to a position that is losing (again, for the player to move, which would be our opponent). And vice versa, a position is losing if all moves lead to winning positions.

This algorithm can be easily extended to compute the number of moves: If we are in a winning position, and there are multiple losing positions to choose from, pick the one where the game will be shortest. And if we are in a losing position, do the contrary.

The solution is most easily implemented using recursion with memoization. C++ code follows.

  int memo[105][105][105];

  int solve(int a, int b, int c) {
    // base case: I'm forced to lose
    if (a==1 && b==0 && c==0) return -1;

    // memoization: if I already computed this, return the result
    int &result = memo[a][b][c];
    if (result != 0) return result;

    result = -1; 
    int r[3]; r[0]=a; r[1]=b; r[2]=c;

    // try all possible moves
    for (int row=0; row<3; row++) 
      for (int col=0; col<r[row]; col++) {
        if (row+col==0) continue; // ... except for the move where we lose

        int s[3]; s[0]=a; s[1]=b; s[2]=c;
        for (int i=row; i<3; i++) s[i] = min(s[i], col);
        // now, s[] contains the row lengths after the move 

        int curr = solve(s[0],s[1],s[2]);
        if (curr < 0) {
          if (result<0) 
            result=1-curr; // we found the first winning move
          else 
            result=min(result,1-curr); // check whether this winning move is better
        } else {
          if (result<0) 
            result=min(result,-curr-1); // check whether this losing move is better
        }
      }
    return result;
  }

  int moves(int N) { return solve(N,N,N); }

Value	1000
Submission Rate	125 / 1507 (8.29%)
Success Rate	25 / 125 (20.00%)
High Score	SkidanovAlex for 709.03 points (20 mins 0 secs)
Average Score	527.51 (for 25 correct submissions)

The process described in the problem statement can be visualised as "peeling off" layers from the box. First, we remove the "top" layer, then the "back" layer, then the "left" layer, then the "top" layer again, and so on, until the entire box is removed.

A similar process is used for the 2D case: alternately we remove the "top" and the "left" row of the rectangle. Of course, the 2D rectangles can have different orientations in 3D space, and this is where those phrases like "all cubes with minimal X and Y coordinates" came into play – they simply made sure that for any orientation the process will work in the same way.

Of course, we can't afford to number each and every unit cube in the box, there are too many of them.

Lucky news is that we don't need to do this, and it will even make our solution a bit simpler. Most of the instructions are "take this set of cubes that doesn't contain the one you need, and number it". At this point, the only thing that matters is the volume of that set (i.e., the count of unit cubes it contains). If the last value used before this set was N, and this set contains M cubes, then the last of them will get the number N+M. And we don't really care how the numbers N+1 to N+M are distributed.

This allows us to write a simple function that solves the 3D case: Remove 2D rectangles of cubes and sum their sizes, until we find the layer that contains our cube.

  // c* is in [0,s*)
  long long solve3D(long long sx, long long sy, long long sz, long long cx, long long cy, long long cz) {
    long long result = 0;

    while (true) {
      // remove the top layer
      if (sx==1 || sy==1 || sz==1) break;
      if (cz==0) return result + solve2D(sx,sy,cx,cy);
      result += sx*sy; cz--; sz--;

      // remove the back layer
      if (sx==1 || sy==1 || sz==1) break;
      if (cy==0) return result + solve2D(sx,sz,cx,cz);
      result += sx*sz; cy--; sy--;

      // remove the left layer
      if (sx==1 || sy==1 || sz==1) break;
      if (cx==0) return result + solve2D(sy,sz,cy,cz);
      result += sy*sz; cx--; sx--;
    }

    // if we got here, a single 2D case remains of the entire box
    if (sx==1) return result+solve2D(sy,sz,cy,cz);
    if (sy==1) return result+solve2D(sx,sz,cx,cz);
    if (sz==1) return result+solve2D(sx,sy,cx,cy);
  }

As the volume is at most 10¹⁸, one of the dimensions is at most 10⁶, and thus the while-loop will make at most 10⁶ iterations.

We can make a similar solution for the 2D case. However, there is one small catch: Removing rows one at a time can lead to exceeding the time limit for a (10⁹ x 10⁹ x 1) box.

Luckily, we can easily speed this solution up. If our cube has 0-based coordinates (CX,CY), then we will clearly make free=min(CX,CY) full iterations of the while-loop before hitting our cube. We can easily count all the cubes used in these steps, and only then do the remaining part of the function.

XXXXXXXXXXXXXXX
XXXXXXXXXXXXXXX
XXXXXXXXXXXXXXX
XXX.......?....
XXX............
XXX............
XXX............

The schema above shows a 15x7 rectangle after three iterations. The cells denoted 'X' are those that were numbered already, '?' is our cube, its coordinates are (10,3). The count of 'X'es is (15*3) + (7-3)*3.

The general 2D solution will look as follows:

  // c* is in [0,s*)
  long long solve2D(long long sx, long long sy, long long cx, long long cy) {
    long long result = 0;
    long long free = min(cx,cy);
    result += free*(sx+sy-free);
    cx-=free; cy-=free;
    sx-=free; sy-=free;

    while (true) {
      if (sx==1 || sy==1) break;
      if (cy==0) return result+cx+1;
      result+=sx; cy--; sy--;
      if (cx==0) return result+cy+1;
      result+=sy; cx--; sx--;
    }
    if (sx==1) return result+cy+1; else return result+cx+1;
  }

And our work is done. All that remains is to count the number of dimensions of the given box, and then to call the appropriate function:

  long long getNumber(int sx, int sy, int sz, int cx, int cy, int cz) {
    cx--; cy--; cz--;

    if (sx==1 && sy==1) return cz+1;
    if (sx==1 && sz==1) return cy+1;
    if (sy==1 && sz==1) return cx+1;

    if (sx==1) return solve2D(sy,sz,cy,cz);
    if (sy==1) return solve2D(sx,sz,cx,cz);
    if (sz==1) return solve2D(sx,sy,cx,cy);

    return solve3D(sx,sy,sz,cx,cy,cz);
  }