15 November 2015 devdraft algorithm

DevDraft just held the Sept. challenge 2015 with an intriguing algorithmic problem. After days of contemplation, my solution reaches 100% code correctness and perfect algorithmic problem solving for runtime efficiency.

Problem

A nearby city has recently undergone a massive revitalization effort and, in order to celebrate and attract economic investment, is going to throw a parade. The mayor plans to deploy a number of security forces for the days leading up to the parade to keep the parade route free of vandalism. However, the budget is limited, so the mayor wants to make sure the security is deployed in such a way as to maximize effectiveness.

You are given a list of integers representing the threat of vandalism occurring on the city blocks along the parade route—​0 means vandalism will not occur on a block, and greater integers indicate a greater danger of vandalism occurring. The parade is planned to move in a straight line and pass by every block exactly once. You are also given several security forces, each of which can patrol a number of adjacent blocks, totally nullifying the threat on the blocks they patrol. The forces come in different types with different patrol lengths; for example, an officer on bike can patrol farther than an officer on foot. The forces are represented by a list of pairs of integers, where the first integer is the number of adjacent blocks a type of force can patrol and the second is how many forces are available of that type.

The number of forces available is limited so you must place them strategically to minimize the sum of threat levels of all blocks that are not patrolled. Because the minimum threat level may be achieved by multiple arrangements of security, we ask that you output only the minimum total threat level that can be achieved, and not the positions of the forces.

C++ Implementation

Originally, the implementation is in Groovy but the runtime performance can be 100X slower than its C++ counterpart. Therefore, I decided to submit the C++ version though many Groovy constructs are not supported by the C++ STL and must be reimplemented. As expected, the rewards pay off.

The following code in C++ implements a branch and bound dynamic programming algorithm to solve the problem. More information about the solution analysis and complexity is available on the repo.


comments powered by Disqus