October 26, 2021 Single Round match 817 Editorials

ShoppingStickers

We need to make one observation: merging two purchases into one bigger purchase will never give us fewer stickers than the two original purchases.

This should be pretty obvious. Suppose the first purchase involves paying (a*S + b) dollars and getting a stickers, and the second purchase involves paying (c*S + d) dollars and getting c stickers. If we make both purchases together, we will pay (a*S + c*S + b + d) dollars and we are guaranteed to get at least a+c stickers. (If b+d happens to be at least S, we will get one extra sticker.)

Thus: if we want the most stickers, we can simply buy everything at once.

The same observation can also be used in the other direction: if I take any purchase and split it into two smaller purchases, the number of stickers cannot increase. Hence, if we want the smallest total number of stickers, we can simply purchase each item separately.

public int[] purchase(int S, int[] items) {
    int A = 0;
    for (int x : items) A += x;
    A /= S;
    
    int B = 0;
    for (int x : items) B += x / S;

    return new int[] { A, B };
}

Gym

We need an efficient way to simulate what’s going on at the gym. The main observation: as the machines are (from the point of view of our task) identical, we do not care who uses which machine. More precisely, we don’t need to track which machines are occupied, we just need to know how many of them there are.

An easy but useful trick is to get rid of the fractional times by multiplying all times by 2. In the new version of the problem clients arrive at even times and clients who stayed depart at odd times.

We don’t need any fancy data structure for the simulation, a simple array will do. The last customer will arrive at time 2(N-1). All departures from the gym that happen after this moment don’t matter, so we only need to track the earlier departures. We will have an array in which we’ll record, for each time before the last customer’s arrival, the number of customers departing.

We will simply simulate the gym one second at a time.

• At even times we check a new customer. If there are no machines available, we send them away. If there are some, the customer starts using a machine. We decrease the number of available machines, calculate the customer’s departure time, and if it’s early enough, we record this customer in the array mentioned above. 
• At odd times, we check how many customers are leaving and we increase the number of available machines by the number of people who left.

(The time limit was loose, so solutions that used priority queues to store the customers currently present in the gym should have also fit into the time limit, even though they have an extra logarithmic factor.)

public int calculateProfit(int M, int N, int T) {
    int[] depart = new int[2*N];
    int availableMachines = M;
    int profit = 0;
    for (int n=0; n<N; ++n) {
        // one client arrives at time n
        if (availableMachines > 0) {
            ++profit;
            --availableMachines;
            int twiceTimeOut = (int)(2*n + 1 + 2*((1L * n * n) % T));
            if (twiceTimeOut < depart.length) {
                ++depart[twiceTimeOut];
            }
        }
        // some clients leave at time n + 0.5
        availableMachines += depart[2*n+1];
    }
    return profit;
}

DogsInAGrid

As is the case in constructive tasks, there can be multiple valid solutions. The one we describe is the one we find easy to both discover and implement. 

Once we start playing with small patterns, it’s easy to discover a good solution for three rows. (In fact, this happens to be an optimal solution for three rows.)

  DDDDDDD
  OOOOOOO
  GGGGGGG

With C columns, this produces 3C-4 dogs: C vertically, C-2 in one diagonal direction and C-2 in the other.

This pattern can easily be repeated:

  DDDDDDD
  OOOOOOO
  GGGGGGG
  OOOOOOO
  DDDDDDD
  .......

This way, adding two more rows adds 3C-4 dogs. This produces a 39×40 matrix with 2204 dogs. We can fit 19 dogs into the last row for a total of 2223 dogs, which is (one more than) enough.

Once we know a pattern for 2222+ dogs, we can create a pattern for any smaller number of dogs, for example as follows:

1. Start with the board full of ‘O’s, there are no dogs.
2. One character at a time, create the above pattern and keep track of the current number of dogs.
3. Once the number of dogs we still need becomes 19 or fewer, add those dogs in the last row of the grid and terminate. (For our pattern, adding these dogs one at a time does not create any other dogs, so we can always hit the target number exactly.)

IntrospectiveNumbers

Given the exact set of digits used, we can count the introspective numbers using multinomial coefficients – or, equivalently, using a product of binomial coefficients. For example, the count of introspective numbers with the numbers 1, 2, 4 is (choose(7, 4) * choose(7-4, 2) * choose(7-4-2, 1)). This is derived as follows: there are 1+2+4 = 7 positions total. We choose which four of them are 4s, then we choose which two of the remaining three are 2s, and then we choose which one position of the remaining one position is the position with the 1.

Using the above formula we can count the total count of introspective numbers for each length: iterate over all 511 nonempty sets of nonzero digits, and for each of them calculate the count of such numbers and add it to the total for the corresponding length.

The above approach can also be generalized to count introspective numbers with any given prefix. For example, suppose we want to count all 13-digit introspective numbers that start “433”. We can do so efficiently as follows:

