Tuesday, July 17, 2012

UVA 12416 - Excessive Space Remover


You are editing a text in a simple editor like notepad, you start to wondering how to remove all the consecutive spaces from your document. After a while, you came with the idea of repeatedly "replace all" two consecutive spaces with one space (let's call this an action). Facing this issues makes you thing even further, now you want to know the number of actions required to remove all the consecutive spaces from your document.

The first observation to solve this problem is that for all the regions with consecutive spaces we just care about the one with higher number of consecutive spaces. The following example shows a string were the highest number of  consecutive spaces is 4:


Is not hard to see that the other regions need less or equal number of actions to complete (because the the actions are parallel in each region). Which means we just need to focus in the amount of spaces of the region with more consecutive spaces.

Now let's get our hands dirty with an example, let's call \(N\) the maximum number of consecutive spaces in certain region of our document.

Note that the number of actions increase every time we exceed a power of 2. Once we know this code the solution is straightforward, first we iterate the whole string and get the value of the region with more consecutive spaces, let's called it \(b\), after that, we increment a variable \(i\) until \(2^{i} < b\) holds.

No comments: