same to me.

For a string to be uncertain, letters in different positions in the original string have to match in the final string. If the letters are more than K apart, you don't have enough deletions to make them match. So, based on this, if there are two equal letters at most K apart, such as

axxxxxa

You can delete all of the Xs and one A; there is no way to tell if you left the first a or the second a. If there are no equal letters at most K apart, return Certain.

How to solve it?

You look from the most significant bit to the least significant bit and ask. If I flip this bit will it be better or worse? and if it's better to switch you switch, if it's worse you don't and go to the next bit.

We'll treat each bit separately.

First, note that at a bit k, if A[i] and A[j] differ in any bit above k, then the answer is already determined by the higher order bits. So, we only care about A[i] and A[j] being the same above k bits. Thus, it's easy to count the number of good pairs if we flip or not flip (using a map or something) by doing a linear scan through A.

My Div1 Medium failed system tests, and after testing it in the room it has about ~60% probability of passing :(.

Note that splitting each single sequence decrements K by one. Meaning, if you split all your sequences in one move, your K will be decremented by the number of sequences that you have.

{45} -> {10, 35} -> {9, 9, 26} -> {8, 8, 8, 18} -> {7, 7, 7, 7, 11} -> {6, 6, 6, 6, 6, 5} -> ...

Lol, 34 hours is a very little amount of time to prepare 6 problems :d. What do you exactly mean by "preparing"? Did you really wrote 6 statements, 6 model solutions, 6 test sets in one day :o?

And aren't TC admins afraid that someone will someday fail to prepare everything in time? Do they have some spare problems?

Haha, exactly my thoughts, I have been staring at this code for 5-10 minutes, read it twenty times and of course unsuccessfully tried to challenge it with example test and I still don't know why it gives "Certain" :d.

s.size() returns a size_t, which is unsigned, So i think it will be compared with the unsigned version of n-1 which is a very large number.
He is lucky

OK, Marcin_smu told me that this is because of unsigneds — I considered this during challenge phase, but thought that unsigned + int is int :/. Is it a rule that uint + int = uint or is it an undefined behaviour or something like that?

At each move, you can do different things to each sequence. At this stage, the example splits the 2 sequence, and subtracts the 1 sequence by one.

Question 1: I think that memoization is easier to code and understand, and still fast enough.

Q2: Actual clock running times depend on hardware, but I have an idea of what could be the cause. Are you using a testing plug-in that downloads the sample cases and tests your code against them, all in one run? If so, you may be recomputing dp(100,100) once per each test case.