"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&lt;iostream&gt;
#include&lt;cstdlib&gt;
#include&lt;vector&gt;
#include&lt;sstream&gt;
#include&lt;algorithm&gt;
using namespace std;

size_t n_leds, n_symbols;

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

  return false;
}

int possible_led_removals(size_t erase_index, vector&lt;string&gt; leds, size_t depth)
{
  for(vector&lt;string&gt;::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 &lt; (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 &gt;&gt; problems;

  for(size_t i = 0; i &lt; problems; ++i) {
    cin &gt;&gt; n_leds &gt;&gt; n_symbols;

    vector&lt;string&gt; symbols;

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

      for(size_t k = 0; k &lt; n_leds; k++) {
        bool on;
        cin &gt;&gt; on;
        led &lt;&lt; on;
      }

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

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

    cout &lt;&lt; n_leds - max_removals &lt;&lt; endl;
  }

  return 0;
}
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&lt;string&gt; leds by const vector&lt;string&gt;&amp; 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-&gt;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.