January 17, 2020 Single Round Match 775 Editorials

CompletelyDifferentStrings

Each position in the output string is completely independent of the others. For each position we know the letters we cannot use: the ones that are present in the forbidden array at that position. For example, if forbidden = {“cat”, “dog”, “doe”}, we know that:

• At index 0 we cannot use ‘c’ or ‘d’.
• At index 1 we cannot use ‘a’ or ‘o’.
• At index 2 we cannot use ‘t’, ‘g’, or ‘e’.

Once we know which letters we cannot use at some index, we also know how many different letters can be used at that index. The answer is simply the product of those counts.

For example, if we have the forbidden strings mentioned above and S = 26, we have 24 options for character 0, 24 options for character 1, and 23 options for character 2, so there are 24*24*23 strings that are completely different from the forbidden ones.

    public int count(int S, String[] forbidden) {
        int N = forbidden.length, L = forbidden[0].length();
        int answer = 1;
        for (int i=0; i<L; ++i) {
            boolean[] seen = new boolean[S];
            for (int n=0; n<N; ++n) seen[ forbidden[n].charAt(i) - 'a' ] = true;
            int unseen = 0;
            for (boolean s : seen) if (!s) ++unseen;
            answer *= unseen;
        }
        return answer;
    }

EnlargeTheCave

As the first step of our solution we will process the kobolds: for each kobold we mark all rocks that are around the kobold as rocks that cannot be excavated. This is clearly both necessary and sufficient to make sure none of the kobolds can enter our cave.

Once we did that, we can use any kind of graph traversal (e.g., DFS or BFS) to enlarge our cave. Below, we’ll describe how to use BFS. We’ll start by placing all vertices of the current cave into the BFS queue. Then we run BFS until one of two things happens: either our cave becomes exactly as large as we need, or the queue becomes empty. In the first case we return the current map, in the second case we know that we excavated everything we could and it still wasn’t enough, so there is no solution.

A single iteration of the BFS looks as follows: take a cell from the queue. For each rock that is adjacent to this cell and not marked as protected due to the kobolds, if the cave still isn’t large enough, excavate that cell and put it into the BFS queue.

The time complexity of this solution is linear in the size of the map.

    public String[] enlarge(String[] cave, int desiredArea) {
        int[] DR = {-1, 1, 0, 0};
        int[] DC = {0, 0, -1, 1};

        int R = cave.length;
        int C = cave[0].length();
       
        int currentArea = 0;
        boolean[][] isExcavated    = new boolean[R][C];
        boolean[][] canBeExcavated = new boolean[R][C];
        int[] Q = new int[2*R*C + 47];
        int qs=0, qf=0;

        // find all cave cells and put them into a BFS queue
        for (int r=0; r<R; ++r) for (int c=0; c<C; ++c)
        if (cave[r].charAt(c) == '.') {
            ++currentArea;
            isExcavated[r][c] = true;
            Q[qf++] = r;
            Q[qf++] = c;
        }

        // find all kobolds, mark cells around them as impossible to excavate
        for (int r=0; r<R; ++r)
            for (int c=0; c<C; ++c) canBeExcavated[r][c] = true;
        for (int r=0; r<R; ++r) for (int c=0; c<C; ++c)
        if (cave[r].charAt(c) == 'K') {
            canBeExcavated[r][c] = false;
            for (int d=0; d<4; ++d) {
                int nr = r+DR[d], nc = c+DC[d];
                if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
                canBeExcavated[nr][nc] = false;
            }
        }

        // run BFS until cave is large enough or until the queue becomes empty
        while (currentArea < desiredArea && qs < qf) {
            int cr = Q[qs++];
            int cc = Q[qs++];
            for (int d=0; d<4; ++d) {
                int nr = cr+DR[d], nc = cc+DC[d];
                if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
                if (isExcavated[nr][nc]) continue;
                if (!canBeExcavated[nr][nc]) continue;
                ++currentArea;
                isExcavated[nr][nc] = true;
                Q[qf++] = nr;
                Q[qf++] = nc;
                if (currentArea == desiredArea) break;
            }
        }

        if (currentArea < desiredArea) return new String[0];

        String[] answer = new String[R];
        for (int r=0; r<R; ++r) {
            answer[r] = "";
            for (int c=0; c<C; ++c)
                if (isExcavated[r][c]) answer[r] += '.';
                else answer[r] += cave[r].charAt(c);
        }
        return answer;
    }

IterateOverACube

The outline of our solution is as follows:

• Find a formula that will tell us, for a given s, how many cells (x,y,z) have x+y+z = s.
• Iterate over all s to find the correct one and the index of the cell we seek among those. That is, after this step we have a specific s and we know that we are looking for the index’-th cell among those with this s.
• Find a formula that will tell us, for a given s and x, how many cells (x,y,z) have x+y+z = s.
• Iterate over all x to find the correct one and the index of the cell we seek among those. That is, after this step we know s and x, and we know that we are looking for the index’’-th cell among those.
• Iterate over all y to find the right cell.

