July 17, 2020 2020 TCO Round 2B Editorials

FixedNumberOfDigits

We can break the infinite sequence of numbers you will write into blocks according to the number of digits they have.

We will process the blocks one at a time, in order. For each block, we can compute how many numbers it contains (via a formula in constant time, or via binary search and checking whether a number X steps away still has the correct number of digits). Once we know the count of numbers in each block, we know how many digits it contains. If it’s strictly less than the number we should write, we subtract the count for the block from the number of digits we should write and move to the next block. Otherwise, the answer is in the current block. We determine how many numbers were fully written and then the correct part of the next number.

long current = start;
    	for (int d = digitCount(current); ; ++d) {

        	// find out how many numbers (x) we would write with exactly d digits

        	long hi = 1; for (int i=0; i<d; ++i) hi *= 10;
        	long x = (hi - current + step - 1) / step;

        	// if we need more digits, write all of them

        	if (d * x < numberOfDigits) {
            	numberOfDigits -= d * x;
            	current += x * step;
            	continue;
        	}

        	// if we got here, this length is where the fun stops
        	// write full numbers until you reach or exceed the limit,
        	// then erase last digits until you are at the limit

        	x = (numberOfDigits + d - 1) / d;
        	numberOfDigits -= d * x;
        	current += (x-1) * step;
        	while (numberOfDigits < 0) {
            	current /= 10;
            	numberOfDigits += 1;
        	}
        	return current;
    	}

RoomPairs

There are many possible constructions. Below I show a simple inductive one with very few special cases.

For now, assume that all inputs are solvable. Then, we can make the following observations:

• If R > 1 and N >= 2C-1, we can solve the problem for (R-1, C, N-2C+1) and then add an extra row of unit squares.
• The same with adding an extra column.
• If R > 1 and N <= the maximum solution for (R-1, C), we can solve the problem for (R-1, C, N) and then extend each room in its bottom row by adding one square in the next row to the room.
• The same with extending the rooms into the next column.

We can easily verify that this will reduce any large input into a smaller one, until we run into either the trivially solvable (1, 1, 0) or into trouble. The trouble is that the case (2, 2, 2) has no solution. This can easily be verified manually: if we divide a 2×2 building into four rooms we have four pairs, if we do three rooms we have three pairs, if we do two rooms we have one pair, and with one room we have no pairs.

Luckily, all other cases are solvable. In my implementation of the above solution (including this particular order in which the rules are applied) I needed to special-case the inputs (3, 2, 2) and (3, 2, 5).

Eggheads

The solution is a state-based dynamic programming. A state of the game (after zero or more rounds) can be described using five sets of elements: the set of your players who played and won, the set of your players who have played and lost, two similar sets of their players, and a set of topics that have already been used. More compact representations are possible, but this sparse representation of a state is easier to work with (the whole state fits into an int as a bitmask) and the number of states is low enough so that we don’t have to worry about efficient encoding too much.

Evaluation of an individual round with two known players and a known topic can be done via a small internal dynamic programming (that is just a more compact way of evaluating a closed-form formula). For each player separately we compute the probability with which they score 0, 1, 2, 3 points. Knowing these, we can then iterate over all pairs of scores and compute the probability of win/draw/loss after first three questions. The potentially infinite follow-up process in case of a draw (one question each until the tie is broken) can then also be handled in constant time: if player A answers correctly with probability pA and player B with probability pB, the probability that A eventually wins is the probability that A answers correctly and B incorrectly given that there was not a tie in this round — i.e., pA(1-pB) / ( pA(1-pB) + pB(1-pA) ).

Evaluation of a team round can easily be reduced to an individual round: if we have players with probabilities p1, … , pK on a team, they are the same as an individual with probability 1 – (1-p1)…(1-pK). This is because the team will not know the answer if and only if all players do not know the answer.