427.md (3613B)
1 Source: https://codeforces.com/blog/entry/12082 2 3 The [round statistics](//codeforces.com/blog/entry/12087) are nicely put by [DmitriyH](/profile/DmitriyH "Эксперт DmitriyH"). 4 5 #### [427A - Полицейские-рекруты](/contest/427/problem/A "Codeforces Round 244 (Div. 2)") ( Author : [Bidhan](/profile/Bidhan "Кандидат в мастера Bidhan") ) 6 7 Maintain a variable, *sum*. Initially *sum*=0, it keeps the number of currently free police officers. With every recruitment operation, add the number of officers recruited at that time to *sum*. When a crime occurs, if *sum* > 0 then decrease the number of free officers by one, otherwise no officers are free so the crime will go untreated. 8 9 Model solution : [6546268](/contest/427/submission/6546268 "Посылка 6546268 от Bidhan") 10 11 #### [427B - Перевод заключенных](/contest/427/problem/B "Codeforces Round 244 (Div. 2)") ( Author : [Bidhan](/profile/Bidhan "Кандидат в мастера Bidhan") ) 12 13 The severity of crimes form an integer sequence. Find all the contiguous sequences without any integer greater than *t*. If the length of any sequence is *L*, then we can choose *c* prisoners from them in *L* - *c* + 1 ways. 14 15 Model solution : [6546272](/contest/427/submission/6546272 "Посылка 6546272 от Bidhan") 16 17 #### [427C - КПП](/contest/427/problem/C "Codeforces Round 244 (Div. 2)") ( Author : [Bidhan](/profile/Bidhan "Кандидат в мастера Bidhan") ) 18 19 Find the strongly connected components of the graph. From each component we need to choose a node with the lowest cost. If there are more than one nodes with lowest cost, then there are more than one way to choose node from this component. 20 21 Model solution : [6546275](/contest/427/submission/6546275 "Посылка 6546275 от Bidhan") 22 23 #### [427D - Расшифровка сигнала](/contest/427/problem/D "Codeforces Round 244 (Div. 2)") ( Author : [msh_shiplu](/profile/msh_shiplu "Эксперт msh_shiplu") ) 24 25 ***O*(*n*2) dynamic programming solution :** Calculate the longest common prefix ( LCP ) for each index of *s*1 with each index of *s*2. Then, calculate LCP for each index of *s*1 with all the other indexes of it's own ( *s*1 ). Do the same for *s*2. Now from precalculated values, you can easily check the length of the shortest unique substring starting from any of the indexes of *s*1 or *s*2. Suppose *i* is an index of *s*1 and *j* is an index of *s*2. Find the LCP for *i* and *j*. Now, the minimum of the length of LCP, length of shortest unique substring starting from *i*, length of shortest unique substring starting from *j* is the answer for *i*,*j*. Now we need to find the minimum answer from all possible *i*,*j* pair. This problem can also be solved in  by suffix array and in *O*(*n*) using suffix automaton. 26 27 Model solution : [6546277](/contest/427/submission/6546277 "Посылка 6546277 от Bidhan") 28 29 #### [427E - Полицейский патруль](/contest/427/problem/E "Codeforces Round 244 (Div. 2)") ( Author : [Bidhan](/profile/Bidhan "Кандидат в мастера Bidhan") ) 30 31 Trying to place the police station on existing criminal locations is the best strategy. Calculate the cost from the leftmost criminal location, then sweep over the next locations. By doing some adjustments on the cost of the previous location will yield the cost of the current location. 32 33 Model solution : [6546283](/contest/427/submission/6546283 "Посылка 6546283 от Bidhan")