Match Editorials

Match summary

This time around, the contestants faced a 1000 point problem that required both some thinking and a clever implementation. This combination turned out to be deadly, as only four contestants submitted anything, and even those submissions failed. Successful challenges were scarce, thus what decided the match were the scores on the medium problem.

Kankuro, with the fastest time on the medium, won the round, closely followed by Hornax and victorj.

The Problems

Value	250
Submission Rate	78 / 81 (96.30%)
Success Rate	77 / 78 (98.72%)
High Score	wcao for 248.35 points (2 mins 19 secs)
Average Score	212.14 (for 77 correct submissions)

Imagine that we are solving the task manually. We have the old deck of cards in front of us, and a set of instructions how to insert them into the new deck.

Instead of keeping the new deck of cards as a stack, we can arrange them into a row, with the top card on the left and the bottom one on the right. Now, whenever inserting a new card, we count from the left until we find the right place where it should be inserted, place the new card there, and shift the remaining cards one position to the right.

This exact approach is easily implemented using a simple array. Note that the resulting algorithm is very similar to the simple sorting algorithm InsertSort. Java code follows.

  public String rearrange(String deck, int[] above) {
    int N = above.length;
    char[] newDeck = new char[N];
    for (int i=0; i<N; i++) {
      for (int j=i; j>above[i]; j--) newDeck[j]=newDeck[j-1];
      newDeck[above[i]]=deck.charAt(i);
    }
    String result = "";
    for (int i=0; i<N; i++) result += newDeck[i];
    return result;
  }

Exercise: Did you find this task too easy? Then find and implement a solution that is faster than quadratic in the number of cards.

Value	500
Submission Rate	57 / 81 (70.37%)
Success Rate	50 / 57 (87.72%)
High Score	Kankuro for 481.32 points (5 mins 38 secs)
Average Score	319.56 (for 50 correct submissions)

As the class name suggests, simulation was enough to solve this task.

Approach 1: Heavy artillery. Use a map to assign turn numbers to visited states. Whenever a state appears for the second time, thanks to the map we will find this out. The difference in turn numbers of both occurrences is the length of the period.

  vector<int> step(vector<int> prev) {
    vector<int> next(1, prev.size() );
    for (int i=0; i<int(prev.size()); i++) if (prev[i]>1) next.push_back( prev[i]-1 );
    sort( next.begin(), next.end() );
    return next;
  }

  int periodLength(vector <int> heaps) {
    map< vector<int>, int> visited;
    sort( heaps.begin(), heaps.end() );
    int time = 0;
    visited[ heaps ] = time++;
    while (1) {
      heaps = step( heaps );
      if (visited.count( heaps )) return time - visited[ heaps ];
      visited[ heaps ] = time++;
    }
  }

Approach 2: Use Floyd's cycle finding algorithm.

  public int periodLength(int[] heaps) {
    ArrayList<Integer> slow = new ArrayList<Integer>();
    for (int i=0; i<heaps.length; i++) slow.add(heaps[i]);
    Collections.sort(slow);
    ArrayList<Integer> fast = slow;

    while (true) {
      slow = step(slow);
      fast = step(fast);
      fast = step(fast);
      if (slow.equals(fast)) {
        int period = 0;
        while (true) {
          slow = step(slow);
          period++;
          if (slow.equals(fast)) return period;
        }
      }
    }
  }

Approach 3: Just store all visited states in an array, and for each new state traverse the entire array and check whether it already occured. Thanks to how this game works, even such solutions would pass with plenty of time left.

To see that the first two approaches work in time, it is enough to note that the states of the game are simply integer partitions of the number of cards, which is at most 50. The number 50 has only 204,226 different partitions, so this is an upper bound on the number of states we have to visit until one repeats.

The fact that the third solution works in time is related to how the game behaves – it tends to reach a roughly "triangular" state (such as "1,2,3,4") quickly. The game is called Bulgarian solitaire. Follow the link for an overview of research related to this game.

Exercise: Find the absolutely worst test case, i. e., one that forces Approach 1 to visit as many states as possible. How would you make sure your case really is the worst one? (Hint: Find a way how to compute pre-period and period lengths for all states at the same time.)

Value	1000
Submission Rate	4 / 81 (4.94%)
Success Rate	0 / 4 (0.00%)
High Score	No correct submissions
Average Score	No correct submissions

This task turned out to be too difficult for everyone participating in this match, but some of the submissions were very close to passing. The problem might seem intimidating at the first glance, but if we find the right approach, it can be implemented in under 50 lines of code.

Observation 1: Whenever we decide to place a strip horizontally, we need to place other four strips horizontally as well, to get a 5 by 5 square. (There is no other way how to create a rectangle.)

