codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

166.md (3637B)


      1 Source: https://codeforces.com/blog/entry/4173
      2 
      3 Initially the order of problems was A-C-E-D-B. But we were not sure about last two.
      4 
      5 [166A - Rank List](/contest/166/problem/A "Codeforces Round 113 (Div. 2)")
      6 
      7 This is simple straight-forward problem — you were asked to sort the teams with the following comparator: (*p*1 > *p*2) or (*p*1 = *p*2 and *t*1 < *t*2). 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.
      8 
      9 [166B - Polygons](/contest/166/problem/B "Codeforces Round 113 (Div. 2)")
     10 
     11 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.
     12 
     13 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.
     14 
     15 Similarly you can cut polygon A into trapezoids (with vertical cuts). In this case you'll need a binsearch by *x*-coordinate.
     16 
     17 [166C - Median](/contest/166/problem/C "Codeforces Round 113 (Div. 2)")
     18 
     19 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.
     20 
     21 Also there is a solution without any cases: while the median isn't equal to *x*, just add one more number *x* to array.
     22 
     23 [166D - Shoe Store](/contest/166/problem/D "Codeforces Round 113 (Div. 2)")
     24 
     25 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 *l**i* and *l**i* + 1. It allows solving with dynamics. The state will be (the number of first unconsidered man *i*, is pair of shoes with size *l**i* available, is pair of shoes with size *l**i* + 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).
     26 
     27 [166E - Tetrahedron](/contest/166/problem/E "Codeforces Round 113 (Div. 2)")
     28 
     29 Obvious solution with dynamics: you need to know only how many moves are left and where is the ant. This is 4*n* states, each with 3 options – most of such solution passes. Observe that the vertices A, B, C are equivalent. This allows writing such solution:
     30 
     31 ```
     32 int zD = 1;
     33 int zABC = 0;
     34 for (int i = 1; i <= n; i++) {
     35 	int nzD = zABC * 3LL % MOD;
     36 	int nzABC = (zABC * 2LL + zD) % MOD;
     37 	zD = nzD;
     38 	zABC = nzABC;
     39 }
     40 cout << zD;
     41 ```
     42 
     43 Also this problem could be solved by *log*(*n*) with binary exponentiation of some 2 × 2 matrix into power *n*.