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

Sort by

recency

|

19 Discussions

|

  • jaredtrh20
     + 0 comments

    Here's my attempt at a proof:

    When : Any one button would turn off all the lights so pick the cheapest one.

    Otherwise:

    Firstly, we know that each button is either pressed once or not at all because 2 presses is the same as not pressing and is always cheaper since cost is always positive.

    Secondly, the order of button presses does not matter as the state of any light is completely determined by the number of button presses at distance away from it.

    With that in mind, let's try deciding to press or not press buttons greedily from left to right. Consider that we are at button and all buttons' states have already been decided. At this point all lights will be off otherwise it is impossible to turn off all lights. Now, if light is on, we must press button because no button to the right will be able to turn it off. Likewise, if light is off, we must not press button which will turn it on and we won't be able to turn it off with buttons to the right. So buttons' states can be entirely determined after we know the states of buttons .

    Take an arbitrary button press configuration for and let denote pressed buttons in ascending order with . Then the open-closed interval will either be completely on/off and they will be alternating. Remove if is off. Now is on which will be turned off by the th button. Note that this button press flips the entire alternating sequence because its range is while the range of the initial buttons are . This turns on and we can remove and append (like a queue). From there we let induction take over. Note that when would go past the end but it would not cover the end it is impossible to turn off all the lights. From this we see that each contributes and since the contribution would always be positive and we are trying to minimize, we should only press one button .

    A better time complexity is instead of like the editorial says because each takes .

  • yashparihar729
     + 0 comments

    Here is my solution in java, javascript, python, C, C++, Csharp HackerRank Turn Off the Lights Problem Solution

  • 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;
}

  • konetikirankumar
     + 0 comments
    def get_sum(s, c, k, t):
    v = None
    for p in range(s, len(c), 2 * k + 1):
        print(p, end=' ')
        if v:
            t += 2 * k + 1
        else:
            v = 0
        v += c[p]
    if t < len(c):
        v = None
    print(' => ', v, 't=', t)
    return v
def turnOffTheLights(k, c):
    mm = None
    for s in range(k + 1):
        summ = get_sum(s, c, k, k + 1 + s)
        if not mm or (summ and mm > summ):
            mm = summ
    return mm

  • thecodingsoluti2
     + 0 comments

    Here is Turn Off the Lights problem solution - https://programs.programmingoneonone.com/2021/07/hackerrank-turn-off-the-lights-problem-solution.html