• There are 10 positions left to be filled.
• We know that some of those positions will need to contain the remaining 3s and 4s. Let’s count these first.
• We need to choose one of the available positions that will contain the remaining digit 3. This choice can be done in choose(10,1) ways.
• Once we make that choice, there are 9 positions left. Out of those, three must contain the remaining 4s. These positions can be chosen in choose(9,3) ways.
• Once we chose where to place the 3s and 4s, there are still 6 positions left. These need to be filled with digits other than 3 and 4. We can iterate over all sets of digits other than 3 and 4 to find those sets that have sum 6. (In this case, these would be {6} and {1,5}.) For each of them separately, we count the number of ways to arrange those digits on the remaining positions. The total count of ways to fill in the last 6 unoccupied positions is the sum over all these mutually disjoint sets of options.

And with this in place, the task becomes solvable in a very standard way. First we determine the length of the number we seek: for each length we calculate the count of introspective numbers of that length until we have enough of them. Then we construct the number we seek by finding its digits from the most significant to the least significant one.

In each step of this solution we are in the same situation: we have already counted and discarded all introspective numbers between 1 and some threshold, and we have the index of the number we seek among the numbers we haven’t processed yet. We then count the next group of numbers. If their count is greater than the index we have, the number we seek is among them. Otherwise, we skip the whole block of numbers and we subtract their count from the index.

For example, suppose we already know that we want the number at index 1234 among all numbers of length 13 that start “433”. We can now count numbers that start “4331”. If there’s, for example, 2000 of those, our number is among them and thus we have determined the next digit. If there’s, for example, just 1000 of those, we discard them all and now we are looking for the number at index 234 among all 13-digit numbers of the form “433x…” with x >= 2. We then try the prefixes 4332, 4333, 4334, and so on, until we find the correct value of the next digit.

In the implementation there are two places where we should be careful: making sure that our counting does not overflow (cap all counts at 10^18+1), and when counting the numbers for a given prefix, don’t forget to handle the situation where the chosen set of digits does not fit into the number.

long MAX = 1_000_000_000_000_000_000L;
long[][] binomial;
long[] countLength;

long mul(long a, long b) {
    if ((MAX+1) / a < b) return MAX+1;
    return Math.min( a*b, MAX+1 );
}

void precompute() {
    binomial = new long[100][];
    for (int n=0; n<100; ++n) {
        binomial[n] = new long[n+1];
        for (int k=0; k<=n; ++k) {
            if (k == 0 || k == n) {
                binomial[n][k] = 1;
            } else {
                binomial[n][k] = binomial[n-1][k-1] + binomial[n-1][k];
                if (binomial[n][k] > MAX) binomial[n][k] = MAX+1;
            }
        }
    }

    countLength = new long[46];
    int[] selected = new int[10];
    for (int sub=2; sub<(1<<10); sub+=2) {
        int sc = 0;
        int total = 0;
        for (int n=0; n<10; ++n) if ((sub & 1<<n) != 0) {
            selected[sc++] = n;
            total += n;
        }
        int remain = total;
        long curr = 1;
        while (remain > 0) {
            curr = mul(curr, binomial[remain][selected[sc-1]] );
            remain -= selected[sc-1];
            --sc;
        }
        countLength[total] += curr;
        countLength[total] = Math.min( countLength[total], MAX+1 );
    }
}

long countWithPrefix(int[] partial, int pl) {
    int[] placed = new int[10];
    for (int i=0; i<pl; ++i) ++placed[ partial[i] ];
    for (int n=1; n<10; ++n) if (placed[n] > n) return 0;

    int totalForced = 0;
    for (int n=1; n<10; ++n) if (placed[n] > 0) totalForced += n;
    if (totalForced > partial.length) return 0;

    int remains = partial.length - pl;

    long curr = 1;
    for (int n=1; n<10; ++n) if (placed[n] > 0) {
        curr = mul( curr, binomial[remains][n - placed[n]] );
        remains -= (n - placed[n]);
    }

    int[] available = new int[10];
    int ac = 0;
    for (int n=1; n<10; ++n) if (placed[n] == 0) available[ac++] = n;

    long optionsForRest = 0;
    int[] selected = new int[10];
    for (int asub=0; asub<(1<<ac); ++asub) {
        int sc = 0;
        int stotal = 0;
        for (int i=0; i<ac; ++i) if ((asub & 1<<i) != 0) {
            selected[sc++] = available[i];
            stotal += available[i];
        }
        if (stotal != remains) continue;
        long these = 1;
        int tmp = remains;
        for (int i=0; i<sc; ++i) {
            these = mul( these, binomial[tmp][selected[i]] );
            tmp -= selected[i];
        }
        optionsForRest += these;
        optionsForRest = Math.min( optionsForRest, MAX+1 );
    }
    return mul(curr, optionsForRest);
}

