268A - Games

With only 30 teams, the simplest solution is simulating all the matches:

for i = 1 to N
  for j = 1 to N
    if i != j and h[i] = a[j] then
      ++ans

An O(N + M) solution is also possible, where M is the length of colors' range (i.e. 100 under the given constraints). First, you need to count for each color i the number of teams cntH[i] which have the home uniform of color i and the number of teams cntA[i] which have the away uniform of color i. The answer is the sum of products of these quantities for each color, i.e. sum of cntH[i] * cntA[i] over all i.

268B - Buttons

Let us first detect the worst case scenario. It is more or less apparent that when Manao tries to guess the i-th (1 <= i <= n) button in order, he will make n-i mistakes in the worst case. After that the correct button is evident.

Now let's count the total number of presses Manao might need before he guesses the whole sequence. When he is guessing the first button he makes n-1 mistakes, but the "mistake cost", i.e. the number of presses before the mistake is made, is equal to 1. When Manao goes for the second button, the mistake cost becomes 2, because each time Manao needs to press the first (already guessed) button. Continuing like this, we obtain that when Manao tries to guess the i-th button in order, he will perform (n-i) * i button presses.

After Manao guessed the correct sequence, he needs to enter it once, which is another n presses.

So we already have an O(n) algorithm: sum up (n-i)*i for i=1, ..., n-1 and add n to the sum obtained.

When n is anything that fits in 32-bit integer type, the task is solvable in O(1)*. The sum (n-i)*i is two separate sums: the sum of n*i and the sum of i*i. The first sum is n*(1+...+n-1), which can be computed with the sum of arithmetic progression. The second sum is the sum of squares from 1 to n-1, which can be evaluated with a polynom of degree 3: http://pirate.shu.edu/~wachsmut/ira/infinity/answers/sm_sq_cb.html

*The only problem is that the answer for large n-s does not fit even in 64-bit integer type, but at least we can compute its remainder from division by anything.

268C - Beautiful Sets of Points

Obviously, if a set contains a point (x', y'), it can not contain any other point with x=x' or y=y', because these two points would be an integer distance apart. There are only n+1 distinct x-coordinates and m+1 distinct y-coordinates. Therefore, the size of the set sought can not exceed min(n, m) + 1.

If the constraint x+y>0 was not present, the set of points (i, i) (0 <= i <= min(n, m)) would do nicely. The distance between two points (i, i) and (j, j) is equal to |i-j|*sqrt(2) and can only be integer when i=j. On the other hand, there are min(n, m) + 1 points and we already know that we can't take more than that.

Since point (0, 0) is restricted, we can take the other "diagonal", i.e. use points (i, min(n, m) - i).

268D - Wall Bars

Those who are well experienced at dynamic programming can scroll down to "Overall solution" right away. Those who have some experience in DPs can read my attempt to explain how you can come up with that solution. Those with no experience probably shouldn't read this at all :)

Imagine a solution which considers all possible designs, adding the bar-steps one by one. Consider any sequence, like 2123412413. There are 4 ways to continue this sequence by appending '1', '2', '3' or '4' to it. For each of the 4^n wall bars / strings we need to check that for at least one of {'1', '2', '3', '4'} character the following is true: its first entry in the string is at position no more than h, each next one differs from the previous by no more than h and the last one is beyond position n-h.

Surely, such a solution won't work for large n-s in any reasonable time, but we can start from it in the search of a better approach. First, let's note that we can check the feasibility of the string after each character addition: if somewhere in the middle of string we noticed that for each of the characters the necessary conditions are broken, there is no reason to complete the string. Also, note that we don't need the whole prefix to check the validity of the conditions after each character addition. All we need to know is when each of the '1', '2', '3' and '4' characters occured last, and whether the conditions for each of the characters have been fulfilled up to this point. It turns out that two prefixes in which [each of the characters last occured at the same position] and [the validity of the conditions for each character are equal], are absolutely equivalent for the brute force algorithm's further operation. That is, for example for h=4 these two prefixes can be completed (up to length n) in the same number of ways:

44123424132
12424224132

The last time each of the characters have occured at the same positions, characters '1' and '3' are already "lost" (the conditions are already broken for them), characters '2' and '4' can still turn the string into a valid one.

With the help of the observations made, we can already build a polynomial-time algorithm based on dynamic programming principle. Let ways[curN][i][j][k][l][ii][jj][kk][ll] be the number of designs of height curN, where the last step in direction 1 was at height i, the last step in direction 2 — at height j and so on; ii, jj, kk, ll are boolean parameters which indicate whether the conditions are valid in the corresponding direction. When we choose the direction for the step at height curN+1, we obtain a design with curN+1 steps, the last step in the direction we chose is now at height curN+1 and rest stay where they were. Conditions validity can also be reassessed. Since curN is always one of {i, j, k, l}, we can obtain a O(n^4) algorithm. However, this is still too slow.

Another observation: if we are looking at a bar at height curN and the last step in this direction was earlier than curN-h steps ago, we don't really care which height was it exactly at, since this direction is not valid any more. Therefore, the number of states in our algorithm can be only O(n*h^3). Moreover, those ii,jj,kk,ll parameters correlate with the heights of the latest steps in the corresponding directions, so we can (almost) get rid of them, thus reducing the number of states in a number of times.

On the base of these observations we can probably build different solutions. I will tell mine.

Overall solution

We will keep a 5-dimensional DP :) Let ways[curN][alive][last1][last2][last3] be the number of designs where:

• There are exactly curN steps.

• If the direction of the latest step if still "alive", then alive = 1, otherwise it's equal to 0. A direction is alive if its first step was not higher than h and each subsequent one was higher than the previous by at most distance h.

