9.md (5354B)
1 Source: https://codeforces.com/blog/entry/283 2 3 ### A. [Die Roll](../../../contest/9/problem/A) 4 5 If the maximum of Yakko's and Wakko's points is a, then Dot will win, if she has not less than a points. So the probability of her win is (6 - (a-1)) / 6. Since there are only 6 values for a, you can simply hardcode the answers. 6 7 8 ### B. [Running Student](../../../contest/9/problem/B) 9 10 It is simple to calculate the time *t**i* that the Student will need, if he gets off the bus at the i-th stop: *t**i* = *b**i* + *s**i*, where *b**i* = *x**i* / *v**b* is the time he will drive on the bus, and  is the time he will need to get from the i-th stop to the University. We need to choose indices with minimal possible *t**i*, and among them - the index with minimal possible *s**i*, that is, with maximal *b**i*, that is (since the coordinates of bus stops are already ordered) with maximal i. 11 12 Note that due to precision issues, you should be careful when you compare *t**i*: the condition *t**i* = *t**j* should be written in the form |*t**i* - *t**j*| < ε for some small ε. 13 14 15 ### C. [Hexadecimal's Numbers](../../../contest/9/problem/C) 16 17 Brute force solution, when you try each number from 1 to n, will not fit into the time limit. 18 Note, however, that all good numbers have at most 10 digits, and each of the digits is 0 or 1. That is, there are at most 210 binary strings to check. Each of these strings is a number from 1 to 210 - 1 in binary representation. So the algorithm is the following: for each number from 1 to 210 - 1 write its binary representation, read it as if it was decimal representation and compare the result to n. 19 20 21 ### D. [How many trees?](../../../contest/9/problem/D) 22 23 Denote by *t**nh* the number of binary search trees on n nodes with height equal to h. We will derive a recurrent formula for *t**nh*. For the base case note that *t*00 = 1 (empty tree), and *t**i*0 = *t*0*i* = 0 if i>0. 24 25 Now take any binary search tree on n nodes with height equal to h. Let m be the number written at its root, 1 ≤ *m* ≤ *n*. The left subtree is a binary search tree on m-1 nodes, and the right subtree is a binary search tree on n-m nodes. The maximal of their heights must be equal to h-1. Consider 2 subcases: 26 1. The height of the left subtree is equal to h-1. There are *t**m* - 1, *h* - 1 such trees. The right subtree can have any height from 0 to h-1, so there are  such trees. Since we can choose left and right subtrees independently, we have  variants in this case. 27 2. The height of the left subtree is less than h-1. There are  such trees, and the right subtree must have height exactly h-1, which gives us totally  variants. 28 So the recurrent formula is the following: . 29 30 All the values *t**nh* can be calculated by dynamic programming. The answer, then, is . 31 32 33 34 ### E. [Interesting graph and Apples](../../../contest/9/problem/E) 35 36 The funny ring consists of n vertices and n edges. If there is another edge except for these n, then the vertices it connects belong to more than one cycle. So, an interesting graph is just a funny ring. 37 A graph is a funny ring if and only if the following conditions hold: 38 A1. The degree of each vertex equals 2. 39 A2. The graph is connected. 40 Now let's figure out when a graph is not yet a funny ring, but can be transformed into a funny ring by adding edges. There are obvious necessary conditions: 41 B1. m < n. 42 B2. There are no cycles. 43 B3. The degree of each vertex is not more than 2. 44 Let's add edges so that these conditions were preserved, and the sequence of edges was lexicographically minimal. So, we add an edge (i,j) such that: 45 1. The degrees of i and j are less than 2. (Otherwise we would break B3). 46 2. i and j belong to different connected components. (Otherwise we would break B2). 47 3. The pair (i,j) is lexicographically minimal. 48 Let's see what we have when we can't add edges anymore. Since there are no cycles, each connected component is a tree, and therefore has at least one vertex with degree less than 2. If there are two connected components, then they could be connected by an edge without breaking B1-B3. So the graph is connected, has no cycles, and the degree of each vertex is not more than 2. This means that the obtained graph is just a walk and we can connect its end points to obtain a funny ring. 49 50 To summarize, the algorithm is the following: 51 1. Check if A1-A2 hold. If yes, output "YES" and 0. 52 2. Check if B1-B3 hold. If no, output "NO". 53 3. Output "YES" and n-m. 54 4. Add edges as described. When the edge (i,j) is added, output "i j". 55 5. Find the only vertices i and j with degree less than 2 (they can be equal if n=1). Output "i j".