We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Turn Off the Lights
  5. Discussions

Turn Off the Lights

  • mark_webster
     + 0 comments

    Concise C++ version.

    Note: this challenge had the potential to be interesting, but the expected solution actually solves only a very easy subset of the problem domain as stated in the challenge. It would be easy to construct input data that completely defeat most of the submitted answers (including this one). This low quality challenge should probably be removed or updated.

    long turnOffTheLights(int k, vector<int> c) {
    const int len = c.size(), kwid = 1+k*2, adj = len-k-1+kwid;
    int64_t best = INT64_MAX, cc = best;
    for (int beg=0, pos, rem; beg<=k; best=min(best, cc), beg++) {
        if ((rem = (adj-beg) % kwid) && rem <= k) continue;
        for (pos=beg, cc=0; pos<len && cc<best; pos+=kwid) cc += c[pos];
    }
    return best;
}