SRM 457

Match Summary

Round Overview
Discuss this match

In the first SRM of the year coders faced a harder than usual problemset. In division 1, the results after the coding phase were short lived and Petr and ACRush found themselves to be in the same room. ACRush managed to challenge Petr’s 1000-pointer but Petr took no time to return the favor by succesfully challenging ACRush’s solution for the 250 points problem. Meanwhile, reiten appeared to consolidate in the first place. However, when the system tests results came every remaining submission to the hard problem was taken down giving Petr the victory due to six succesful challenges and good performance in both the easy and medium problems. ainu7 was able to get a close second place due to an outstanding total of 375 points gained during the challenge phase.

In division 2, coders phased a slightly more complicated than usual easy problem and a very tricky medium problem with less than 70 coders managing to solve more than one problem. However, six coders were still able to solve all three problems, KVF and Orfest finished in close first and second places, respectively, thanks to strong performances in the three problems and a successful challenge.

TheSquareDivTwo

Used as: Division Two - Level One:

An important observation to make regarding this problem is that every placement containing the same number of checkers as the input is reachable. This can be shown to be true by asumming two scenarios in case we need to move a checker from a cell to another: (1) There are no other checkers blocking the way or (2) There is one checker blocking the way. (1) can be easily solved by merely moving the checker to the wanted position. A case in which there are many checkers blocking a path can be solved as a combination of multiple (2) cases. As to solve case (2) we can imagine the following placement:

1
2
3
4
CC..
  .C..
  .C..
  .C..

We want to move the checker to the left towards the right side but there are checkers placed at the second column which are blocking the way. The key is that checkers are indistinguishable from each other so we may just move the blocking checker to the desired position and let the original checker in its position:

1
2
3
4
CC..C.C.C..C.C.C
  .C...C...C...C..
  .C.. - > .C.. - > .C.. - > .C..
  .C...C...C...C..

Now that we know that every state with the same number of checkers is reachable. It is now possible to have just about any placement in which the numberC [i] of checkers in each column i matches the originalR [i], since the sum of allC [i] will still be equal to number of checkers in the original board.

We still need to find the lexicographically first among all these placements. A way to understand this requirement is to see that empty spots are best to have in the top right-most cells while it is better to have checkers in the bottom left-most cells. The rule about the number of cells in each column prevents us from having control regarding the horizontal position of a checker, but for each column we have control over the vertical locations of its checkers. Since it is better to have the checkers in the bottom positions we may just place all of a columns n checkers in the bottom n rows. Which leads us to another way to solve the problem: Quickly notice the pattern in which every column has its required checkers in its bottom cells by taking a close look to the example cases. Example pseudo code follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
String[] solve(String[] board) {
  for (i = 0; i < board.length(); i++) {
    R[i] = (number of checkers in row i)
  }
  result = new char[n][n]
  fill(result, '.')
  for (i = 0; i < board.length(); i++) {

    //Place R[i] checkers on the bottom cells of this column:
    currentCell = board.length() - 1
    for (j = 1; j <= R[i]; j++) {
      result[i][currentCell] = 'C'
      currentCell--
    }
  }

  return (result converted to String[]);
}

TheTriangleBothDivs

Used as: Division Two - Level Two:

Used as: Division One - Level One:

When facing this kind of problems it is usually a good idea to avoid corner cases as much as possible by using approaches that require less conditional branching and are more general. This problem was not the exception. Although it was possible to solve the problem by doing some analysis to the input string and trying to generate a result from it by replacing the unknowns with convenient values it required to concentrate on many special cases. One case that was overlooked by many solutions was “00:00 GMT-?” (quotes for clarity), when a solution does not consider that “00:00 GMT-0” is an invalid time for the clock, then it would return “00:00” while the expected result is “01:00”.

