427A - Полицейские-рекруты ( Author : Bidhan )
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.
Model solution : 6546268
427B - Перевод заключенных ( Author : Bidhan )
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.
Model solution : 6546272
427C - КПП ( Author : Bidhan )
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.
Model solution : 6546275
427D - Расшифровка сигнала ( Author : msh_shiplu )
O(n2) dynamic programming solution : Calculate the longest common prefix ( LCP ) for each index of s1 with each index of s2. Then, calculate LCP for each index of s1 with all the other indexes of it's own ( s1 ). Do the same for s2. Now from precalculated values, you can easily check the length of the shortest unique substring starting from any of the indexes of s1 or s2. Suppose i is an index of s1 and j is an index of s2. 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.
Model solution : 6546277
427E - Полицейский патруль ( Author : Bidhan )
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.
Model solution : 6546283