Below is very short description of solutions to problem that I can solve. Because it is "short description", for most problems, there is no proof of correctness. Proving the solutions is up to you.

100541A - Stock Market

This is the most simple problem in the set.

Observations:

• If you buy stock, you're better to buy as much as possible.
• If you buy stock on the i-th day, then you will always sell every stock on some j-th day, where j > i and the price of the stock on the j-th day is maximal.

Now we have an algorithm that runs in time O(N):

• Initialize f(i) to be the maximum value of the stock price from i-th day to N-th day.
• For each value of i from 1 to N, try to buy stock on i-th day, and find the value that you will sell these stocks using f(i+1).

100541B - Sum

Observation:

• There's only small number of different values of [N/i]. In fact, we can prove that there's only O(sqrt(N)) different values:

Using the above observation, we have a O(sqrt(N)) algorithm:

i = 1
result = 0
while i <= N:
    value = N / i
    last = N / value    // This is the last value such that (N / last) still equals to (N / i)
    result += (last - i + 1) * value
    i = last + 1
print result

100541C - ATM withdrawal

First, there's no solution when N mod 1000 > 0. After dealing with this, we can divide N by 1000.

Obvious (and wrong) greedy solution:

• Let u = N mod 10. Using notes 1, 2, 3, 5, pay u.
• Divide N by 10
• Repeat the above 2 steps for c+1 times.
• For the remaining values, pay using 5*10^c.

This greedy is wrong with the following test: N = 110 (after dividing by 1000), and c = 1. It calculate the number of ways to pay N value incorrectly. (correct answer is 2: 110 = 50 + 30 + 30 = 50 + 50 + 10, while the greedy will find 1).

But we can fix this greedy solution:

• Let t = the note with maximum value. Before applying the above greedy, we pay X notes with value t, where X = (N — t) / t.

100541D - Treasure Box

Observation:

• After at most 100 transformations, X mod 100 will become some value that we already seen.

In other words, the sequences of transformation will look like this:

 + a₁ + a₂... + a_i + b₁ + b₂... + b_k + b₁ + b₂... + b_k + b₁ + b₂... + b_k + ...

So we can group b₁, b₂, ..., b_k together, and calculate the result in O(k).

100541E - ACM

Observation:

• There is only small number of primes (36 primes) below 150.

Algorithm:

• Build 36 segment trees. Each node in the k-th segment tree stores the power of the k-th prime in the product of in the corresponding segment.
• Using the segment trees, we can update / query for each prime in time O(log(N)).

Traps:

• You must use long long
• MOD can be equal to 1

100541H - Pencil Game

Let i, j be the first and last column of the result sub-rectangle. Let u, v be the first and last row of the result sub-rectangle.

By using basic algebraic transformations, we have:

2 * L = (j - i + 1) * (v - u + 1) * (N * (u + v) + (i + j))

Let W = j - i + 1 and H = v - u + 1. Note that W * H is our solution.

Because the number of factors of an integer is small, we can loop through all possible values of W and H (first generate all factors of L, then consider only the factors of L). For each pair (W, H), we can uniquely find u and i, and check if it is indeed a valid solution.

100541I - Space Tour

This is a dynamic programming problem. Note that the 4 different paths do not have a common point, so we can consider them separatedly. Use 4 different dp functions to calculate the length of each 4 path.

For example, the path that initially go to left direction can be calculated this way:

for i = 1..M:
    for j = 1..N:
        if a[i][j] == 1:
            f[i][j] = 1
            if a[i-1][j] == 1:
               f[i][j] = f[i-1][j-1] + 2

After calculating the 4 dp functions, we can loop through each starting position (i, j) and calculate the result if we start at this position.

100541J - Math Magic

This is another dynamic programming problem.

Let f(i, x, y, z, t) be the maximum score you can get if you used some tiles 1..i, and the colors at the four directions are x, y, z, t.

From f(i, x, y, z, t), you can calculate all values of f(i + 1, x', y', z', t') by trying all possibilities of adding the (i + 1) - th tile to one of the four directions.

This solution is a bit slow to get accepted. You can try following optimizations:

• Only consider reachable states (i, x, y, z, t).
• Only consider states where x <= y <= z <= t.

Traps:

• Result can be negative