Match Editorial

Match summary

This match featured another conceptual problem set from Vasyl[alphacom]. If in the previous his SRM 403 all problems were about numbers composed of digits 4 and 7, in this SRM all problems were about checkers on rectangular board. Somewhat unexpectedly, the match turned out to be very tough. In Division 1 only 17 coders solved the Medium and only 4 coders solved the Hard. Nobody was able to finish both these problems correctly. nika won his first SRM with correct solutions on first two problems and 275 challenge points. lukasP had the fastest Hard, but got only the second place because of skipped Medium. Petr rounded the Top-3. Egor, the author of the fastest Medium, took the fourth place.

In Division 2 nobody was able to solve the Hard problem and only 16 coders succeded in solving the Medium. The fastest among them was Secluder, however he didn't get anything during the Challenge phase and took only the second place. The first place was taken by Jasoni86 with 200 challenge points. TT87 with 150 challenge points got the bronze.

The Problems

Value	250
Submission Rate	515 / 555 (92.79%)
Success Rate	469 / 515 (91.07%)
High Score	kemo for 248.46 points (2 mins 14 secs)
Average Score	208.18 (for 469 correct submissions)

This problem is really straightforward. We need to consider each checker separately and choose the closest corner to it. This is done by calculating the distance from the checker to each of 4 corners and choosing the minimum. The distance between cells (x, y) and (x', y') is equal to |x - x'| + |y - y'|.

public class TheSimpleGame {
  public int count(int n, int[] x, int[] y) {
    int res = 0;
    int[] cx = new int[] {1, 1, n, n};
    int[] cy = new int[] {1, n, 1, n};
    for (int i=0; i < x.length; i++) {
      int dst = 10000;
      for (int j=0; j < 4; j++)
        dst = Math.min(dst, Math.abs(x[i] - cx[j]) + Math.abs(y[i] - cy[j]));
      res += dst;
    }
    return res;
  }
}

Value	600
Submission Rate	167 / 555 (30.09%)
Success Rate	16 / 167 (9.58%)
High Score	Secluder for 512.48 points (12 mins 10 secs)
Average Score	346.75 (for 16 correct submissions)

Value	300
Submission Rate	326 / 435 (74.94%)
Success Rate	200 / 326 (61.35%)
High Score	Petr for 295.59 points (3 mins 28 secs)
Average Score	228.88 (for 200 correct submissions)

Let's fix some K and try to find the best way to gather some K checkers in the same cell. To do this, we first consider a very slow approach: iterate through all possible subsets of K checkers and for each subset find the best way to gather all checkers from it in the same cell. The following question immediately arises: how to solve the problem for a fixed subset of K checkers? If we have K checkers located at (x[1], y[1]), ..., (x[k], y[k]) and wish to move them into the cell (x, y), the number of required moves will be (|x - x[1]| + ... + |x - x[k]|) + (|y - y[1]| + ... + |y - y[k]|) = (|x - x[1]| + ... + |x - x[k]|) + (|y - y[1]| + ... + |y - y[k]|). The sum is broken into two separate sums, where the first one is dependent only on x and the second one is dependent only on y. It means we can choose x and y independently.

Let's show that the best x is one of x[i] (in fact, the best x is the median of all x[i], but we don't need this fact to solve the problem). Sort x[i] in non-descending order: x[1] ≤ ... ≤ x[k]. Suppose that the best x is not one of x[i] and is located between points x[j] and x[j+1]: x[j] < x < x[j+1]. We have j points to the left of x and k - j points to the right. If j < k - j, then changing x to x + 1 will increase the distance to the left points by j and decrease the distance to the right points by k - j. In total the distance will decrease by k - 2*j > 0. Similarly, if j > k - j, then changing x to x - 1 will decrease the total distance by 2*j - k > 0. So the only case when x can be optimal, is when j = k - j. But in this case the distance is the same on the whole segment [x[j], x[j+1]], so x = x[j] or x = x[j+1] also produce the best total distance.

So what we have is that the best meeting point for any subset of checkers is of form (x[i], y[j]), where both x[i] and y[j] are some input coordinates. At the first glance, it doesn't help much because we can't iterate through all subsets of checkers (it can be as much as 2^50 subsets). But the correct idea is near: we can iterate through all possible meeting points (it can be at most 2500 such points)! For each meeting point we will then need to answer the question: which subset of K checker is best gathered at this meeting point? And the answer is simple: this is the subset containing K closest checkers to this meeting point. So finally our solution in pseudocode looks as follows:

Fill result array by sufficiently large numbers
Iterate through all x[i]
  Iterate through all y[j]
    Iterate through all K
      Choose a subset containing K closest checkers to the cell (x[i], y[j])
      Calculate the cost of gathering these checkers in (x[i], y[j])
      Set result[K] := min(result[K], cost)

Java implementation of this approach follows.

import java.util.*;
public class TheTower {
  public int[] count(int[] x, int[] y) {
    int N = x.length;
    int[] res = new int[N];
    Arrays.fill(res, 1000000000);
    int[] dst = new int[N];
    for (int i=0; i<N; i++)
      for (int j=0; j<N; j++) {
        // calculate distance from (x[i], y[j]) to all checkers
        for (int k=0; k<N; k++)
          dst[k] = Math.abs(x[i] - x[k]) + Math.abs(y[j] - y[k]);

        // sort distances
        Arrays.sort(dst);

        // for each K choose the subset of K closest checkers
        int sum = 0;
        for (int k=0; k<N; k++) {
          sum += dst[k];
          res[k] = Math.min(res[k], sum);
        }
      }
    return res;
  }
}

Value	1000
Submission Rate	28 / 555 (5.05%)
Success Rate	0 / 28 (0.00%)
High Score	null for null points (NONE)
Average Score	No correct submissions

Value	500
Submission Rate	120 / 435 (27.59%)
Success Rate	17 / 120 (14.17%)
High Score	Egor for 336.07 points (22 mins 16 secs)
Average Score	239.54 (for 17 correct submissions)

Despite very low success rate, this problem is nothing more than standard combinatorial game problem. Though there are two things that make this problem harder:

1. Usually you are only asked for a winner, but here you should additionally return the number of moves before the game finishes.
2. Combinatorial games are usually acyclic, i.e. it's impossible to repeat the same position two or more times in the games. In this game it's possible.

Let's describe a general way of solving such problems. First, we need to identify the set of states (positions) that can occur during the game. Here the state of the game is vector (white piece position, black piece position, player to do the next move).

For each state we need to find the outcome of the game (WIN if the player to do the next move will win, LOSE if this player will lose, DRAW if the game will last infinitely without either player winning). Note that for this game DRAW is impossible, but there are games where some states lead to DRAW. For each state where the outcome is not DRAW we additionally need to calculate the number of moves the game will last.

There are two possible approaches to do this calculations. The first one is iterative and the second one is a variation of breadth first search. The first approach works slower, but for this problem both algorithms are fine. The proof of algorithms' correctness is left to the reader, but it's worth noting that both are based on the following simple recursive definitions:

• the position's outcome is WIN if there's a move from it that leads to a position with outcome LOSE;
• the position's outcome is LOSE if all moves from it lead to positions with outcome WIN;
• outcome for all other positions is DRAW.

The pseudocode for iterative algorithm is given below (it uses two array - OUTCOME[state] is game's outcome and MOVES[state] is the number of moves before the game's end):

Set OUTCOME for all states as UNKNOWN

Set OUTCOME to WIN and MOVES to 1 for all states
    where it's possible to win in 1 move

Do the following iteration until there are updates in OUTCOME:
  Iterate through all states
    If from some state A there's a move to a state B where OUTCOME[B] = LOSE:
      Set OUTCOME[A] to WIN
      Set MOVES[A] to min{MOVES[B]+1} by all B such that
        a) there's a move from A to B
        b) OUTCOME[B] = LOSE
    If all moves from some state A lead to states B where OUTCOME[B] = WIN:
      Set OUTCOME[A] to LOSE
      Set MOVES[A] to max{MOVES[B]+1) by all B such that
        there's a move from A to B

For all states where OUTCOME is UNKOWN, set OUTCOME to DRAW

Check misof's code for an implementation of similar approach.

The complexity of the previous approach can be estimated as O(MAX_MOVES_BEFORE_GAME_FINISH * STATES_NUMBER * MAX_MOVES_FROM_A_SINGLE_STATE). Another approach uses a queue which contains all positions for which outcome is known. Each state is thus visited at most one time and the complexity of the algorithm is O(STATES_NUMBER * MAX_MOVES_FROM_A_SINGLE_STATE). The approach is very similar to breadth first search, of course with some modifications. The pseudocode for it is shown below (it additionally uses one more array NEED; it contains the number of moves to winning positions from a state we still need to find in order to confirm that the outcome for this state is LOSE):