Observation 2: There are just a few patterns how the strips can be arranged. For N=3 there is just one (all vertically), for N=7 there are four patterns, for N=11 there are 11 and for N=15 there are 34 patterns (one with 15 vertical strips, one with 15 horizontal, eleven with 5 horizontal, and twenty-one with 10 horizontal strips).

While there are just a few patterns, there are lots and lots of ways how to assign the individual strips to their places in the pattern. Trying all of them is not doable within the time limit. Luckily, we don't have to.

We can approach the problem from the other side: Given a bitmap, can it be assembled from the strips we have?

For the largest possible input, there are 9000 bitmaps to check (corresponding to numbers 1000 to 9999). Each time we can process all valid patterns, cut the bitmap into strips, and then compare the obtained set of strips with the one given in the input.

In the solution below, we encode each strip to an integer in the range 0 to 31, to avoid unnecessary manipulations with strings. The function check() cuts the current bitmap into pieces, so that the horizontal rows of strips start in columns a, b, and c, and then checks whether the obtained set of pieces is good.

  static String[] digitBitmaps = {
    "XXX..XXXXXXXX.XXXXXXXXXXXXXXXX",
    "X.X..X..X..XX.XX..X....XX.XX.X",
    "X.X..XXXXXXXXXXXXXXXX..XXXXXXX",
    "X.X..XX....X..X..XX.X..XX.X..X",
    "XXX..XXXXXXX..XXXXXXX..XXXXXXX"
  };

  int N, D;
  int[] pcs;
  int[][] bitmap;

  void makeBitmap(int num) {
    bitmap = new int[N][5];
    for (int i=0; i<N; i++) Arrays.fill(bitmap[i],0);
    int[] digits = new int[D]; for (int i=0; i<D; i++) { digits[D-1-i]=num%10; num/=10; }
    for (int i=0; i<D; i++) for (int j=0; j<5; j++) for (int k=0; k<3; k++) 
      bitmap[4*i+k][j] = digitBitmaps[j].charAt(3*digits[i]+k)=='X' ? 1 : 0;
  }

  int getPiece(int x0, int y0, int dx, int dy) {
    int a=0; for (int i=0; i<5; i++) { a*=2; a+=bitmap[x0+i*dx][y0+i*dy]; }
    int b=0; for (int i=4; i>=0; i--) { b*=2; b+=bitmap[x0+i*dx][y0+i*dy]; }
    return Math.min(a,b);
  }

  int toNumber(String S) {
    int a=0; for (int i=0; i<5; i++) { a*=2; if (S.charAt(i)=='X') a++; }
    int b=0; for (int i=4; i>=0; i--) { b*=2; if (S.charAt(i)=='X') b++; }
    return Math.min(a,b);
  }

  boolean check(int a, int b, int c) {
     boolean[] taken = new boolean[N]; Arrays.fill(taken,false);
     int[] required = new int[N];
     int x = 0;
     if (a+5<=N) for (int i=0; i<5; i++) { taken[a+i]=true; required[x++]=getPiece(a,i,1,0); }
     if (b+5<=N) for (int i=0; i<5; i++) { taken[b+i]=true; required[x++]=getPiece(b,i,1,0); }
     if (c+5<=N) for (int i=0; i<5; i++) { taken[c+i]=true; required[x++]=getPiece(c,i,1,0); }
     for (int i=0; i<N; i++) if (!taken[i]) required[x++]=getPiece(i,0,0,1);
     Arrays.sort(required);
     for (int i=0; i<N; i++) if (pcs[i]!=required[i]) return false;
     return true;
  }

  public int largestNumber(String[] pieces) {
    N = pieces.length; D = (N+1)/4;
    pcs = new int[N]; for (int i=0; i<N; i++) pcs[i]=toNumber(pieces[i]); Arrays.sort(pcs);

    int lo, hi=1;
    for (int i=0; i<D; i++) hi*=10; lo=hi/10; hi--; if (D==1) lo--;
    for (int num=hi; num>=lo; num--) {
      makeBitmap(num);
      if (check(N,N,N)) return num;
      if (D>=2) for (int a=0; a+5<=N; a++) if (check(a,N,N)) return num;
      if (D>=3) for (int a=0; a+5<=N; a++) for (int b=a+5; b+5<=N; b++) if (check(a,b,N)) return num;
      if (D==4) if (check(0,5,10)) return num;
    }
    return -1;
  }

Exercise: By hand, construct a valid input for which we can assemble at least 16 different bitmaps. Once you implemented the solution, find out the input for which this count is maximized.