Fortunately, it was possible to avoid all the corner cases by taking a brute force approach. There are only 60*24 = 1440 minutes in a day and only 19 time zones supported by the clock. So we may iterate through all the possible times and time zones and then ask if it was possible that the clock would originally have that time before the malfunction that makes some characters unrecognizable. If the time and zones were possible, convert the time to GMT. Then return the lexicographically smaller of all the times that were found to be possible. A pseudo code version of the solution follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
String fix(String time) {
  String result = "99:99"
  for (h = 0; h <= 23; h++) {
    for (m = 0; m <= 59; m++) {
      for (z = -9; z <= 9; z++) {
        String tem = (format(h, m, z) as "HH:MM GMT+z")
        // (or "HH:MM GMT-z" depending of z's sign )

        //Compare if time could have been tem before the malfunction:
        correct = true
        for (i = 0; i < time.length(); i++) {
          if (tem[i] != time[i]) {
            //the characters are different
            if (time[i] != '?') {
              //the characters differ and they are known
              //characters in time, this solution is invalid.
              correct = false
            }
          } else {
            correct = false
          }
        }

        // Get the current hour in GMT by subtracting time zone offset
        // from h:
        gh = h - z

        // Fix the new hour value in case it become negative/ higher than 24
        if (gh < 0) {
          gh += 24;
        } else if (gh >= 24) {
          gh -= 24;
        }
        // (This is also doable by using a modulo operation:
        // gh = (h - z + 24) % 24 )

        tem = (format(gh, m) as "HH:mm")
        if (correct) {
          result = pick lexicographically first(tem, result)
        }
      }

    }
  }
}

TheHexagonsDivTwo

Used as: Division Two - Level Three:

First we need to ellaborate on handling the rotation condition, since it can complicate our calculations if we consider it while doing the search. Imagine we have the total number of possible solutions without considering the rotation requirement, since each number on the hexagons has to be different and there are six hexagons in the part that can be rotated we would simply have to divide the result by 6.

A simple brute force algorithm in which we pick a different number from 1 to n for each hexagon will time out. In the worst case, we would need about 300⁷ steps, this can be cut by using backtracking, but it is likely still too high.

For this problem, it is useful to understand that the modulo operation partitions the set of integer numbers. For a given k, the result of x%k will yield a integer equal to 0, 1, 2, … or k-1. Since k is at most 9 we can do a brute force search for the results of x%k where x is a number on each hexagon instead of doing the search for the numbers themselves. Once a valid distribution of modulos on the hexagons is found we can use some combinatory to get the number of ways an assignment of numbers from 1 to n can yield those modulos on the hexagons. The number of intgers that yield a certain value m mod k can be computed by dividing n by k and then considering the n%k and that we are considering numbers starting with 1 to determine whether this number has to be increased or not:

1
2
3
4
5
6
7
8
9
static long countMod(long n, long k, long m) {
  //returns the number of times a number between 1 and n
  // equals m mod k.
  long s = n / k;
  if (m > 0 && m <= n % k) {
    return s + 1;
  }
  return s;
}

Once we know how many integers yield a certain result mod k, we can determine the number of placements that match our hexagon of modulos. For each m value that is present in the hexagon, get x=countMod(n,k,m) and then multiply the count by x if m appears on exactly one hexagon or by x*(x-1) if m appears twice or x*(x-1)*(x-2) if m appears thrice.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.util.*;
import java.text.DecimalFormat;
public class TheHexagonsDivTwo {
  long s; //the sum of valid placements
  long n, k;
  long center; //the modulo on the central hexagon.
  int[] external; //the modulos on the other six sorrounding hexagons

  void backtrack(int p) {
    if (p == 6) {
      //found a valid mod k setup.
      long t = countMod(n, k, center);
      for (int i = 0; i < 6; i++) {
        long x = countMod(n, k, external[i]);
        for (int j = 0; j < i; j++) {
          if (external[j] == external[i]) {
            x--;
          }
        }
        t *= Math.max(0, x); //if x reaches a negative number, this
        //modulo distribution is impossible.
      }
      s += t;
    } else {
      // pick a modulo for the p-th hexagon
      for (int i = 0; i < k; i++) {
        external[p] = i;
        // make sure the modulo is not equal to the one on the center
        // or an adjacent one.
        if ((i != center) &&
          ((p == 0) || (i != external[p - 1])) &&
          ((p != 5) || (i != external[0]))
        ) {
          //continue backtracking
          backtrack(p + 1);
        }
      }
    }

  }

  public long count(int n, int k) {
    this.n = n;
    this.k = k;
    s = 0;
    external = new int[6];
    // choose a modulo for the center hexagon
    for (int i = 0; i < k; i++) {
      center = i;
      backtrack(0);
    }
    return s / 6;
  }
}

