Solutions: Team Practice 2

Problem C - Multiplication Game

• We can use Eratosthese’s Sieve to factorize the numbers in $O(\log{n})$.

• Note: There are only 4792 primes below $\sqrt{2^{31}-1}$

Problem D - Polyline Simplification

• Calculate the area of triangle using $\frac{1}{2} \left|\begin{vmatrix} x_1 & y_1 & 1\\ x_2 & y_2 & 1\\ x_3 & y_3 & 1\\ \end{vmatrix}\right|$

• To use Heron’s formula, you should square root each factor before multipling them together.

• Sort all pairs of $(area, p_{middle})$, and put them into a set (using binary tree).

• Maintain a list (or double linked list) of adjacent triangles.

• In each step, find the smallest triangle, and two adjacent triangles.

• Remove the middle (smallest) triangle from the set, and modify two adjacent triangles.

Problem I - Initials

• Construct DAG graph

• Use dynamic programming to find the optimum path.

Problem J - Particle Collision

• Simulation & Computational Geometry

• Need a good Geometry template.

Problem F - Flow Free

• Observation: Complete searchable because the number of possible path is limited, and each square can only has 3 to 4 colors.

Problem B - Open-Pit Mining

• Tag: minimum cut / maximum flow

• Some more explaination for the provided editorial: the left pipes are potential profit, and the right pipes are the profits “eaten up” by digging other blocks.