Scissors

For each second, let’s observe how many scissors are free (opened):

0: 1
1: 2
2: 4
3: 8
4: 16
…

At time t, 2^t of the scissors are free. We want to find the first time that we can have N + 1 scissors free. Use a for loop and find this moment.

  public int openingTime(int N) {
        long free = 1, locked = N;
        int timeElapsed = 0;
        while (locked > 0) {
            timeElapsed += 10;
            long willOpen = Math.min(free, locked);
            locked -= willOpen;
            free += willOpen;
        }
        return timeElapsed;
    }

MaximumBalances

The optimal way is to construct a string like this: ()()()()…
This way, having o opening brackets and c closing brackets, the answer is min(o, c) * (min(o, c) + 1) / 2.

The proof that this pattern is optimal can be made after observing that whenever we have nested parentheses, we can increase the beauty of the string by removing one level of nesting. E.g., if you have (S), changing it to ()S will increase the number of balanced substrings.

public int solve(String s) {
        	int open = 0, closed = 0;
        	for(int i = 0; i < s.length(); i++) {
            		if(s.charAt(i) == '(') open++;
            		else closed++;
        	}
        	int n = Math.min(open, closed);
        	return (n*(n+1))/2;
    	}

ValueDivision

Consider the following case:

{7, 7, 7, 7}
Returns: {4, 5, 6, 7 }

The idea comes to mind. Each time you find the maximum number that has more than one occurrence, apply the operation on it. In fact, you do the operation several times such that the number of occurrences of maximum becomes one. It is obvious that it’s impossible to remove the maximum completely. So, what is the best option? Keep the last one and decrease the remaining ones.

def getArray(self, A):
        A = list(A)
        last_max = 10**9 + 47
        while True:
            curr_max, curr_last = 1, None
            for i in range(len(A)):
                if A[i] < last_max and A[i] >= curr_max:
                    curr_max = A[i]
                    curr_last = i
            if curr_max == 1:
                break
            for i in range(curr_last):
                if A[i] == curr_max:
                    A[i] -= 1
            last_max = curr_max
        return A

SpeedingUpBozosort

[misof:] The nicest part of this problem is the central idea it illustrates. Did you intuitively expect that making multiple random swaps will actually speed up the algorithm? If not, why? And if you did, what exactly do you now expect about a more general question: how many swaps are optimal? Is there a threshold beyond which you are doing too many? And does the answer change if we count comparisons and swaps together, instead of just comparisons? What is the optimal number of swaps per round in that setting? (The total number of comparisons and swaps is obviously proportional to the actual running time.)

The number of states is at most 6! = 720. The first thing we need to calculate is the transition matrix. This is to calculate trans[p][q] = probability to get q from p after numSwaps swaps.

For each p, let’s calculate the trans[identity permutation][p] where identity permutation is 1, 2, 3, …, N. Calculating other values is easy then.

Let t[p][k] = probability of reaching p from identity permutation after exactly k moves. t[identity permutation][0] = 1. It’s easy to calculate the values in O(numSwaps * N! * N ^ 2). Even it can be solved using matrix multiplication in O(log(numSwaps) * N! * N ^ 2). It is not needed by the way.

Now the problem is classical. We have a graph, we start from a vertex. We random walk to other vertices to reach a vertex). It can be solved using a system of equations. Let dp[p] be the answer if we start from vertex p (that stands for a permutation). Let checkNeed(p) be the number of checks need to be done on p to detect if it’s sorted or not.