public String nth(long index) {
    precompute();
    int length = 1;
    while (index >= countLength[length]) {
        index -= countLength[length];
        ++length;
    }
    System.out.println("correct length "+length+" index within length "+index);
    int[] answer = new int[length];
    for (int p=0; p<length; ++p) {
        for (answer[p]=1; answer[p]<10; ++answer[p]) {
            long curr = countWithPrefix(answer, p+1);
            if (curr > index) break; else index -= curr;
        }
    }
    String finalAnswer = "";
    for (int x : answer) finalAnswer += x;
    return finalAnswer;
}

Hagar

We will start by discarding all empty castles. If nothing remained, the answer is 0. From this point on we assume that each castle has a positive amount of gold.

The optimal strategy for each player is a mixed strategy: they will choose each option with some probability.

Suppose we know that Hagar’s strategy is to choose exactly K castles with a non-zero probability. Then, it’s clearly optimal for Hagar for those to be the K castles with the most gold.

Formal proof: Suppose we know the optimal strategy for Hagar and for the king if Hagar chooses the K most expensive castles with a nonzero probability. The king’s strategy is some probability distribution on those K castles. For each of Hagar’s possible choices we can calculate Hagar’s expected profit as the sum of (gold in a castle) times (probability that the castle is not defended). Let P be the largest of those values. The king’s strategy guarantees that Hagar’s expected profit cannot exceed P.

Can Hagar do better by selecting from a different set of exactly K castles? No. This is because the king can map those castles to the K most expensive ones (maximum of the new set to the maximum of the old set, and so on) and then use the same strategy. For each of Hagar’s possible choices we can again calculate Hagar’s expected profit as the sum of (gold in a new castle) times (probability that the castle is not defended). The probabilities are the same, the amount of gold in each castle is at most the same, so by using the same strategy as above the king can still guarantee that Hagar’s profit cannot exceed P. And this means that Hagar cannot gain anything by choosing a set of K castles with smaller amounts of gold.

This gives us only N strategy types for Hagar to consider: one for each number of castles that may be raided.

Now let’s look at one of those cases and find the actual optimal strategy for Hagar – i.e., the probability distribution with which he should raid each of the K castles.

Here we can use the principle of indifference: In order for Hagar’s choice to be optimal, even if the king knows Hagar’s strategy, there is nothing he can do, because for the king all the sensible options give the same expected outcome. Let’s see this on an example:

Suppose we have four castles with A, B, C, D tons of gold. Hagar wants to choose the castle with X tons of gold with probability x > 0. From the king’s point of view we can compute as follows: if the king chooses to defend castle A, Hagar’s expected profit will be b*B+c*C+d*D. If the king defends castle B, Hagar’s profit will be a*A+c*C+d*D. And so on. The king can force the smallest of these outcomes by deterministically picking that option. And, in turn, this means that if the outcomes aren’t all equal, Hagar can improve the final result by increasing that minimum – i.e., tweaking his probabilities in a way that increases the worst option(s) at the expense of the bigger ones. Hence, if Hagar’s choice is optimal, the four king’s choices all give the same expected outcome.

This gives us four equations with four variables. Three of them simplify quite significantly: e.g., from the first two expected profits we get b*B+c*C+d*D = a*A+c*C+d*D, which simplifies to a*A = b*B. Hence, three of the four equations are a*A = b*B = c*C = d*D, and the fourth one is a+b+c+d = 1: probabilities always sum to 1.

Let’s set a*A = b*B = c*C = d*D = q. Then, a+b+c+d = 1 becomes q/A + q/B + q/C + q/D = 1, and thus q = 1 / (1/A + 1/B + 1/C + 1/D). Then, Hagar’s expected profit is b*B+c*C+d*D = 3*q.

In general, for any subset of K castles, q is the reciprocal of the sum of reciprocals of all gold amounts in those castles, and then Hagar’s expected profit is (K-1)*q. Hagar can choose the maximum profit over all choices of K. (For this particular profit we have just found Hagar’s strategy that guarantees he gets at least this expected profit, and we can also compute the probabilities for the king’s strategy that guarantees Hagar gets at most this expected profit.)

As a reward, the implementation is very simple:

public double expectedProfit(int[] gold) {
    Arrays.sort(gold);
    int N = gold.length;
    int lo = 0;
    while (lo < N && gold[lo] == 0) ++lo;
    double answer = 0.;
    for (; lo<N; ++lo) {
        // find the optimal solution assuming Hagar attacks castles in [lo,N)
        double denominator = 0;
        for (int i=lo; i<N; ++i) denominator += 1. / gold[i];
        double numerator = (N-lo-1);
        answer = Math.max( answer, numerator / denominator );
    }
    return answer;
}