For D, we did a matrix exponentiation on number of different graphs (for n=5, there were only 34 different graphs, link). However, it was still somewhat slow to raise power for every query and precomputing "power of 2" matrices was not enough. So the idea was instead of doing (A(B(CD)))v we did (A(B(C(Dv)))) which is qlogn*n^2 instead of qlogn*n^3. And that was sufficient to get AC (My teammate Bruteforceman mentioned this blog).

You can normalize each state. Then for n=5 there only remain 34 states, 13 of which are unconnected. If you know the probability distribution of states at time l, you can use matrix exponentiation to get the answer, since 14³·q·log(r - l) fits within the time limit (one extra state for 'having been in any connected state').

Unfortunately 34³·q·log(l) seems too slow to use matrix exponentiation directly for getting this probability distribution. Instead, using matrix exponentiation again, calculate the probability of exactly k edges flipping in l steps (only 11 states so it again fits within the time limit). Now iterate over the (unnormalized) state at l and using previous result it is relatively straightforward to compute the probability that this will be the state at l.

Combining these two steps got me AC in 373ms.

Generate a million binary strings and pray.

Solved by Bruteforceman. The main idea is: suppose you would like to know what is at i'th position. Then query for:

• [i, j], [i+1, j]
• [i, j+1], [i+1, j+1]
• [i, j+2], [i+1, j+2]

and so on. Say the reply to the first query is X and to the second query is Y. Now, the probability for both being valid is 1/4. Also, you may assume that if: Y = {X, X-1} then may be (X, Y) are valid. So record, X-Y. If you see number of 0 or 1 going over say 2 or 3, then you know that by high probability the answer is that number (0 or 1).

Our solution which passed stress testing:

Let's guess the second half of the string. For each ask for K values: [0, r], [1, r], ..., [K - 1, r]. For each consider multiset . Sort all pairs by decreasing of frequency of the most frequent value in .