For the destination (where permutation is sorted) dp[dest] is equal to checkNeed(dest). Consider a not sorted permutation p, It leads to a normal system of linear equations. Read about how to solve them using the Gauss method here.

   int[] factorial = {1, 1, 2, 6, 24, 120, 720, 5040};
    int[] nton = {1, 1, 4, 27, 256, 3125, 46656, 823543};
    int[] simplify;

    int[][] generatePermutations(int N) {
        if (N == 0) return new int[][] { {} };
        int[][] answer = new int[factorial[N]][N];
        int x = 0;
        for (int[] prev : generatePermutations(N-1)) {
            for (int i=N-1; i>=0; --i) {
                int y = 0;
                for (int j=0; j<i; ++j) answer[x][y++] = prev[j];
                answer[x][y++] = N-1;
                for (int j=i; j<N-1; ++j) answer[x][y++] = prev[j];
                ++x;
            }
        }
        return answer;
    }

    int fastCode(int[] perm) {
        int N = perm.length;
        int code = 0;
        for (int x : perm) code = N*code + x;
        return code;
    }

    int encode(int[] perm) {
        return simplify[fastCode(perm)];
    }

    public double expectedComparisons(int[] A, int numSwaps) {
        // generate all permutations and implement a handy way of encoding+decoding them
        int N = A.length;
        int[][] permutations = generatePermutations(N);
        simplify = new int[nton[N]];
        for (int n=0; n<factorial[N]; ++n) simplify[fastCode(permutations[n])] = n;

        // check which among them sort A, and precalculate the number of comparisons
        // made when each of them is checked during bozosort
        boolean[] isSorted = new boolean[factorial[N]];
        int[] comparisonsWhenChecked = new int[factorial[N]];
        for (int n=0; n<factorial[N]; ++n) {
            isSorted[n] = true;
            for (int i=0; i+1<N; ++i) {
                ++comparisonsWhenChecked[n];
                if (A[ permutations[n][i] ] > A[ permutations[n][i+1] ]) {
                    isSorted[n] = false;
                    break;
                }
            }
        }

        // for the identity permutation use DP to precalc the probability of getting
        // each permutation after swaps
        double[] oldProbs = new double[factorial[N]];
        oldProbs[0] = 1.;
        int[] tperm = new int[N];
        for (int sw=0; sw<numSwaps; ++sw) {
            double[] newProbs = new double[factorial[N]];
            for (int n=0; n<factorial[N]; ++n) if (oldProbs[n] != 0) {
                for (int x=0; x<N; ++x) for (int y=0; y<N; ++y) {
                    for (int i=0; i<N; ++i) tperm[i] = permutations[n][i];
                    int tmp = tperm[x]; tperm[x] = tperm[y]; tperm[y] = tmp;
                    newProbs[ encode(tperm) ] += oldProbs[n] / N / N;
                }
            }
            oldProbs = newProbs;
        }

        // precompute the whole matrix of transition probabilities
        double[][] trans = new double[factorial[N]][factorial[N]];
        for (int n=0; n<factorial[N]; ++n) {
            int[] cperm = new int[N];
            for (int p=0; p<factorial[N]; ++p) {
                // with probability oldProbs[p], swaps turn the identity into permutation p
                // we need to calculate the same effect on our permutation
                for (int i=0; i<N; ++i) {
                    cperm[i] = permutations[n][ permutations[p][i] ];
                }
                trans[n][encode(cperm)] += oldProbs[p];
            }
        }

        // build a system of linear equations
        int M = factorial[N];
        double[][] E = new double[M][M+1];
        for (int n=0; n<M; ++n) {
            E[n][n] = 1;
            E[n][M] = comparisonsWhenChecked[n];
            if (isSorted[n]) continue;
            for (int p=0; p<M; ++p) E[n][p] -= trans[n][p];
        }

        // solve the system of linear equations
        for (int c=0; c<M; ++c) {
            int rmax=c;
            for (int r=c; r<M; ++r) if (Math.abs(E[r][c]) > Math.abs(E[rmax][c])) rmax = r;
            for (int c2=c; c2<=M; ++c2) { double tmp=E[rmax][c2]; E[rmax][c2] = E[c][c2]; E[c][c2] = tmp; }
            for (int r=c+1; r<M; ++r) {
                double q = - E[r][c] / E[c][c];
                for (int c2=c; c2<=M; ++c2) E[r][c2] += q * E[c][c2];
            }
        }
        double[] solutions = new double[factorial[N]];
        for (int r=M-1; r>=0; --r) {
            double rhs = E[r][M];
            for (int c=r+1; c<M; ++c) rhs -= E[r][c] * solutions[c];
            solutions[r] = rhs / E[r][r];
        }
        return solutions[0];
    }