Set OUTCOME for all states as UNKNOWN
Set NEED for all states as the number of possible from from the state

For all states where it's possible to win in 1 move
  Set OUTCOME to WIN
  Set MOVES to 1
  Put this state into the queue

While the queue is not empty
  Get the state A from the queue
  For all states B such that there's a move from B to A
    If OUTCOME[A] is WIN
      Decrease NEED[B] by 1
    If (OUTCOME[A] is LOSE) or (OUTCOME[A] is WIN and NEED[B] is 0)
      Set OUTCOME[B] to (not OUTCOME[A])
      Set MOVES[B] to MOVES[A]+1
      Add B to the queue

For all states where OUTCOME is UNKNOWN, set OUTCOME to DRAW

For a challenge submission using this approach take a look at Petr's solution.

You can also find this and this threads about this problem helpful.

Excercise. Initially this problem allowed n up to 50. How to solve the problem under such constraints? Note that even the second described approach will be too slow.

Value	1000
Submission Rate	27 / 435 (6.21%)
Success Rate	4 / 27 (14.81%)
High Score	lukasP for 463.64 points (42 mins 56 secs)
Average Score	372.19 (for 4 correct submissions)

Main difficulty in this problem comes from the necessity to count different checkers placements as equal if they become the same after one or several board rotations. Note that each placement becomes the same after 4 board rotations, however some placements repeat themselves after 2 or even 1 board rotations. Let's denote the number of placements that require at least 4 rotations to repeat themselves as C4, that require at least 2 rotations - as C2 and that require just 1 rotation - as C1.

It's not hard to see that all C4 placements are broken into groups of four, where all placements within a group are the same, all C2 placements are broken into the pairs of the same placements, and all C1 placements are distinct. Therefore, the total number of distinct placements is C4/4 + C2/2 + C1.

Now, let's denote the number of placements that become the same after 4 rotations (this includes those placements that become the same after 2 or 1 rotations) as T4, that become the same after 2 rotations (including those that become the same after 1 rotation) as T2, and that become the same after 1 rotation as T1. T and C values are connected as follows:

T4 = C4 + C2 + C1
T2 = C2 + C1
T1 = C1

<=>

C1 = T1
C2 = T2 - T1
C4 = T4 - T2

So, it's enough for us to calculate T1, T2 and T4. First let's calculate T4, i.e. the number of all possible placements. Denote the number of checkers we have of each color as ch[0], ..., ch[k-1]. If n^2 < ch[0] + ... + ch[k-1], then there's no possible placements and we can return 0. Otherwise, there are C(n^2, ch[0]) ways to put checkers of color 0, C(n^2 - ch[0], ch[1]) ways to put checkers of color 1 on the remaining positions, and so on. Here C(N, M) is the number of ways to choose M positions from N, i.e. N! / (M! * (N-M)!). We get the following formula for T4:

T4 = C(n^2, ch(0)) * C(n^2-ch[0], ch[1]) * ... * C(n^2-ch[0]-...-ch[k-2], ch[k-1]) =

  n^2 * (n^2 - 1) * ... * (n^2 - ch[0] - ... - ch[k-1] + 1)
= ---------------------------------------------------------
             ch[0]! * ch[1]! * ... * ch[k-1]!

We will need to do similar calculations several more times, so let's denote the number of ways to put objects of k colors where there are ch[i] object of color i onto N positions as choose(N, ch[0], ..., ch[k-1]). So T4 = choose(n^2, ch[0], ..., ch[k-1]).

Now let's calculate T2. To do this, note that all cells of the board are broken into pairs of cells that come into each other after 2 rotations. The only exception is the case when n is odd, in this case the central cell always remains the same after rotation and the other cells are still broken into pairs. In order for a placement to repeat itself after two rotations, we need to ensure for each pair that either both cells in it contain checkers of the same color or both cells in it are empty. We have 2 possible cases here:

