*n*as strings in base

*k*(assuming we have characters for all digits between 0 and

*k*-1). Now we sort those strings lexicographically, for example the first few would typically be 1, 10 (=

*k*), 100 (=

*k*

^{2}), ... How many numbers are in the same position in this sorted order as in the order where we just sort by number?

*n*and

*k*are up to 10

^{18}, and you have to solve 1000 testcases in 3 seconds.

*n*people are standing in a row, each with either a red or a blue hat on. Each person can see the hat colors of the people in front of them (with smaller position numbers), but not their own hat color or the hat colors of the people behind them. Each person also knows the total number of red and blue hats. Then, the following process happens in rounds: in one round, every person who can already deduce their hat color, declare that they have done so (they do not declare the color itself). If multiple people can deduce it in the same round, they declare it simultaneously without hearing each other first. In the next round, on the other hand, people can already use the information of who has declared in the previous round to potentally make additional deductions themselves. Which people will eventually declare, and which will still be in the dark about their hat color even after an large number of rounds?

*n*,

*r*) possible sequences of hat colors, where

*r*is the globally known number of red hats. After the

*i*-th round, from the point of view of the first person who does not see any hats, some of those sequences are still possible, and some are not (in other words, if the hats did in fact correspond to this sequence, would everybody say what they have said?). This set of possible sequences

*S*also clearly defines what all other people are thinking: for each person, the set of possible sequences that is possible from their point of view is equal to the intersection of

_{i}*S*with the set of sequences that have the correct hat colors for those hats that they see. This sounds trivial when spelled out, but it was actually not that easy to state it for me during the round.

_{i}*i*-th round? They will look at the set of sequences that are still possible from their point of view (given by the intersection mentioned above), and check if their hat color is the same in all of them. If yes, they will declare, otherwise they won't.

*S*given

_{i}*S*

_{i-1}and the declarations? We need to check the declarations that would have happened for each sequence in

*S*

_{i-1}(assuming each person sees some prefix of that sequence), and remove those sequences where this set of declarations does not match one for the real sequence of hats. Once again, this looks very simple, almost trivial, but it was actually far from easy to state concisely.

*S*can be described by the lists of possible amounts of red hats in each of the prefixes of the sequence. For example, suppose there are 4 red and 3 blue hats in total. The initial set

_{i }*S*

_{0 }can then be described as: empty prefix has 0 red hats; the prefix of length 1 has 0 or 1 red hats; 2 has 0, 1, 2; 3 has 0, 1, 2, 3; 4 has 1, 2, 3, 4; 5 has 2, 3, 4; 6 has 3, 4; and the whole sequence has 4. Every sequence that has 4 red and 3 blue hats satisfies those constraints, and every sequence that satisfies those constraints has 4 red and 3 blue hats.

*S*can then be described as: empty prefix has 0 red; 1 has 0, 1; 2 has 0, 1, 2; 3 has 1, 2, 3; 4 has 2, 3; 5 has 2, 4; 6 has 3, 4; 7 has 4.

_{1 }*i*having

*j*red hats as (

*i*,

*j*), then the (

*i*+1)-th person will declare if exactly one of (

*i*+1,

*j*) and (

*i*+1,

*j*+1) is still possible, and not declare if both are possible. This criterion allows us to compute the declarations that actually happen, and the same criterion then allows us to eliminate states which contradict those declarations. However, we also need to pay attention to also eliminate states that do not have a possible predecessor (if both (

*i*-1,

*j*-1) and (

*i*-1,

*j*) are eliminated, then (

*i*,

*j*) should be eliminated as well), or a possible successor (if both (

*i*+1,

*j*) and (

*i*+1,

*j*+1) are eliminated, then (

*i*,

*j*) should be eliminated as well). This criterion is also the basis of the inductive proof that

*S*can always be represented in the above form.

_{i}*i*,

*j*) that are still possible after each round, and stop when this set of states stops changing.