# “The broken pedometer” optimizations

This is a solution to the problem: "The Broken Pedometer" on the UVA online judge. (Note: I can not use anything beyond what is in g++ 4.6 which is what is used for the competition I'm training for.)

Algorithmic approach (pretty simple, but fast enough, not needed to understand to comment on the code):

• possible_led_removals recursively attempts to remove one integer from all the strings in leds while maintaining a unique array of strings (leds):
• If removing an integer leads to duplicates in leds, return (base case)
• Otherwise, return the maximum amount of possible removals (depth) at the same index from the strings in leds, while maintaining leds to be an array of unique strings (recursion)

My C++ is /very/ rough, and I mostly use C++ because of the STL. However, I'd like to improve my C++ to improve my contest performance, so any help, algorithmic as well as code-wise is much appreciated! Thanks!

#include<iostream>
#include<cstdlib>
#include<vector>
#include<sstream>
#include<algorithm>
using namespace std;

size_t n_leds, n_symbols;

bool any_duplicates(vector<string> &leds)
{
for(size_t i = 0; i < (int)leds.size(); ++i)
for(size_t j = i + 1; j < (int)leds.size(); ++j)
if(leds[i] == leds[j]) return true;

return false;
}

int possible_led_removals(size_t erase_index, vector<string> leds, size_t depth)
{
for(vector<string>::iterator it = leds.begin(); it != leds.end(); ++it) {
string::iterator string_it;
string_it = (*it).begin() + erase_index;
(*it).erase(string_it);
}

int max_depth = 0;

if (any_duplicates(leds)) {
return depth;
} else {
for(size_t i = 0; i < (int)leds[0].length(); ++i)
max_depth = max(possible_led_removals(i, leds, depth + 1), max_depth);
}

return max_depth;
}

int main()
{
size_t problems;
cin >> problems;

for(size_t i = 0; i < problems; ++i) {
cin >> n_leds >> n_symbols;

vector<string> symbols;

for(size_t j = 0; j < n_symbols; j++) {
ostringstream led;

for(size_t k = 0; k < n_leds; k++) {
bool on;
cin >> on;
led << on;
}

symbols.push_back(led.str());
}

int max_removals = 0;
for(int i = 0; i < n_leds; ++i)
max_removals = max(max_removals, possible_led_removals(i, symbols, 0));

cout << n_leds - max_removals << endl;
}

return 0;
}


## Notes on the code

bool any_duplicates(vector<string> &leds)
{


if you're not planning to change the vector contents, this should be

bool any_duplicates(vector<string> const &leds)


also observe this is an O(n2) search; it may not matter much for N<=100 as given, but simply sorting the values and doing a linear scan would be O(n log n).

## Notes on data structures

Since you're given P<=15, you could trivially encode each symbol as a bitmap in a uint16_t. This simplifies the LED deactivation (just mask out the bit) and speeds up the sorting and duplicate detection (it's an integer comparison).

## Notes on algorithms

Since the number of symbols may greatly exceed the number of bits, it may be possible to cut the search space down faster by working the other way round.

At least, if some of the bits (LEDs) have the same value in every symbol, you know they can always be removed and you don't need to check them. In the second linked example, the last two bits are always zero, so you can ignore them during your search.

I also have a nagging feeling there could be a much smarter approach based on information theory, but if there is, it hasn't crystallized yet.

## Footnotes

• justification of O(n2):

the outer loop

for(size_t i = 0; i < (int)leds.size(); ++i)


is clearly linear, so we execute the inner loop n times:

for(size_t j = i + 1; j < (int)leds.size(); ++j)
if(leds[i] == leds[j]) //...


does n-1 comparisons for each n in [0..size). Let's write out the total number of steps for some small values of n to be clear:

• n=2: i in [0,2) gives two iterations over the outer loop; the first gives two iterations of the inner loop for j in [0,2) and the second gives a single iteration for j in [1,2). So, we did 2 + 1 = 3 comparisons.
• n=3: now we do three top-level iterations, and the inner loop covers the ranges j in [0,3), [1,3), [2,3). So, 3 + 2 + 1 = 6 comparisons.
• n=4: 4 + 3 + 2 + 1 = 10 comparisons

this is just the sum of the arithmetic progression n + (n-1) + ... + 2 + 1

Use the formula given in the link with a1=1 and an=n to get (n/2)(n+1)

This gives the maximum number of comparisons performed, (n/2)(n+1) = (n2 + n)/2, proportional to O(n2). Obviously it may return early, but I don't know how likely that is: this is the worst-case performance.

• bitmap encoding

Taking one of the sample symbols from your link, 1 0 1 1 0 1 1: since every character is one or zero I can trivially interpret this as a binary number:

column: 6 5 4 3 2 1 0
value:  1 0 1 1 0 1 1
= 2^6 + 2^4 + 2^3 + 2^1 + 2^0 = 91 (decimal)


and as you're guaranteed <=15 LEDs, you need <=15 bits to represent every possible value, so uint16_t (giving 16 bits) is big enough.

• bitmap manipulation

Now, comparisons are clearly faster with this scheme, but so is disabling LEDs. For example, it was something like:

vector<string> disable_led(size_t index, vector<string> leds)
{
for(vector<string>::iterator it = leds.begin(); it != leds.end(); ++it) {
string::iterator string_it;
string_it = (*it).begin() + erase_index;
(*it).erase(string_it);
}
return leds;
}


while the integer-encoded version could be:

vector<uint16_t> disable_led(size_t index, vector<uint16_t> leds)
{
uint16_t mask = ~(1 << (n_leds-index));
for(auto it = leds.begin(); it != leds.end(); ++it) {
}
return leds;
}


You could even avoid copying & mutating the LED vector at all, just update the mask as you pass it down, using it in each comparison. That seems like more work in the inner loop, but there's good chance it's faster anyway

• Thanks for your notes. Couple of questions: a) Is this really an O(n^2) search? Because of the recursion (although backtracking, so it depends on the input, of course) isn't the average-case much worse? b) Can you elaborate on the "encode each symbol as a bitmap" and "just mask out the bit"? Thank you very much for your time! – Sirupsen Aug 17 '12 at 15:28
• The O(n^2) comment was just addressed to any_duplicates, not the whole thing – Useless Aug 17 '12 at 16:50