The second formula is easy. As s=x+y+z, we have y+z = s-x. If the value s-x is not in the range [0,2n-2], there are no such (y,z). If s-x is in [0,n-1], there are s-x+1 such (y,z): y can be anything between 0 and s-x, inclusive, and z is the rest. The remaining case is symmetric.

Two thirds of the first formula are also easy. If we have s in [0,n-1], the cells (x,y,z) with x+y+z = s form a “triangle” and there’s clearly (s+2 choose 2) such cells. (For a combinatorial argument, imagine s balls and two barriers arranged in a row. Each arrangement of these objects corresponds to one way of splitting s into x+y+z.)

If we have s in [2n-2,3n-3], the answer is the same by symmetry. More precisely, the answer for s in this range is the same as the answer for 3n-3-s.

The tricky part is the middle: the part where the cut of the cube is essentially a hexagon. A neat way of computing the number of cells for s in (n-1,2n-2) is as follows: Imagine that instead of our cube we are cutting the entire first octant of the space. The cut will be a triangle, just like in the first case. Of course, not all of those cells lie inside our cube, so we have to subtract those that don’t. But this is easy: the extra cubes are three identical triangles (corresponding to x>=n, y>=n, and z>=n, respectively), and as we know their size (which is m = s-n+1), we can compute the number of cells they contain. Hence, the formula for the middle cuts is (s+1)(s+2)/2 – 3*m*(m+1)/2.

   long cutSize(long N, long S) {
        if (S <= N-1) return (S+1)*(S+2)/2;
        if (S >= 2*N-2) { S = 3*N-3-S; return (S+1)*(S+2)/2; }
        long full_triangle = (S+1)*(S+2)/2;
        long missing_side = S - (N-1);
        long missing_area = missing_side * (missing_side+1) / 2;
        return full_triangle - 3*missing_area;
    }
   
    public int[] findCell(int N, long index) {
        // find the correct sum
        int S = 0;
        for (; S<=3*N-3; ++S) {
            long cs = cutSize(N,S);
            if (cs <= index) index -= cs; else break;
        }

        // find the correct x
        int x = 0;
        for (; x<N; ++x) {
            int remains = S-x;
            if (remains < 0) continue;
            if (remains > 2*N-2) continue;
            long cs = (remains <= N-1) ? remains+1 : 2*N-1-remains;
            if (cs <= index) index -= cs; else break;
        }
        // find the correct y and z
        for (int y=0; y<N; ++y) {
            int z = S-x-y;
            if (z < 0 || z >= N) continue;
            if (index == 0) return new int[] {x,y,z};
            --index;
        }
        return new int[0]; // should not happen
    }

CardDrawGame

The constraints are rather small, so we should be able to try all possibilities if we don’t do it in a too naive way.

The first observation is that we can have up to 2000 different cards, but only 20 different values. So, we won’t iterate over all (roughly 2000^3) possibilities of the three cards we can draw but we will iterate over all (only roughly 20^3) possibilities for the three values we’ll draw. For each of these we will determine the probability that we draw those exact cards (this is easy) and the probability that we’ll win from having those cards in hand (this is explained below). The answer we seek is simply a weighted sum of the probability of winning over all these possibilities.

The subproblem that remains is the following one: I know the three cards in my hand and I know the multiset of cards in my deck. What is the optimal way of swapping some cards, and what win probability does it produce?

In my solution, I solved this problem using some simple dynamic programming. Given the cards in deck, I compute the probabilities p(x,y): given that I draw x cards from the deck at random (where 0 <= x <= 3), what is the probability that I will draw cards with sum y?

