Codeforces Round #113 (Div. 2) Tutorial

Codeforces Round #113 (Div. 2) Tutorial

By RAD, 11 years ago, translation,

Initially the order of problems was A-C-E-D-B. But we were not sure about last two.

166A - Rank List

This is simple straight-forward problem — you were asked to sort the teams with the following comparator: (p1 > p2) or (p1 = p2 and t1 < t2). After that you can split the teams into groups with equal results and find the group which shares the k-th place. Many coders for some reason used wrong comparator: they sorted teams with equal number of problems by descending of time. Such submits accidentally passed pretests but get WA #13.

166B - Polygons

Polygon A is convex, so it is sufficient to check only that every vertex of polygon B is strictly inside polygon A. In theory the simplest solution is building common convex hull of both polygons. You need to check that no vertex of polygon B belongs to this hull. But there is a tricky detail: if there are many points lying on the same side of convex hull than your convex hull must contain all these points as vertices. So this solution is harder to implement and has some corner case.

Another solution: cut polygon A into triangles (by vertex numbers): (1, 2, 3), (1, 3, 4), (1, 4, 5), ..., (1, n - 1, n). The sequences of angles 2 - 1 - 3, 2 - 1 - 4, 2 - 1 - 5, ..., 2 - 1 - n is increasing. It means that you can find for each vertex of B to which triangle of A it can belong using binsearch by angle.

Similarly you can cut polygon A into trapezoids (with vertical cuts). In this case you'll need a binsearch by x-coordinate.

166C - Median

If the initial array doesn't contain number x, than you definitely need to add it (that's +1 to answer). Than do the following. While median is strictly less than x you need to increase it. Obviously the surest way to increase the median is to add a maximal possible number (105). Similarly while the median is strictly more than x, add a number 1 to the array. Constraints are small, so you can add the numbers one by one and recalculate the median after every addition.

Also there is a solution without any cases: while the median isn't equal to x, just add one more number x to array.

166D - Shoe Store

Let's sort the people by decreasing of shoes size. Observe that when considering the i-th man we are interested in no more than 2 pairs of shoes: with size li and li + 1. It allows solving with dynamics. The state will be (the number of first unconsidered man i, is pair of shoes with size li available, is pair of shoes with size li + 1 available). You have 3 options: leave the i-th man without shoes or sell him a pair of shoes of one of suitable size (if available).

166E - Tetrahedron

Obvious solution with dynamics: you need to know only how many moves are left and where is the ant. This is 4n states, each with 3 options – most of such solution passes. Observe that the vertices A, B, C are equivalent. This allows writing such solution:

int zD = 1;
int zABC = 0;
for (int i = 1; i <= n; i++) {
	int nzD = zABC * 3LL % MOD;
	int nzABC = (zABC * 2LL + zD) % MOD;
	zD = nzD;
	zABC = nzABC;
}
cout << zD;

Also this problem could be solved by log(n) with binary exponentiation of some 2 × 2 matrix into power n.