Just some hints to improve your C++ code if not the algorithm logic:

• Use const references for passing big objects like vectors to functions. For example, replace vector<string> leds by const vector<string>& leds in any_duplicates. Otherwise, it will perform a full copy of the vector and its elements. Here, const reference is right since the vector is not modified.
• You could add std::ios_base::sync_with_stdio(false); at the beginning of your code. Default thing for streams is to call C functions from cstdio. Putting that line allow streams not to use those functions and then to be faster.
• For readability, you could replace (*it).stuff by it->stuff everywhere.
• vector::size() returns a size_t and that's what you use in your loops. No need to cast the result to an int.
• I may be wrong, but I don't see any functions from cstdlib used here. You could get rid of that header.

You could also probably improve readability and performance by using features from C++11 (usable with the option -std=c++0x with gcc). I don't know if your contest allows it or not.

• The problem I saw with using const vector<string>& leds as a parameter for possible_led_removals is that it modifies leds, thus passing by reference will alter a vector used later by any other function that recurses on the same vector. – Sirupsen Aug 17 '12 at 14:46
• Also, size_t is declared in cstdlib, isn't it? – Sirupsen Aug 17 '12 at 14:50
• @Sirupsen It's declared in cstddef which is included by any header that uses size_t, so most of the C and C++ headers. – Morwenn Aug 17 '12 at 14:51
• Great! Thank you very much for your help. :-) – Sirupsen Aug 17 '12 at 14:52

The others have made some good points, a few I'd like to add.

Look at using std::bitset<> to hold the on/off information. Then use the bitmap encoding/manipulation that @Useless has suggested.

for(size_t i = 0; i < (int)leds[0].length(); ++i)
max_depth = max(possible_led_removals(i, leds, depth + 1), max_depth);


This piece is, I think, the source of your serious speed issues. The problem is that you reach the same subset of working led segments by different approaches. i.e. you and remove 0 then 1, or you can remove 1 then 0, but you end up in the same place. You should rework you code so that it considers each subset only once.

• This is true. Do you have any ideas on how to avoid this, besides some sort of memorization? – Sirupsen Aug 17 '12 at 18:36
• @Sirupsen, simplest solution would be to do for(size_t i = erase_index;... That way you only consider one order of producing each possible subset. – Winston Ewert Aug 17 '12 at 18:40