104A - Blackjack

Determine the result based on each value of n carefully.

104B - Testing Pants for Sadness

We use a[1], a[2], ..., a[n] to denote the given n values. To achieve the maximum number of clicks, it is obvious that we should first choose a[i] - 1 wrong answers and then select the correct one, for every i. For a[i], we have a[i] - 1 wrong answers, and thus we start from 1 to i - 1 for a[i] - 1 times, which gives (a[i] - 1) × (i - 1) clicks. Also remember that i contributes a[i] clicks, and this gives totally (a[i] - 1) × (i - 1) + a[i] clicks before we move to index i + 1. Therefore, we enumerate all the elements, and add the answers together.

104C - Cthulhu

Let us consider what form can such a graph have. There are n nodes and only one circle. This implies that we must have n edges as well, i.e., m = n. Next, after deleting some single edge, we will surely obtain a connected tree. Therefore, we can adopt a double loop to check if we can obtain a connected tree by eliminating some edge. The connectivity can be simply checked by using Union-Find.

I also find that it is sufficient to just check whether the original graph is connected or not, which can reduce the double loop to a single loop.

104D - Russian Roulette

We first consider the case where n is an even integer, and there is only one bullet. It can be seen that all the positions can be divided into two types, even indices and odd indices. The probability of winning is always 0.5 no matter at which type we put the bullet. Now suppose that we have two bullets. One can check that if both two bullets are put at the same type, the winning probability is still 0.5; otherwise, the winning probability is decreased. Thus, we should put the two bullets at the same type. Extending this to a general approach, we should put bullets at the even indices until all the even indices have been used up, and then put them at the odd indices. To achieve the minimum lexicographical order, we should implement the above operations from right to left.

Now we deal with the case where n is an odd integer. For one bullet, we can put it at any position, which always gives a winning probability of . When there are two bullets, the second one should be put at a position with even index so that the winning probability is not decreased. For more bullets, the strategy is similar as the case where n is even. In a word, when n is an odd integer, we should put the first bullet at position n. Then, we put the other bullets at positions n - 1, n - 3, n - 5, ..., 4, 2, n - 2, n - 4, ..., 5, 3, 1.

104E - Time to Raid Cowavans

This is a very very tricky problem.

If we answer the query by exhaustive calculation, the complexity is O(qN). However, note that if all queries have , the complexity is reduced to . On the other hand, if all the queries have , we can previously use DP algorithm to compute the results for all the potential values of b, resulting in a complexity of .

Based on the above observations, we can select one of the two algorithms according to the value of b. We sort the queries in the increasing order of b. For , we use DP algorithm with complexity O(N) to calculate the desired result; otherwise we directly compute the sum. The former operation may be implemented for at most times, which gives complexity while the latter one might be implemented for at most times, which gives complexity . Therefore, the total complexity has been reduced to .