codeforces-scrape

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

14.md (4608B)


      1 Source: https://codeforces.com/blog/entry/389
      2 
      3 ### [A. Letter](../../../contest/14/problem/A)
      4 
      5 To find the smallest rectangle containing the picture, iterate through the pairs (i,j) such that the j-th symbol in i-th line is '*'; find the minimum and maximum values of i and j from these pairs. The rectangle to output is [*i**min*, *i**max*] × [*j**min*, *j**max*].  
      6    
      7 
      8 ### [B. Young Photographer](../../../contest/14/problem/B)
      9 
     10 First we find the intersection of all segments. To do this, denote by m the rightmost of left ends of the segments and denote by M the leftmost of right ends of the segments. The intersection of the segments is [m,M] (or empty set if m>M). Now determine the nearest point from this segment. If *x*0 < *m*, it's *m*, and the answer is *m* - *x*0. If *x*0 > *M*, it's *M*, and the answer is *x*0 - *M*. If ![](https://espresso.codeforces.com/749c7b5acd626af9f654a7a9c45a7e72ae3739b1.png), it's *x*0, and the answer is 0. If m>M, then the answer is -1.  
     11   
     12 
     13 ### [C. Four Segments](../../../contest/14/problem/C)
     14 
     15 There must be many ways to solve this problem. The following one seems quite easy to code.  
     16 First count the number of distinct points among segments' ends. If it's not equal to 4, the segments can't form a rectangle and we output "NO". Then calculate the minimum and maximum coordinates of the 4 points: *x**min*, *x**max*, *y**min*, *y**max*. If *x**min* = *x**max* or *y**min* = *y**max*, then even if the segments form a rectangle, it has zero area, so we also output "NO" in this case.  
     17 Now if the segments indeed form a rectangle, we know the coordinates of its vertices — (*x**min*, *y**min*), (*x**min*, *y**max*), (*x**max*, *y**min*) and (*x**max*, *y**max*). We just check that every side of this rectangle appears in the input. If it is the case, we output "YES", otherwise we output "NO".  
     18   
     19 
     20 ### [D. Two Paths](../../../contest/14/problem/D)
     21 
     22 Take any pair of non-intersecting paths. Since Flatland is connected, there must be a third path, connecting these two. Remove a road from the third path. Then Flatland is divided into two components — one containing the first path, and the other containing the second path. This observation suggests us the algorithm: iterate over the roads; for each road remove it, find the longest path in both connected components and multiply the lengths of these paths. The longest path in a tree can be found by depth first search from each leaf.   
     23   
     24 
     25 ### [E. Camels](../../../contest/14/problem/E)
     26 
     27 Let us call an index j such that *y**j* - 1  >  *y**j*  <  *y**j* + 1 a *cavity*. Also, we'll call humps and cavities by the common word *break*. Then there must be exactly *T* = 2*t* - 1 breaks, and the first one must be a hump.  
     28 Denote by *f**nth* the number of ways in which a camel with *t* breaks, ending at the point (n,h), can be extended to the end (the vertical *x**N* = *N*) so that the total number of breaks was equal to T. Note that:  
     29 1. *f**NTh* = 1, if h=1,2,3,4. (We have already finished the camel and it has T breaks)  
     30 2. *f**Nth* = 0, if 0 ≤ *t* < *T*, *h* = 1, 2, 3, 4. (We have already finished the camel, but it has less than T breaks)  
     31 3. *f**n*, *T* + 1, *h* = 0, if 1 ≤ *n* ≤ *N*, *h* = 1, 2, 3, 4. (The camel has already more than T breaks).  
     32    
     33 Now we find the recurrent formula for *f**nth*. Suppose that *t* is even. Then the last break was a cavity, and we are moving up currently. We can continue moving up, then the number of breaks stays the same, and we move to one of the points (*n* + 1, *h* + 1), (*n* + 1, *h* + 2), ..., (*n* + 1, 4). Or we can move down, then the number of breaks increases by 1, and we move to one of the points (*n* + 1, *h* - 1), (*n* + 1, *h* - 2), ..., (*n* + 1, 1). This gives us the formula  
     34 ![](https://espresso.codeforces.com/bb042e4d20db3f7b4c33498561e49dca993dcc6f.png).  
     35   
     36 If *t* is odd, then the last break was a hump, and similar reasoning leads to the formula  
     37 ![](https://espresso.codeforces.com/8fc933a174c005b52ffcb7abab83c0be0a45a020.png).  
     38   
     39 We can calculate *f**nth* by dynamic programming. Consider now the point (2, *h*) on a camel. There are h-1 ways to get to this point (starting from points (1, 1), ..., (1, *h* - 1)), and *f*2, 0, *h* ways to extend the camel to the end. So the answer to the problem is ![](https://espresso.codeforces.com/354f45c5b67de98802fb5de9d46822d18922657e.png).