Once I know these values, I can iterate over all subsets of cards I can keep (making sure not to discard more than I have left to draw). Once I fix the cards I want to keep, I know their sum, hence I know the sum I want to see on the cards I draw, and that’s exactly what I precomputed above.

    vector< vector<long long> > get_ways(int target, const vector<int> &count) {
        vector< vector<long long> > answer(4, vector<long long>(target+1,0));
        answer[0][0] = 1;
        for (int m=0; m<int(count.size()); ++m) {
            // process cards with value m
            for (int c=3; c>=1; --c)
            for (int u=1; u<=min(c,count[m]); ++u)
            for (int v=u*m; v<=target; ++v)
                answer[c][v] += binomial(count[m],u) * answer[c-u][v-u*m];
        }
        return answer;
    }

    double winChance(int target, vector<int> count) {
        long long totalCards = accumulate(count.begin(), count.end(), 0);
        long long totalChoices = (totalCards*(totalCards-1)*(totalCards-2)) / 6;

        double answer = 0;

        int M = count.size()-1;
        for (int a=0; a<=M; ++a)
        for (int b=a; b<=M; ++b)
        for (int c=b; c<=M; ++c) {
            // initial hand (a,b,c)
            long long waysToDraw = 0;
            if (a < b && b < c)
                waysToDraw = 1LL * count[a] * count[b] * count[c];
            if (a == b && b == c)
                waysToDraw = 1LL * count[a] * (count[a]-1) * (count[a]-2) / 6;
            if (a < b && b == c)
                waysToDraw = 1LL * count[a] * count[b] * (count[b]-1) / 2;
            if (a == b && b < c)
                waysToDraw = 1LL * count[a] * (count[a]-1) * count[c] / 2;

            vector<int> newcount = count;
            --newcount[a]; --newcount[b]; --newcount[c];
            if (newcount[a] < 0 || newcount[b] < 0 || newcount[c] < 0) continue;

            double maxWinProb = 0.;
            if (a+b+c == target) maxWinProb = 1.;

            auto ways = get_ways(target, newcount);

            // try discarding 1-3
            if (totalCards >= 4) {
                { int needed = target-a-b; if (0 <= needed && needed <= target) maxWinProb = max( maxWinProb, 1. * ways[1][needed] / (totalCards-3) ); }
                { int needed = target-a-c; if (0 <= needed && needed <= target) maxWinProb = max( maxWinProb, 1. * ways[1][needed] / (totalCards-3) ); }
                { int needed = target-b-c; if (0 <= needed && needed <= target) maxWinProb = max( maxWinProb, 1. * ways[1][needed] / (totalCards-3) ); }
            }
            if (totalCards >= 5) {
                { int needed = target-a; if (0 <= needed && needed <= target) maxWinProb = max( maxWinProb, 2. * ways[2][needed] / (totalCards-3) / (totalCards-4) ); }
                { int needed = target-b; if (0 <= needed && needed <= target) maxWinProb = max( maxWinProb, 2. * ways[2][needed] / (totalCards-3) / (totalCards-4) ); }
                { int needed = target-c; if (0 <= needed && needed <= target) maxWinProb = max( maxWinProb, 2. * ways[2][needed] / (totalCards-3) / (totalCards-4) ); }
            }
            if (totalCards >= 6) {
                { int needed = target; if (0 <= needed && needed <= target) maxWinProb = max( maxWinProb, 6. * ways[3][needed] / (totalCards-3) / (totalCards-4) / (totalCards-5) ); }
            }

            // add to answer
            answer += waysToDraw * maxWinProb;
        }
        return answer / totalChoices;
    }

FairSplit

Four consecutive bags are easy to split: x + (x+3) is the same as (x+1) + (x+2). Thus, whenever (A,B) is fair, (A,B+4k) must also be fair. And, in particular (A,A+4k+3) is always fair. That was the easy part.

Given (A,A+n), the total number of candies is (2A+n)(n+1)/2. A necessary condition for the solution to exist is that this sum must be even. As 2A+n and n+1 have different parities, one of them must therefore be divisible by 4. The value n+1 being a multiple of 4 gives us the case mentioned above. The other case differs based on the parity of A: for even A we may have solutions with n=4k, for odd A solutions with n=4k+2.

The problem with this second type of solutions is that it not always exists. For example, if A=7 and n=2, we have the bag sizes {7,8,9}. Their sum is even, but the pair (7,9) clearly isn’t fair.

Where’s the problem? Well, first of all, we should realize that both for n=4k and for n=4k+2 the total number of bags we have is odd. Thus, one of the boys must get more bags than the other. This gives us a second necessary condition: Clearly, a solution does not exists if the boy with more bags is guaranteed to have more candy. The split that gives the boy with more bags the least candy is the split where the boy gets the n/2 + 1 smallest bags and his brother gets the n/2 largest. If this split gives the first boy too many candies, there is no solution.

Luckily for us, the above condition is not just necessary but also sufficient: if, for this particular split of bags, the first boy has too few candies, we can gradually change the split by one candy in each step by always swapping some bag with x candies for a bag with x+1 candies from his brother.

When we work out the formulas for the sum of the smallest and biggest bags, this condition simplifies to a very simple condition: the pair (A,A+n) is fair if n has the correct remainder modulo 4 and (n/2)^2 >= A.

To compute the final answer, we can now proceed as follows: Split all A into groups according to their remainder modulo 4. For each group, calculate the number of fair pairs of the first type (this is an arithmetic sequence with difference -1). Then, split all those As into new groups according to the smallest x such that x^2 >= A. For each of these new groups, calculate the number of fair pairs of the second type. (Again, this is an arithmetic sequence with difference -1, as all those As share the same smallest n that works.)

The total number of cases we consider is O(sqrt(max value)), which is fast enough by a wide margin.