November 2011 Contest Problem Editorials

Problem Tester for the November 2011 Contest was Tolstikov Aleksey.

-------------------------------------------------------------------------------------------------------

DOMNOCUT (written by Anton Lunyov)

You can view the editorial here.

You can view the solution here:

Problem Setter's solution

-------------------------------------------------------

HAREJUMP (written by Saransh Bansal)

The question requires some Mathematics and the whole system can be seen as State Transitions. The number of ways to reach a state(X) is equal to number of ways of reaching the states which can help the rabbit reach state(X).

Hence F(x) = ∑ F(x- jump lengths)

The above recursive equation if used will result in a TLE as X can be up to 10^18. So a faster approach was required.

Matrix Exponentiation by squaring can help solve this problem. This is a very standard problem and many elite coders could solve this problem with many optimizations. For newbies who did get the recursion but could not solve the problem within Time Limit, I suggest to read about how Matrix Exponentiation can be used to solve Fibonacci problem. Refer to this link to know more

You can view the solution here:

Problem Setter's solution

Problem Tester's solution

-------------------------------------------------------

STEPAVG (written by Gennady Korotkevitch)

There are several different approaches to this problem (and the top contestants always provide a broad range of them).

The simplest of them resulting in a reasonable score is greedy. We'll try to make the set of numbers smaller and closer overall to K at the same time. To do this, take the smallest (X) and the largest (Y) number out of the remaining ones. If K is much smaller than their average (X+Y)/2, then it's reasonable to use two largest numbers for the current operation (as there are. too many large numbers at the moment). If K is much larger than their average, then use two smallest numbers (as there are too many small numbers at the moment). Finally, if K is close to their average (the exact definition of "close" may differ), then use the smallest and the largest number -- this way you replace two numbers which are far from K with one number which is close to K.

A better approach is doing the greedy in the reverse order -- that is, we don't change the given set of numbers (except removing some), but we change K. The idea is taking the smallest (X) and the largest (Y) numbers available again. If K is much smaller than (X+Y)/2, let's say that the last operation is replacing the smallest number and what we get from the remaining numbers with their average. Then it's clear that the number we should get from the remaining ones should be close to 2K-X. Similarly, if K is much larger than (X+Y)/2, then use the largest number in the last operation and try to get as close as possible to 2K-Y with the remaining numbers. Finally, if K is close to (X+Y)/2, then replace X and Y with (X+Y)/2. This kind of approach was successfully implemented by David Stolp (pieguy) for the top spot. I found the solutions of other top scorers less readable, so I'd like to ask them to share their ideas :)

And the last but not the least, I want to apologize for the tie of the top scorers. Actually, their solutions get the smallest possible score -- the differences of their results and K are less than 10^(-6). The reason they didn't get the score of 0.000000 is simple -- there exists a test case where K is less than all of Ai. In fact, making the constraint on N lower would have helped to distinguish them, but it was too late to change anything when I realized that.

You can view the solutions here:

Problem Setter's solution

Problem Tester's solution

-------------------------------------------------------

LUCKYDAY (written by Hiroto Sekido)

First, we consider the case where X, Y > 0. Let f(i) be the vector (S[i] S[i+1] 1), then there is a 3*3 matrix A such that f(i+1) = A f(i). Now, our task is calculating the number of vectors f(k) = (C m 1) satisfying L[i] <= k <= R[i], and 0 <= m < P.

The sequence f has a period r (at most P^2), since A is a regular matrix. That is f(k+r) = f(k), for all k >= 1.

The first part of solving the problem is calculating a period r and integers k which satisfy f(k) = (C m 1) for each m. Finding minimum k such that f(k+1) = f(1) is enough to calculate a period r. Therefore, we should search P+1 vectors in the sequence f, and it can be calculated by using baby-step-giant-step. At first, calculate the vectors A^d f(1) for 0 <= d < L, and store the vectors. For finding a vector v, we calculate (A^L)^e v for 0 <= e < r/L, and search these vectors in the set of all vectors A^d f(1). The precalculation takes O(L) time, and finding a vector in the sequence takes O(r/L) time if hashes are used for searching. Here, let's set L = P^1.5, then this part takes O(P^1.5) + (P+1) * O(P^2 / P^1.5) = O(P^1.5) time.

The second part is calculating the answer for each intervals. It can be calculated by using binary search. It takes O(Q log P) time.

If X and/or Y are 0, above algorithm cannot be applied, because the matrix A may be singular. However, these cases are not so difficult. A similar method can be used for the case X > 0 or Y > 0, and the problem becomes trivial for the case X = Y = 0.

You can view the solution here:

Problem Setter's solution

-------------------------------------------------------

NEWREST (written by Ashar Fuadi)

This problem is to be solved using dynamic programming approach plus some combinatorics.

First, define dp[i][j] as the number of ways to cook exactly j different types of dish for i days. As the base case, it is obvious that dp[0][0] = 1, dp[0][x] = 0 for x > 0.

Suppose we know the value of dp[i][j] for some pair (i, j). Now, consider the (i+1)th day. There are two options for us:

• Cook a dish which has been cooked before. There are j types of such dishes. We can update dp[i+1][j]:
  dp[i+1][j] += j * dp[i][j]
• Cook a new type of dish. Note that we don't care which type of dish it is; we only care that its type is different from all j types. We can update dp[i+1][j+1]:
  dp[i+1][j+1] += dp[i][j]

After that, we'll take the actual types of dish into account. There are M available types of dish. There are P(M, j) ways to choose j types from M types (the order is important). So, the number of ways to cook exactly j different types of dish for i days is P(M, j) * dp[i][j] = (M! / (M-j)!) * dp[i][j] = M! * (M-j)!^-1 * dp[i][j]. Of course, all calculations are performed modulo MOD = 1000000007.

We can precompute all values of k! for all 1 ≤ k ≤ M. The value of k!^-1 (mod MOD) can be calculated using Euler's Theorem: k!^-1 = k!^MOD-2 (mod MOD). Also, the DP values can be computed only once for all T test cases.

Since the original problem asks for the number of ways to cook at most K different types of dish in N days, the final answer is: sum {M! * (M-j)!^-1 * dp[N][j]} for all 1 ≤ j ≤ min(M, K).

The complexity of this solution is O(N(M+K) + M log MOD + T(M+K)).

You can view the solutions here:

Problem Setter's solution

Problem Tester's solution

-------------------------------------------------------

POSTAL (written by Anirban Mitra)

Notice the following 2 observations

1. The postmen can be considered as if they are passing through each other

2. The relative position of a postman never changes

Using the first we can calculate the final positions by just adding or subtracting the time from the initial positions depending on the direction being South or North. Combining this with 2, we can easily see that if we sort the final positions, we will get the position of the the respective postman. But we also have to calculate the collisions. For that we can do the sorting of the positions using Bubble Sort where each swapping of adjacent numbers in the array means a collision. And, hence we can easily count the same.

You can view the solutions here:

Problem Setter's solution

Problem Tester's solution

-------------------------------------------------------