April 28, 2021 TCO21 Algorithm Round 1B Editorials

HIndex

A good way to visualize the definition of the h-index is to use a histogram.

Imagine that we sorted the author’s papers in descending order based on their number of citations, and then we make a bar plot of the sequence. For example, for the sequence {8, 5, 4, 4, 4, 2, 1} we would get this:

X
X
X
XX
XXXXX
XXXXX
XXXXXX
XXXXXXX

8544421

After sorting, the h-index can be defined as the largest h such that each of the leftmost h papers has at least h citations. In the figure this can be seen as the size of the largest square that fits into the lower left corner of the histogram. For the above sequence the h-index is 4, as seen below.

X
X
X
XX
OOOOX
OOOOX
OOOOXX
OOOOXXX

Now we can easily solve the competition task. As there are at most 300 papers, we know that the answer is at most 300 and we can test all possible options. If we want to have h-index equal to some value H, we know exactly which square in the histogram we need to fill, and we can easily count how many extra citations we need. For example, below the letters C show the three extra citations needed to get to h-index 5 and the dots are additional citations that bring us to h-index 6.

X
X
X.....
XXCCC.
OOOOX.
OOOOX.
OOOOXX
OOOOXXX

Mathematically, in order to have h-index x, we need to look at the x currently most-cited papers and for each of them that has fewer than x citations we need to pay for the missing ones.

The above solution can be easily implemented in O(N^2), where N is the number of papers. If you want practice before the harder rounds of TCO, try finding another solution with a better time complexity!

public int cheat(int[] realCitations, int budget, int citationPrice) {

    Arrays.sort(realCitations);

    int N = realCitations.length;
    int maxPurchases = budget / citationPrice;

    int answer = 0;
    for (int h=1; h<=N; ++h) {
        int purchasesNeeded = 0;
        for (int i=0; i<h; ++i) if (realCitations[N-1-i] < h)
            purchasesNeeded += h - realCitations[N-1-i];
        if (purchasesNeeded <= maxPurchases) answer = h;
    }
    return answer;
}

Pancakes

If the number of pans P is greater than the number of pancakes N, some pans are clearly useless: we cannot cook more than N pancakes at the same time. So let U = min(P,N) be the number of useful pans.

In total, we need to cook 2N pancake sides. As we can cook at most U sides per minute, we surely need at least 2N/U minutes, rounded up. If we can find a schedule that always uses exactly ceiling(2N/U) minutes, we can be sure that the schedule will be optimal.

And luckily for us, such schedules do indeed always exist. One simple way to construct such a schedule is to start by picking a specific order of jobs: first we cook all pancakes from one side, then we cook all of them from the other side in the same order. An optimal schedule can now be constructed greedily by making the jobs in this order, U of them at a time.

For example, suppose we have N=5 pancakes and P=U=3 useful pans. We can order the jobs as follows:

ABCDEabcde

and then divide them into minutes as follows:

ABC, DEa, bcd, e--

This way of constructing the schedule clearly always uses the smallest possible number of minutes: except possibly for the last minute we are always using all the pans we can, so there cannot be any better solution.

The only thing that needs to be shown is that the schedule is always valid. The only way it could be invalid is if we tried to cook a pancake from both sides during the same minute. But this can never happen thanks to the specific order of jobs we chose. For any pancake, the two jobs for it are N steps apart (there are exactly N-1 other jobs between them). And as N >= U, this means that the first side cannot end in the same group of U jobs as the second side.

    public String[] makePancakes(int N, int P) {
        int U = Math.min(N, P); // useful pans
        int D = (2*N+U-1) / U;  // days needed
        char[] queue = new char[3*N];
        for (int n=0; n<N; ++n) {
            queue[n] = (char)('A'+n);
            queue[N+n] = (char)('a'+n);
            queue[2*N+n] = '-';
        }
        String[] answer = new String[D];
        for (int d=0; d<D; ++d) { 
            answer[d] = "";
            // take the next U available jobs
            for (int u=0; u<U; ++u) answer[d] += queue[d*U+u];
            // and fill in dashes for the useless pans
            while (answer[d].length() < P) answer[d] += '-';
        }
        return answer;
    }

Antiqueen

This counting problem will clearly have to be solved using some application of dynamic programming. The main idea is simple: we will go from 0 steps to N and for each number of steps we will look at each square of the board and compute the number of ways to reach that square after that number of steps. The number of ways in which we can reach (r,c) after n steps is the sum of the numbers of ways in which we can after n-1 steps reach some (r’,c’) such that jumping from (r’,c’) to (r,c) is a valid antiqueen move.

The trick is that a naive implementation runs in O(NR^2C^2): for each of the N*R*C states reachable after a positive number of steps we need to iterate over O(RC) cells we could have come from. As that is too slow, we need to come up with something more clever.

The more clever bit will be a faster way of counting the sum of all ways to reach a given square. Instead of O(RC) time, we will be able to do this in constant time after some precomputations.

If we want the sum over all squares (r’,c’) from which we can move to a given (r,c), we can get it as the sum over the entire board, minus the sum over the squares from which we cannot move to (r,c). These are the squares in the same row, in the same column, and on the same diagonals as (r,c).

Hence, we’ll do the following. Once we determine the number of ways to reach each square for some number of steps n, we will spend O(RC) time to iterate over the board once and we will precompute the total number of ways for each row, each column and each diagonal. Using these precomputed values we can then determine the number of ways to reach each square after n+1 steps in constant time. The total time complexity of the improved solution is O(NRC), which is fast enough.

    public int countPaths(int R, int C, int N) {
        long MOD = 1_000_000_007;
        long[][] ways = new long[R][C];
        // without moving there is 1 way to reach each cell: start there
        for (int r=0; r<R; ++r) for (int c=0; c<C; ++c) ways[r][c] = 1;

        for (int n=0; n<N; ++n) {
            // precompute the sum of ways over the entire board 
            // and the sum of ways for each row, column, diagonal

            long boardsum = 0;
            for (int r=0; r<R; ++r) for (int c=0; c<C; ++c)
                boardsum += ways[r][c];

            long[] rowsums = new long[R];
            long[] colsums = new long[C];
            long[] d1sums = new long[R+C-1];
            long[] d2sums = new long[R+C-1];
            for (int r=0; r<R; ++r) for (int c=0; c<C; ++c) {
                rowsums[r] += ways[r][c];
                colsums[c] += ways[r][c];
                d1sums[r+c] += ways[r][c];
                d2sums[r+C-1-c] += ways[r][c];
            }
        
            // for each cell, take the ways to reach all cells, subtract
            // the ways to reach cells in its row/column/diagonals
            // and fix that you just subtracted the cell itself four times
            long[][] nways = new long[R][C];
            for (int r=0; r<R; ++r) for (int c=0; c<C; ++c) {
                nways[r][c] = boardsum;
                nways[r][c] -= rowsums[r];
                nways[r][c] -= colsums[c];
                nways[r][c] -= d1sums[r+c];
                nways[r][c] -= d2sums[r+C-1-c];
                nways[r][c] += 3 * ways[r][c];
                nways[r][c] %= MOD;
                nways[r][c] += MOD;
                nways[r][c] %= MOD;
            }

            ways = nways;
        }
        long answer = 0;
        for (int r=0; r<R; ++r) for (int c=0; c<C; ++c) answer += ways[r][c];
        return (int)(answer % MOD);
    }