Now we found some correct differences of some prefix sums. So go through these pairs in sorted order and join indices in DSU (like in Kruskal's algorithm) until we got components. To get remaining edges just ask for value in some positions, like in other solutions waiting for 4 evidences. Then do dfs on generated tree and find out all .

We used .

Let me summarize the solution for E. Many people are downvoting descriptions of solutions, but they are correct and I have a complete proof for it. However, various details are important in the proof and slight difference of algorithm may result in significant difference of number of queries / failure probability.

We decide letters one by one. Basically, to decide the i-th letter, we choose some j, and compute the difference of [i, j] and [i + 1, j]. For a single choice of j, it returns the correct answer with probability at least 1 / 4. So, if we repeat this for various j and get some statistics, it's likely that we get the correct value of s_i.

Suppose that s_i = 0. As we see above, for any j, the probability that we get the evidence of s_i = 0 (i.e., Query[i, j] = Query[i + 1, j]) is 1 / 4. What is the probability that we get the evidence of the opposite thing (i.e., accidentally get Query[i, j] - Query[i + 1, j] = 1)? To keep this probability small, it's important to use long intervals. When j - i ≥ 500, this probability turns out to be about 1 / 1000 (by a simple calculation). There's no such j when i is big, in this case we should use Query[j, i] - Query[j, i - 1] for some j.

Since this is probabilistic, we need to try various js. How many js should we try in particular? Imagine a lottery that gives one of "A" or "B" with probability 1 / 4, the other letter with probability 1 / 1000, and "?" in all other cases. We want to decide which of "A" and "B" is more frequent by drawing this lottery several times. One natural way is to repeat drawing the lottery until the difference between (the number of "A"s) and (the number of "B"s) becomes 3. Again, some computation shows that with this strategy, we can almost always find the correct one: the failure probability is about (1 / 250)³. (This is equivalent to Gambler's ruin. See the section "Unfair coin flipping"). Note that, another natural way is to stop when you get the same letter three times: it has a worse error probability.

If we use the strategy above for all positions, since in each position we fail with probability (1 / 250)³, the total failire probability per testcase is about 1000 * (1 / 250)³ = 1 / 15625. Thus this algorithm will get AC with about 99% probability even with 150 testcases.

What is the number of queries? Again, the detail of the choice of j matters. One possible way is to use j = 1000, 999, 998, ... when j < 500 and use j = 0, 1, 2, ... otherwise. For a single i, we draw the lottery about 12 times on average. This is because in 12 attempts the expected difference between the number of two letters is about 3. Thus, for small i, we send queries for intervals [i, 1000], [i, 999], ..., [i, 989] and for large i, we send queries for [0, i], ..., [11, i]. Note that, when we try to get s_i we use queries [i, j] and [i + 1, j], and when we try to get s_i + 1 we use queries [i + 1, j] and [i + 2, j]. We should memoize the answer for [i + 1, j] and do not ask it multiple times. In total, roughly speaking, we need 12000 queries on average. Of course, the number of attempts for a single i is not always exactly 12 because this is a probabilistic parameter. This raises the number of queries a bit, but still we are comfortable with the limit of 18000.

My code: https://ideone.com/jOqZgM

My solution for F: Let's build the sorted list of the players one by one. To find the correct position for the next player we use binary search. That gives us 1000 * log operations which is about what we need.

Now the question is how to compare two players in the binary search? We have 5 groups: higher then 1st, 1st, 2nd, 3rd, lower then 3rd. Let's take any 2 people and ask if one is lower than the other. If we have no answer then we swap them and ask again. You can see that only for (1st, 2nd) and for (1st, 3rd) that will not give you the order. For others you will have the answer and complete the binary search iteration. If during the binary search we failed to insert the element, let's save it for later.

Now in the end we have one or two saved elements and the sorted list. I iterate from the lowest to highest asking the order and that's how we can find 1st-3rd person in the list. Then insert our saved for later there in any order and just sort those 3. That is easy — ask all 6 questions and it's enough to find the order.

I liked the problem personally, really nice. Kudos to the author.

My solution: Pick a guy, let's call him zero. Ask zero about everyone, and everyone about zero. This way, you know whether zero guy is first, second, third (I call these medal guys), above first or below third. Furthermore, you know the categorisation of all the remaining guys (except that sometimes you cannot distinguish a medal guy from either above or below guys). Write quicksort to sort the above and below guys. For the medal guys, you sometimes need special handling:

• For instance, when the zero guy is above first, then all the medal guys behave the same with respect to him. Sorting the medal and below together cannot distinguish the medal guys properly, but they will be sorted as the top three in the "below" list. You just ask 6 queries, and one of them will identify second and third guy.
• If zero guy is third, you cannot distinguish second from above first, so you sort them together. The second guy will naturally end up last.
• and so on

Then it's fairly standard:

1. Waste a lot of time on implementation.
2. Get WA on test 49.
3. Randomise the selection of zero guy.
4. Get WA on test 41.
5. Realise contest ends in 5 minutes.
6. Submit the same code 10 times.
7. Get AC.

G: When deciding where to move, try the following in order (r is some value depending on your dice, described below.)

1. Move to (0, 0).
2. Move to a point from which you can reach (0, 0) with a roll of r.
3. Move directly toward (0, 0) if you're currently to far away.
4. Move away from (0, 0).

As for dice selection, there are a few possible issues

• If we get too few or too low dice, then we spend many moves doing (3).
• If we get too many dice, we spend many moves doing (2), waiting to roll r.
• If r is too small and we roll some big value, we have to do (4) instead of (2), wasting the next move.

Two dice dice selection strategies that work:

• Get four dice with an average of at least 8000 and set r to the sum of maximums. (Needs around moves to get into distance r and around 6⁴ = 1296 moves to finish which leaves some leeway for random variations.)
• Get seven dice each having a duplicate value that is at least half the maximum and set r to the sum of duplicate values. (Needs around moves to get into distance r and around 3⁷ = 2187 moves to finish. This a bit risky if you get too low dice and can be improved by rejecting dice with an average below 5000.)

(I ignored the time taken to get the dice in my analysis, should be around 1'000 for the first and 7'000 for the second strategy in total, but the influence of this is halved as we're already moving toward (0, 0) during this time.)

First the slow solution:

DP(pos, set_of_taken_digits):
ret = 0
for i < pos:
  if digit[i] == digit[pos]:
    ret += DP(i - 1, set_of_taken_digits)
if digit[pos] is not in set_of_taken_digits:
  ret += DP(pos - 1, set_of_taken_digits Union digit[pos])
return ret

If you think a bit, you will be able to optimize the solution. First of all, set_of_taken_digits is a 10 digit bitmask. So, we will store dp[i] for each 0 <= i < len(S) where dp[i] is a 2^10 length array storing dp value for each bitmasks.

To compute dp[pos], we need dp[pos-1] (for the second if) and sum of dp[i] where S[i — 1] == S[pos]. So, we only need two 2^10 array (dp of i-1, and dp of i) and 10 2^10 arrays (for each digit).