961D: Pair Of Lines

Take first two points, and see if they can form a candidate line, and then the remaining dots must be on a different line

If does not work, then the third point must be on the same line as either first or second point.

To check if a, b, c are on the same line, calculate 2d CROSS PRODUCT of (b- a) * (c - a), will be 0 if (b - a) and (c - a) are colinear!!!

1012B: Chemical table

Covert a cell into an edge in bipartite graph!!!

For every path of length 3 we can create a fusion, and we can replace the fusion by reducing the total # of edges by 2.

If a component is connected, we must be able to find a path of length 3, then we can just find the longest path and keep performing the fusion, until max length of path is 2, i.e., simple components

Between simple components, we just need one additional edge to create a new component

702D: Road to Post Office

Regardless of the input value, just get the min of 4 cases: all walk, all drive, drive until the last seg and then walk, drive first leg and then walk

853B: Jury Meeting

Two pointer on k segments, on each day, we need to update, for each jury, the cheapest arrival rate (lower), the cheapest departure date (higher), is it enough the satify all requirement, what is the current cost

1118D2: Coffee and Coursework (Hard Version)

Bsaerch on the number of days, and then just take the highest (number of days) of coffee, minus the ones, not contributing

1017D: The Wu

Note that we have only 2^12 possible choices, so we can just pre-compute the answer for 2^24 = 16 mil iterations

500D: New Year Santa Network

For each edge, calculate how likely it is appear in a path between (a, b). For every delta, reduce the result by 3 * delta * probablility

405D: Toy Sum

The greedy intuition is easy, but I was stuck at proving it!!!

Claim: We can always find a solution if and only if size of X is no longer than half of S

Proof:

  1. If n > S/2, the lower bound of X is higher than the upper bound

  2. If n LTE S/2, Suppose X has A symmetric pairs, then the remaining possible symmetric pair numbers are s/2 - A - (n - A) = s/2 - n + 2A. If we add the constraint in, we can see that we just have enough “idle” pairs!!!

615D: Multipliers

This problem is harder that it appears!!!

What is the number of divisors d(x)? Also, f(x) = x^d(x)/2 f(a *b ) = f(b)^d(a) * f(a)^d(b)