TheHexagonsDivOne

Used as: Division One - Level Two:

This problem was initially meant as a more general version of TheHexagonsDivTwo, in fact I will do a variable change and instead of considering only n I will convert problem to one similar to TheHexagonsDivTwo in which we have n and k and n is always a multiple of k. Once we solve this more general problem, we can use the solution to solve TheHexagonsDivOne. It may appear that the extra generality can make the problem more complicated, but I think that in this case it allows we to focus on a brute force solution similar to the DivTwo version.

In this situation, k can be very large which prevents us from doing the same approach as with the DivTwo version. But there are still only seven hexagons. This means that there are at most 7 different modulos in a single possible placement. The constraint that n is always a multiple of k yields an interesting result: There are exactly n/k integers that yield any value mod k. This means that modulos are indistinguishable from each other. We can then just generate the possible patterns in which we consider each hexagon’s value to specify a modulo id. Each hexagon can either reuse a previous id or introduce a new one. We also keep a count for the times each id was used and also the number of ids that were used.

Determining the count of placements that match one of our patterns is easy: For each id used we can use one of k different values. Then we need to pick a value for each of the hexagons. Since the number of possible values for any modulo is n/k we have n/k different integers to pick values from:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
long s;
long n, k;
long center;
int[] count; //the number of times each modulo was used in the hexagon
int[] external;

void backtrack(int p, int usedMods) {
  //usedMods is the number of different modulos in use.
  if (p == 6) {
    //A pattern has been found:

    long t = 1;
    for (int i = 0; i < usedMods; i++) {
      t *= Math.max(0, k - i); //assign one of the k 
      // possible values to this id

      for (int j = 0; j < count[i]; j++) {
        t *= Math.max(0, n / k - j); //there are n/k possible numbers
        //to assign to each of the
        //hexagons with this id
      }
    }
    s += t;

  } else {
    for (int i = 0; i <= usedMods; i++) {
      external[p] = i;
      count[i]++;
      if ((i != center) &&
        ((p == 0) || (i != external[p - 1])) &&
        ((p != 5) || (i != external[0]))
      ) {
        backtrack(p + 1, Math.max(usedMods, i + 1));
      }
      count[i]--;
    }
  }

}

public long count(int n, int k) {
  if (n % k != 0) {
    System.out.println("oops ");
    return -1;
  }

  this.n = n;
  this.k = k;
  s = 0;
  external = new int[6];
  count = new int[7];
  Arrays.fill(count, 0, 6, 0);
  count[0] = 1;
  count[1] = 1;
  count[2] = 1;
  // The first two external hexagons will always use ids 1 and 2
  external[0] = 1;
  external[1] = 2;
  // the center hexagon will always use id 0:
  center = 0;
  backtrack(2, 3);
  return s / 6;
}

//transform the original problem to the new one:
public long count(int n) {
  return count(n * 2, n);
}

There were many different ways to solve this problem, there is a lengthy discussion in the forums in which other coders explain what they did during the match.

TheSquareDivOne

Used as: Division One - Level Three:

This problem is similar to the division 2 easy with the exception that the constraints are smaller and that it also requires to minimize the number of steps. It requires a similar observation to the one made in the division 2 version. Let us say we have two states:

1
2
3
4
CC...C..
  .C...C..
  .C...C..
  .CC., .CCC

We require to convert the first state into the second one using a minimum number of moves. Once again we can take each checker individually and move it to a destination ignoring the other checkers because they are indistinguishable. I.e: we can decide to move the top-right checker to the bottom left position and just consider this single sequence of steps that requires 6 turns to reach the wanted placement, ignoring the fact that during the movement sequence the checker shared a cell with other checkers because a sequence in which we move each of the checkers by one cell is equivalent in regards to the number of steps required.

It is thanks to that property that we can consider each checker independently. This can be very helpful. Let us continue solving the easier problem of counting the minimum number of steps required to go from one state to another: This is solvable by using a flow network
and a min-cost max-flow algorithm.