TAASquares

(The solution to this problem, including the comment on points, was written by misof.)

Below is construction for N = 10 that has all row and column sums distinct.

For easier reading, it is split into halves.

00000|00000
00000|00002
00000|00022
00000|00222
00000|02222
—–+—–
00001|22222
00001|22222
00012|22222
00122|22222
01222|22222
12222|22222

The top half are the sums 0, 2, 4, 6, 8; the left half are 1, 3, 5, 7, 9; the right half are 10, 12, 14, 16, 18; and the bottom half are 11, 13, 15, 17, 19.

This construction easily generalizes for any even N and it’s clearly optimal.

For an odd N, we can take the above matrix for N+1 and, for example, drop the topmost row and the leftmost column. This only decreases the sum of the last row by 1, making one collision: the last row and the last column now have the same sum. 

What remains in this solution is to show that for odd N we cannot have all sums distinct. (An aside: Obviously, this part was not necessary during the contest. This, together with the observation that the medium problem’s implementation takes time and thus the scores on it will generally be lower, were the two main reasons for setting the point value for this problem only at 800 points. At the same time, this problem does subjectively require more creativity than this round’s medium, which is a part of why it’s worth more.)

Suppose N is odd and all line sums are distinct. 

Imagine that we start in the position where each cell in the matrix is a 1 and thus each line has sum N. We are now going to change some 1s into 0s and 2s so that we shift the sums away from N.

On one hand, we know that at the end only one sum can remain N. Only two can be N-1 and N+1, which requires at least one change in each of them. Then, only two can be N-2 and N+2, and so on. Thus, if we count the number of changes for each line separately, we must get the sum of at least 0 + 1 + 1 + 2 + 2 + … + (N-1) + (N-1) + N = N^2 changes.

On the other hand, let’s proceed as follows. Imagine you already have an NxN matrix with all line sums distinct. For better imagination, sort both rows and columns according to their sum. (This is clearly independent: when you sort columns you don’t change row sums.) Pick the N lines with the highest sums and use a highlighter to highlight them. If this includes R rows and C = N-R columns, we now have a R*C block that has been highlighted twice.

Note that each highlighted line has sum at least N, and each other line has sum at most N. Thus, if we start with all 1s and we want to produce this matrix, we want to shift the sums of highlighted lines up and the sums of other lines down. Changes with this effect are called good, changes with the opposite effect are called bad. From the above observation we can now easily derive that we need (total # of good changes) – (total # of bad changes) >= N^2, but is this possible?

Each change in the once-highlighted region is neutral: it’s bad for its row and good for its column, or vice versa. Each change of a 1 to a 2 in the twice-highlighted region is twice good (both in its row and in its column), and each change of a 1 to a 0 in the not-highlighted region is also twice good. Their opposites are twice bad. 

Thus, the best we can get is (# of good changes) – (# of bad changes) = 2*(number of twice-highlighted cells) + 2*(number of not-highlighted cells) = 4*R*(N-R). 

If N is odd, regardless of what R we choose, 4*R*(N-R) < N^2 and thus we cannot make enough good changes to make all sums distinct, q.e.d. 

Additionally, note that this insight tells us that in any valid solution for an even N we must have R = N/2 and all the above good changes must be a part of the solution. This quite significantly limits the space of possible solution patterns.

  public String[] construct(int N) {
        if (N == 4) return new String[] { "2212", "2002", "0002", "2102" };
        if (N == 5) return new String[] { "12222", "00012", "02221", "00110", "00122" };
        if (N == 1) return new String[] { "1" };
        String[] answer = new String[N];
        for (int n=0; n<N; ++n) answer[n] = "";
        for (int r=0; r<N; ++r) {
            for (int c=0; c<N; ++c) {
                if (c < N-1-r) { answer[r] += '0'; continue; }
                if (c > N-1-r) { answer[r] += '2'; continue; }
                if (r < N/2) answer[r] += '0'; else answer[r] += '1';
            }
        }
        return answer;
    }