100534A - Abnormal Coins

This problem is the easiest amongst the problems. Since you need to choose different polygon types, the optimal way (meaning you would spend minimum amount of coins) is choosing polygon with sizes 3, 4, 5, 6, ... in this increasing order.

Code 100534B - Fake Coins

Since the length of the string is at most 1000, you can loop through all generated code. This can be done by looping through the first and second index of the code.

How to check if two code are equal? One way to do this is to use polynomial hash. For each code, you need to calculate its hash value, which can be done by using simple DP:

Let Hash(i, j) be polynomial hash of string starts at indices i and j, then:

Hash(i, j) = s(i) + Hash(j, i + j) * BASE

After calculating all the hashes, you only need to count how many different hashes are there.

Code

100534C - Coin Graph

Let f(a, b) = the length of the shortest path between a and b.

Let W(G) = total f(a, b) for all pairs of a, b.

In this type of problem, you should find a simple type of graph G, such that W(G) can be calculated easily, and from G, you can generate G' such that W(G') = W(G) + 1 or W(G') = W(G) - 1.

By trial and error, I found that Star graph has this property. A star graph with N vertices has W(G) = (N - 1)², and you can reduce this by one simply by adding 1 edge between the 1-degree vertices. Though there are some special cases when W(G) is small, and you should handle these carefully.

Code

100534D - Coin Table

First, let's not worry about counting the number of paths. After we know how to find maximum number of coins in our path, it will be very simple to count number of paths.

Consider the following figure: We need to go from (1, 1) to (M, N), and you must not go through red cells. This will be equivalent to you must go through green cells.

So now, to answer each query, you can loop through each green cell, and count the maximum number of coins you can have, if your path go through this cell. This can be solved using simple DP.

Code

100534E - Volleyball

This is just an implementation problem, though there are too many details, which make it very hard to code in contest time. :)

100534F - Huge Table

100534G - Coin Game

There are two possibilities: either you move all 1-coins to the left, or you move all 2-coins to the left. Let's say you want to move all 1-coins to the left. For each 1-coin, you will need to swap it with all the 2-coins that lies to the left of it. So, the total cost is the sum of (number of 2-coins to the left) for each 1-coin. This can be calculated in O(N).

Code

100534H - Dreams Were Important Too!

Let call the three edges of the triangle a, b, c.

Let p = P / 2 = (a + b + c) / 2.

Consider all values of a and b (using 2 loops :) ). Since you know P, you can calculate c. And you can check if the area of the triangle satisfies using the formula:

S = sqrt(p * (p - a) * (p - b) * (p - c).

Now, we know all the sides of the triangle. The only thing left is to find its coordinate. Obviously, you can translate the triangle, so that one vertex is at (0, 0). Let the other two vertices be (x1, y1) and (x2, y2). We know that:

a = sqrt(x1 * x1 + y1 * y1)

b = sqrt(x2 * x2 + y2 * y2)

c = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))

To find x1, y1, x2, y2, you can generate all Pythagorean triples. Before looping through values of a and b, generate all triplets x * x + y * y = z * z where z ≤ 10⁴.

This solution is hard to run in time. To solve it, you need to make some optimization, for example:

• p - a must be divisor of S * S / p. This can be proven using the area formula stated above.

• Only consider a satisfying: a < p / 2.

Code

100534I - Coin Robbery

In this problem, you are given a graph G, and you need to find the minimum number of vertex you need to 'block', so that the shortest path from 0 to N - 1 increases.

First, ignore all edges that is not on any shortest path from 0 to N - 1. Now the problem becomes, given a graph G, find minimum number of vertices to block, so that the graph is no longer connected. This can be solved using Max flow.

Code

100534J - Bimetallic coins

In this problem, you are given M = N * (N - 1) / 2 alloys. For each alloy, you know the thermal coefficient, the cost if it is inner or outer of the coin. Obviously, you can create M / 2 coins from these alloys. Now you should calculate the minimum cost. Sort the alloys in increasing order of thermal coefficient. Since you know that all the thermal coefficients are different, and an alloy with smaller thermal coefficient can only be placed outside, the problem can be solved by the following DP:

f(i, j) =  minimum cost if you considered first i alloys. There are still j alloys which are outer, but you have not find the alloy to be inner.

To calculate f(i, j), note that from a state (i, j), you can only make the following transitions:

• Use alloy (i + 1) as outer. Then you will go to state (i + 1, j + 1).
• Use alloy (i + 1) as inner. The outer alloy must be before (i + 1), and still not have inner alloy. So you go to state (i + 1, j - 1).

There is still one thing to take care of: when M is odd, you must ignore 1 alloy. This can be done by adding 1 more dimension to the above DP function.

Code