Consider a network consisting of all the nn cells as nodes. Note that each checker can be considered a single flow unit. The source begins by sending each “checker” to its initial position this means that there is an edge of capacity 1 connecting the source and these cells. Then the checkers move around the nn cells network. Note that each cell is connected to up to 4 other cells that are adjacent to it. Since we wish to minimize the number of steps, the cost for using one of these edges (a step) has a cost equal to 1. The cells that contain checkers in the output would also be connected to the sink. Note that it is valid to have a single cell being used multiple times by different checkers, so the edges connecting each cell need infinite capacity. What we are minimizing is the number of steps, so any edge that is not connecting two adjacent cells has a cost equal to 0. The maximum flow will be equal to the number of checkers, and the minimum cost for this flow will be the minimum number of steps required to achieve the target placement.

Now that we have solved that easier version of the problem, let us move to consider column and row counts. Instead of a fixed checker placement we actually have a condition that the number of checkers in each column i is equal to R[i] (as calculated for the initial placement). This does not really modify the problem that much. Instead of having edges from known cells to the sink we may now add n more nodes that represent each column. Each cell will have an edge of capacity 1 that connects it to its respective column and each column i will have an edge of capacity R[i] that connects it to the sink. This will enforce the two conditions we need: At the end there must be at most one checker on each cell and there must be exactly R[i] checkers on each column i.

This reduction to a min-cost max-flow problem is actually very simple for a coder with experience in this kind of problem. You may be wondering what has caused the 0% success rate. Well, we need not only get the minimum cost, we actually need the lexicographically first placement that gives a minimum cost. An usual way to do this procedure is to iterate through all the n*n cells in the board then modify the flow network so that a flow from the cell to the sink is forbidden (by removing the edge from this cell to its column) and if the minimum cost is still equal to the original one we can say that it is possible not to have a checker in this cell (lexicographically-first means we are looking forward having a preference for empty cells in the upper-left-most cells of the board). Unfortunately, the constraints are too large for this approach to work under the 2 seconds limit.

There are many ways to overcome this issue one involves knowing the theory behind the min-cost flow algorithm to avoid calling a new instance of the max flow algorithm for each cell, I’ll leave that one as an exercise it is currently the solution Petr has submitted to the practice room. The intended solution did not involve theory but an optimization to the idea of verifying the flow for each of the n*n cells.

A min cost flow algorithm can optimize many different kinds of costs and not just the one that is specified as cost in the problem’s statement. We can take the placement of the checkers itself as a cost in a similar way to Petr’s solution during the match, but the costs must be powers of 2. This is because when you sum 2⁰, 2¹, 2²…, 2^(k-1) the result is guaranteed to be smaller than 2^k. This involves adding a cost to the edge that connects a cell with its column, these costs would be powers of 2. The largest power of 2 ( 2^n*n-1 ) is used for the upper left cell and the smallest power of 2 ( 2⁰ ) is used for the bottom right cell. Since the number of steps is the priority to reduce, we need to change the cost connecting each cell to 2^n*n this ensures that flows that minimize the number of steps are given a priority over the ones that minimize the placement itself. As an example, the costs for a n=4 board would be:

1
2
3
4
5
6
7
8
9
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -
32768 | 16384 | 8192 | 4096
  -- -- -- -- -- -- -- -- -- -- -- -- -- -- -
  2048 | 1024 | 512 | 256
  -- -- -- -- -- -- -- -- -- -- -- -- -- -- -
  128 | 64 | 32 | 16
  -- -- -- -- -- -- -- -- -- -- -- -- -- -- -
  8 | 4 | 2 | 1
  -- -- -- -- -- -- -- -- -- -- -- -- -- -- -

And the penalty for using a step would be: 65536.

The checker positions can be then be acquired by performing bitwise operations on the minimum cost for the new network. This approach still has a problem and it is that for a n=18 board, there are 18*18 cells which would overflow a 64 bits integer. A solution for this issue is to use bignums, this requires you to implement the min-cost max flow algorithm using bignums which may be far-fetched. However a simple solution is to still iterate the cells manually in large groups of 55 (for example) cells, and only consider costs for these 55 cells. Then use the bit operations to determine the existence of checkers in these cells and continue moving to the next 55 cells.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
import java.util.*;
import java.text.DecimalFormat;
public class TheSquareDivOne {
  final long INF = 3000;
  final long CINF = 1 l << 62;

