100506A - Average distance

For this problem, you need to calculate:

sum(distance(u, v)) / (some_constant)

How to calculte sum(distance(u, v)) efficiently? Obviously, you cannot iterate through all pair of vertices u and v. That would take at least O(N²).

When calculating the sum, notice that you need to add one edge multiple times. There are only N edges, but for each edge, in naive solution, you added it multiple times. So now you can see an idea for optimizing the naive solution: For each edge, count how many times it appear in sum(distance(u, v)) and add it to result.

Turns out this is quite simple: For edge (u, v) where u is parent of v in the tree, the path going through it must have the form: "something --> u --> v --> something". The number of such path is size(subtree(v)) * (n - subtree(v)).

My code 100506B - Bus Pass

Let's call the vertices which at least one bus trip go through "important vertices". It is easy to see that there are at most 200 important vertices (10 trips * 20 each).

So for each important vertex, you can do BFS to calculate the distance to every other vertices. --> You get all distance from every vertex to each important vertex. Using this information, it is quite simple to get the result.

My code

100506C - Cutting Banknotes

First let's get rid of floating numbers by multiply everything with 100. Now, because dividing the notes by 2 is always better, split each note until you cannot (e.g. for note with value 2.00, multiply it by 100 --> 200, and then split it to 100, then 50, then 25. For note with value 3.00, multiply it by 100 --> 300, and then split it to 150, then 75). After doing this, the problem becomes, given a set of notes, check if you can use these notes to make certain sum (note that you can subtract). In math, this is check if an integer S can be represented as:

x₁ * c₁ + x₂ * c₂ + ...

for some constants c₁, c₂, ...

Now this is application of congruence equation, which to check if there is a solution, you just need to check if everything is divisible by gcd.

My code

100506D - Dice Password Security

This is a dynamic programming problem.

Let f(i, j) =  number of ways to use exactly N words to get a string of length j.

Then, to calculate f(i, j), consider all word that can be added next --> you can use f(i, j) to update f(i + 1, l + a(x)), with a(x) =  some string length

My code

100506E - Lingo

This problem requires inclusion exclusion principle.

The basic idea is to loop through all subsets and calculate the necessary probabilities.

My code

100506F - Splitting the Loot

Let's say you're given N gold bar of weight a₁, a₂, ..., a_N. What is the smallest weight that you need?

Interestingly, this is a well known problem: Huffman encoding. To solve it, you just need to use the following greedy: take 2 smallest bar, merge them into one. Repeat until you have only 1 gold bar left. The length of this gold bar is the result.

Now you have a way to check if you can divide the given gold to a₁, a₂, ..., a_N. You can easily take care of  - 1 case. But how to find answer in other case? You can use Binary search! Let's say you want to check if you can keep X gram. You just need to run the above algorithm to check if you can divide the initial gold bar to X, a₁, a₂, ..., a_N.

My code

100506G - Pachinko

This is another DP problem. The idea is, for each column, calculate: If you drop the ball at this column, what is the probability that it ends up in every cell.

The formula is straight-forward:

Let f(i, j) =  probability that the ball goes to cell (i, j). Then if cell (i, j) is empty, then from cell (i, j), the ball can only go to below cell (i + 1, j). Thus, we update f(i + 1, j) +  = f(i, j). If that cell is '*', then the ball can go to 2 diagonal adjacent cells of the next row, thus we update f(i + 1, j - 1) +  = f(i, j) and f(i + 1, j + 1) +  = f(i, j)

My code

100506H - Hiking

I haven't solved it. But here's a solution by qwerty787788 :

"Let's create a set of interesting points. We add to this set start and end points. Also let's consider all pairs of towers. Let's look at intersection points of two circles with centers in this towers. If such point isn't covered by any other circle, we add it to our set.

Now for each pair of points in set we should find if we can go directly between them. So we just intersect this segment with all circles and look if all points in this segment is covered by at least one circle.

And now we can use dijkstra on this points to find a shortest distance."

100506I - Ranking

This is an implementation problem. You just need to implement everything that is said on the problem statement. The trick is in the sentence: "If ties remain at the end of the contest, the point of comparison between tied teams will be the last point in time where their scores differed".

My code

100506J - Stock

For this problem, you need to solve it bottom up. Thus we go from the last day until day 1. Let use the example input to illustrate:

At day 6, you can sell 3 stock at price 3. And you receive 2 stocks. If you don't do anything with these stocks, you will have to throw them away. So selling them is the best option. So you sell 2 stocks, receive 6 money and can still sell 1 stock at price 3 in day 6. Total money = 6. And can sell 1 stock at day 6.

At day 5, you can sell 2 stock at price 2. And you receive 2 more stocks. Using the same logic as previously, you must sell these stocks. The best way is to sell 1 stock at day 6 for 3 money, and sell 1 stock at day 5 for 2 money. Total money = 11, and can sell 1 stock at day 5. ...

Now the solution should be quite clear: Going from the last day to first day. At each day, try to sell all stock. When you sell, always sell at the highest price that you can. You can keep track of the price that you can sell using C++ set. Please refer to my code for more details.

My code