Блог пользователя Bidhan

Автор Bidhan, 11 лет назад, По-английски

The round statistics are nicely put by DmitriyH.

427A - Police Recruits ( 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 - Prison Transfer ( 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 - Checkposts ( 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 - Match & Catch ( 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 - Police Patrol ( 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

Полный текст и комментарии »

Разбор задач Codeforces Round 244 (Div. 2)
  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

Автор Bidhan, 11 лет назад, перевод, По-русски

Доброго дня!

Совсем скоро 2 Мая, 19:30 MSK. стартует Codeforces Round #244 для участников из второго дивизиона. Как все вы знаете, участники из первого дивизиона могут посоревноваться вне конкурса.

Раунд был подготовлен мной (Bidhan), студентом университета Дхака, Бангладеш. Это мой первый раунд на Codeforces, и я старался сделать задачи контеста интересными и решаемыми для участников из второго дивизиона. Очень много усилий было потрачено на то, чтобы условия задач были как можно понятнее. Надеюсь, что раунд пройдет без накладок, а задачи вам понравятся.

Отдельное спасибо msh_shiplu, лектору университета Дхака, за его большой вклад в подготовку раунда (подготовка одной из задач, написание альтернативных решений, разработка тестов). Также спасибо Gerald за помощь в подготовке контеста.

Желаю всем удачи :-)

Распределение баллов по задачам: 500-1000-1500-2000-2500

Полный текст и комментарии »

  • Проголосовать: нравится
  • +234
  • Проголосовать: не нравится