  final int ITERATION_CELLS = 55;
  final int[] dx = new int[] {
    0,
    0,
    1,
    -1
  };
  final int[] dy = new int[] {
    1,
    -1,
    0,
    0
  };
  int x, y;
  long lastCost;

  //In each iteration, pick ITERATION_CELLS cells and minimize the lex
  //representation for those cells:
  void nextIteration(String[] board, int n, boolean[][] res) {
    //res contains the current known values for the cells before (x,y)
    int bx = x, by = y;
    Network g = new Network();
    //The network class is an abstraction for setting up
    // since it is a known algorithm, it is not included in this sample
    // code to save up on text.

    g.source = g.addVertex();
    g.sink = g.addVertex();
    int[] column = new int[n];
    int[][] cell = new int[n][n];

    int[] columnReq = new int[n];

    //Add a vertex for each column, count the checkers in each row:
    for (int i = 0; i < n; i++) {
      column[i] = g.addVertex();
      int r = 0;
      for (int j = 0; j < n; j++) {
        if (board[i].charAt(j) == 'C') {
          r++;
        }
      }
      columnReq[i] = r;
    }

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        //Add a vertex for each cell

        cell[i][j] = g.addVertex();
        if (board[i].charAt(j) == 'C') {
          //add an edge from the source to this cell
          g.addEdge(g.source, cell[i][j], 1, 0);
        }

        if ((i <= y) && ((i < y) || (j < x))) {
          //If in a previous iteration it was determined this cell
          //should be a finish spot, make a direct edge of capacity
          //one from this cell to the sink. Also reduce the column's
          //capacity. 
          if (res[i][j]) {
            g.addEdge(cell[i][j], g.sink, 1, 0);
            columnReq[j]--;
          }
        }
      }
    }

    //add the edges between connecting each adjacent pair of cells.
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        for (int k = 0; k < 4; k++) {
          int nx = i + dx[k], ny = j + dy[k];
          if ((nx >= 0) && (nx < n) && (ny < n) && (ny >= 0)) {
            //note the cost we are using:
            g.addEdge(cell[j][i], cell[ny][nx], INF, 1 l << ITERATION_CELLS);
          }
        }
      }
    }

    //add edges for the cells we are currently minimizing.
    for (int i = ITERATION_CELLS - 1; i >= 0; i--) {
      if (y < n) {
        //cost decreases as we move towards the bottom- left
        g.addEdge(cell[y][x], column[x], 1, 1 l << i);

        x++;
        if (x >= n) {
          x = 0;
          y++;
        }
      }
    }

    //add 0-cost edges from the remaining cells to the columns.
    while (y < n) {
      g.addEdge(cell[y][x], column[x], 1, 0);
      //...
      x++;
      if (x >= n) {
        x = 0;
        y++;
      }
    }

    //add the edges from the columns to the sink.
    for (int i = 0; i < n; i++) {
      g.addEdge(column[i], g.sink, columnReq[i], 0);
    }
    //call minCostMaxFlow algorithm
    g.minCostMaxFlow();

    long cost = g.minCost;

    //the lastCost variable is used mainly for debugging.
    assert((lastCost == -1) || (lastCost == (cost >> ITERATION_CELLS)));
    lastCost = (cost >> ITERATION_CELLS);
    x = bx;
    y = by;

    long mask = cost & ((1 l << ITERATION_CELLS) - 1);

    for (int i = ITERATION_CELLS - 1; i >= 0; i--) {
      if (y < n) {
        res[y][x] = ((mask & (1 l << i)) != 0);

        //...
        x++;
        if (x >= n) {
          x = 0;
          y++;
        }
      }
    }

  }

  public String[] solve(String[] board) {
    int n = board.length;
    boolean[][] res = new boolean[n][n];

    // Do as many iterations as necessary to fill up the cells:
    lastCost = -1;
    x = 0;
    y = 0;
    while (y < n) {
      nextIteration(board, n, res);
    }

    String[] sres = new String[n];
    for (int i = 0; i < n; i++) {
      StringBuffer buf = new StringBuffer();
      for (int j = 0; j < n; j++) {
        if (res[i][j]) {
          buf.append('C');
        } else {
          buf.append('.');
        }
      }
      sres[i] = buf.toString();
    }
    return sres;
  }
}