Bidhan's blog

By Bidhan, 8 years ago, In English

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

Read more »

  • Vote: I like it
  • +27
  • Vote: I do not like it

By Bidhan, 8 years ago, In English

Good day everyone.

Codeforces round #244 for division 2 participants will start at May 2, Friday, 19:30 MSK. As you all know, participants from division 1 can also take part from out of the competition.

The round was prepared by me (Bidhan), student of University of Dhaka, Bangladesh. This is my first codeforces round. I have tried to prepare interesting and solvable problems for division 2 participants. Special effort was given to make the problem statements as clear as possible. Hoping that everything will go right and everyone will enjoy the round.

Special thanks to msh_shiplu, lecturer of University of Dhaka, for his contribution to the contest by finding time to set one of the problems, writing alternates, reviewing problem statements and giving expert advice on dataset generation in spite of his hectic schedule.

Also, a BIG thanks to nice guy Gerald, for helping throughout the preparation process.

I wish all the participants good luck :)

Update0 : Score distribution is 500-1000-1500-2000-2500.

Update1 : A short editorial of the contest is here. The post will be enlarged to detailed editorial later.

The Russian translation of this post is here.

Read more »

  • Vote: I like it
  • +234
  • Vote: I do not like it