1. n is even. If at least one of ch[i] is odd, then T2 = 0 (we can't distribute odd number of checkers into pairs). Otherwise we need to distribute checkers into n^2/2 pairs, so T2 = choose(n^2/2, ch[0]/2, ..., ch[k-1]/2).
2. n is odd. Here we have (n^2-1)/2 pairs and one central cell. If none of ch[i] is odd, then we just distribute all checkers into pairs and leave the central cell empty: T2 = choose((n^2-1)/2, ch[0]/2, ..., ch[k-1]/2). If only one ch[i] is odd, we put one checker of color i into the central cell and distribute all other cells into pairs: T2 = choose((n^2-1)/2, ch[0]/2, ..., (ch[i]-1)/2, ..., ch[k-1]/2). Finally, if two or more ch[i] are odd, then T2 = 0.

Calculation of T1 is similar. All cells are broken into groups of four (except central cell for odd n) and all cells within a group must be either empty or filled by checkers of the same color. This gives the following cases:

1. n is even. If at least one of ch[i] is not divisible by 4, then T4 = 0, otherwise T1 = choose(n^2/4, ch[0]/4, ..., ch[k-1]/4).
2. n is odd. At most one ch[i] can be not divisible by 4 and it should give 1 in remainder, otherwise T4 is 0. If all ch[i] are divisible by 4, then T1 = choose((n^2-1)/4, ch[0]/4, ..., ch[k-1]/4). If only one ch[i] gives 1 in remainder, then T1 = choose((n^2-1)/4, ch[0]/4, ..., (ch[i]-1)/4, ..., ch[k-1]/4).

One final note is that for calculation of choose it's useful to precalculate inversions of all factorials upto 100,000!. To calculate inversion of an integer X it's helpful to apply Small Fermat Theorem: inv(X) = X^1234567889 MOD 1234567891 (note that 1234567891 is a prime number).

Java implementation of this approach follows. In this implementation I tried to treat calculations of T1, T2 and T4 in a similar way.

public class TheBeautifulBoard {
  final long MODULE = 1234567891;
  long[] inv = new long[100001];

  // a^b MOD 1234567891
  long pow(long a, long b) {
    if (b==0) return 1;
    long x = pow(a, b/2);
    x = (x * x) % MODULE;
    if (b % 2 == 1) x = (x * a) % MODULE;
    return x;
  }

  // multiplicative inversion of x
  long calcInv(long x) {
    return pow(x, MODULE-2);
  }

  // calculating choose(all, cnt[0], ..., cnt[k-1])
  long choose(long all, int[] cnt) {
    long res = 1;
    long sum = 0;
    for (int i=0; i < cnt.length; i++)
      sum += cnt[i];
    all %= MODULE;
    for (int i=0; i < sum; i++) {
      res = (res * all) % MODULE;
      all--;
      if (all<0) all += MODULE;
    }
    for (int i=0; i < cnt.length; i++)
      for (int j=1; j <= cnt[i]; j++)
        res = (res * inv[j]) % MODULE;
    return res;
  }

  // calculates T based on a parameter rot
  // rot = 4 gives T1
  // rot = 2 gives T2
  // rot = 1 gives T4
  long calcT(long n, int[] A, int rot) {
    int C1 = 0;
    for (int i=0; i < A.length; i++) {
      if (A[i] % rot > 1) return 0;
      if (A[i] % rot == 1) C1++;
    }
    if (C1 > 1) return 0;
    if (C1 == 1 && n % 2 == 0) return 0;
    for (int i=0; i < A.length; i++)
      A[i] /= rot;
    return choose(n * n / rot, A);
  }

  public int count(int n, int[] A) {
    // precalculate inversions
    for (int i=1; i<=100000; i++)
      inv[i] = calcInv(i);

    // checking whether all checkers fit onto the board
    long all = (long)n * (long)n;
    int sum = 0;
    for (int i=0; i < A.length; i++)
      sum += A[i];
    if (sum > all) return 0;

    // calculate T
    long T1 = calcT(n, A.clone(), 4);
    long T2 = calcT(n, A.clone(), 2);
    long T4 = calcT(n, A.clone(), 1);

    // calculate C
    long C1 = T1, C2 = T2 - T1, C4 = T4 - T2;
    while (C2 < 0) C2 += MODULE;
    while (C4 < 0) C4 += MODULE;

    // calculate answer
    long res = C1;
    res = (res + C2 * inv[2]) % MODULE;
    res = (res + C4 * inv[4]) % MODULE;
    return (int)res;
  }
}