• last1, last2 and last3 keep the information about the other directions in any order. lasti can be zero in two cases: if there were no steps in the corresponding direction, or if the latest one was earlier than h steps before. Otherwise, lasti is the number of steps between the current step and the latest step in the corresponding direction.

We can optimize by keeping last1<=last2<=last3, which reduces the number of states in roughly 6 times. However, this complicates the code and doesn't have a significant effect (since the transitions processing becomes costly). Thus I will not consider it at all.

What transitions can be made from state [curN][alive][last1][last2][last3]? We shall process the states in order from curN=1 to curN=N-1. ways[1][1][0][0][0] (i.e. a single step) is equal to 4 as a base case. So we have:

• If we add a step in the same direction as the latest (i.e. the one at height curN), then we obtain state [curN+1][alive][last1+1][last2+1][last3+1] (roughly): curN has increased by 1; the "livingness" of the direction of the last step could not change; all the lasti-s have increased by 1. However, note that for lasti=0 it should not be incremented (the corresponding step either does not exist at all, or is way below). Also, for lasti=h-1 it turns to zero (the last step is now too low).

• If we put the step in the same direction as the one which was at height last1, we obtain state [curN+1][last1 > 0 || curN < h][alive][last2+1][last3+1]. This decyphers in the following way: if last1>0, then this condition is alive. last1 could also be 0, but the number of already built steps less than h — in which case this is the first step and the direction becomes alive by putting it. The direction denoted by last1 has been replaced (in the state parameters) by the one in which the curN-th step was sticked out. Therefore, it was 1 step ago and we should write [1] there. On the other hand, that direction could already be dead and we would need to write [0]. It turns out that the value coincides with value of alive. last2 and last3 change in the same way as in the previous case.

• Directions last2 and last3 are treated in the same way as last1.

When we process a transition, the number of designs corresponding to the new state increments by ways[curN][alive][last1][last2][last3]. So the overall answer is sum of all [n][1][a][b][c], where 0<=a,b,c<h plus sum of all [n][0][a][b][c], where at least one of a, b, c is non-zero. So we have an algorithm of O(n*h^3) complexity which needs asymptotically the same amount of memory. Its implementation could catch ML (especially on Java). This can be handled through the following observation: since we only need values [i-1][][][][] to compute [i][][][][]-s, only O(h^3) states need to be kept at any given moment.

Well, before writing this analysis I didn't realize it was so huge :)

You can check SteamTurbine's solution at 3027309 for a very compact implementation of a similar idea.

268E - Playlist

Let us first find the answer for a fixed sequence of songs. Consider any two songs which are at positions i and j (i < j) in the playlist. If Manao liked song i and disliked song j, then song i will be listened to again. Therefore, with probability p[i]*(1-p[j]) the process length will increase by L[i]. The sum of L[i]*p[i]*(1-p[j]) over all pairs (plus the length of all songs since Manao listens to them at least once) is the expected length for the fixed sequence.

So we have that if there are two songs (l1, p1) and (l2, p2), the first one should be placed earlier in the playlist if l1*p1*(1-p2)>l2*p2*(1-p1) and later otherwise. This is obviously true if there are only two songs. But suppose that we have more and you ask, why can't there be another song (l3, p3) such that the above inequality rules out that the first song should be after this one and the second song should be before it? Then it's unclear which of the orders results in the maximum expected value. Consider this case in details:

l1*p1*(1-p2)>l2*p2*(1-p1)
l1*p1*(1-p3)<l3*p3*(1-p1)
l2*p2*(1-p3)>l3*p3*(1-p2)
<=>
l1*p1/(1-p1)>l2*p2/(1-p2)
l1*p1/(1-p1)<l3*p3/(1-p3)
l2*p2/(1-p2)>l3*p3/(1-p3)

(this is not quite true if any pi is equal to 0 or 1, but that's not important here)

We have a contradicting system of inequations, so such a case is impossible.

Next, let's consider some order of songs (l[1], p[1]), ..., (l[n], p[n]), in which there is a pair of neighbouring songs i and i+1, for which the condition l[i] * p[i] * (1 - p[i + 1]) >= l[i + 1] * p[i + 1] * (1 - p[i]) does not hold, and assume that this order is optimal. Evidently, if we interchange songs i and i+1, the answer will only change by the value contributed by this pair (i.e. l[i] * p[i] * (1 - p[i + 1])). The rest of the songs keep their order towards song i and song i+1. But l[i] * p[i] * (1 - p[i + 1]) < l[i + 1] * p[i + 1] * (1 - p[i]), therefore if we put song i+1 before song i, we obtain a larger value. So we have a contradiction — the order chosen is not optimal.

So it turns out that the permutation with maximum possible expected value is obtained when sorting the songs in decreasing order of l[i]*p[i]/(1-p[i]). But we still have a problem of computing the answer for a fixed permutation: we only learned how to do this in O(n^2), which is too slow with n=50000. We can use an idea which is probably a yet another dynamic programming example. Suppose we have fixed j and are counting the contribution of song j towards the answer if Manao dislikes it. This value is (l1*p1 + l2*p2 + ... + l[j-1]*p[j-1]). For j+1, the corresponding value will be (l1*p1+...+l[j-1]*p[j-1]+l[j]*p[j]). It turns out that these values differ in only a single summand, so we can compute each of them in O(1) if we consider j-th one by one in increasing order. This idea can be expressed as follows:

lovedLenExp = 0.
answerExp = 0.
for j = 1 to N
  answerExp += l[j]
  answerExp += lovedLenExp * (1 - p[j])
  lovedLenExp += l[j] * p[j]

That's all :)