HackerRank Turn Off the Lights Problem Solution

In this post, HackerRank Turn Off the Lights Problem Solution.

There are n bulbs in a straight line, numbered from 0 to n – 1. Each bulb i has a button associated with it, and there is a cost. c. for pressing this button. When some button i is pressed, all the bulbs at a distance < & from bulb i will be toggled(off->on, on->off).
Given n. k, and the costs for each button, find and print the minimum cost of turning off all n bulbs if they’re all on initially.
Input Format
The first line contains two space-separated integers describing the respective values of n
and k.
The second line contains n space-separated integers describing the respective costs of each bulb (l.e., Co, C1,…, Cn-1).

Output Format
Print a long integer denoting the minimum cost of turning off all n bulbs.

Sample Input

3 1
1 1 1

Sample Output

Explanation

If we press the middle switch, the middle bulb and the k = 1 closest adjacent bulbs (i.e., the first and third) will turn off. Because all bulbs will be off in one button press, this cost is minimal. Thus, we print 1 as our answer.

HackerRank Turn Off the Lights Problem Solution

Turn Off the Lights C++ Solution

#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T> using vv=vector<vector<T>>;
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"<<endl; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
const ll MOD=1e9+7;
const ll INF=1e14;


int main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);
  int n,t;
  cin>>n>>t;
  vv<pll> g(n+1);
  vector<int> c(n);
  rep(i,n) cin>>c[i];
  ll re=INF;
  rep(i,min(n,t+1)){
    ll sum=0,rb=0;
    for(int j=i;j<n;j+=2*t+1){
      sum+=c[j];
      rb=j+t;
    }
    if(rb>=n-1) MN(re,sum);
  }
  cout<<re<<endl;
  return 0;
}

Turn Off the Lights C Sharp Solution

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ProblemSolver
{
    class Solution
    {
        static char[] splitors = { ' ' };

        /* Input data here */
        static int n;
        static int k;
        static long[] c;        

        static void Input()
        {
            string[] str = Console.ReadLine().Split(splitors);
            n = int.Parse(str[0]);
            k = int.Parse(str[1]);
            str = Console.ReadLine().Split(splitors);
            c = new long[n];
            for (int i = 0; i < n; i++)
            {
                c[i] = long.Parse(str[i]);
            }
        }

        static void Search()
        {            
            long[] cost = new long[n];
            for (int i = 0; i < n; i++)
            {
                cost[i] = -1;
            }
            cost[n - 1] = 0;

            for (int i = n - 2; i >= 0; i--)
            {
                int next = i + k + 1;
                if (next < n)
                {
                    int j = Math.Min(next + k, n - 1);
                    // for (int j = i + 1; j <= next + k && j < n; j++)
                        if (cost[j] != -1)
                        {
                            if (cost[i] == -1)
                            {
                                cost[i] = cost[j] + c[next];
                            }
                            else
                            {
                                cost[i] = Math.Min(cost[i], cost[j] + c[next]);
                            }
                        }
                }
            }

            long ret = -1;
            for (int last = 0; last <= k && last < n; last++)
            {
                int j = Math.Min(last + k, n - 1);
                //for (int j = 0; j <= last + k && j < n; j++)
                    if (cost[j] != -1)
                    {
                        long val = cost[j] + c[last];
                        if (ret == -1)
                        {
                            ret = val;
                        }
                        else
                        {
                            ret = Math.Min(ret, val);
                        }
                    }
            }

            Console.WriteLine(ret);
        }

        static void Main(string[] args)
        {
            Input();
            Search();
        }
    }
}

Turn Off the Lights Java Solution

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] c = new int[n];
        for (int i = 0; i < n; i++) {
            c[i] = sc.nextInt();
        }
        long ans = 1000000000000000000l;
        for (int i = 0; i <= Math.min(n-1, k); i++) {
            int maxCovered = i+k;
            long partialAns = c[i];
            boolean possible = true;
            while (maxCovered < n-1) {
                int button = maxCovered+k+1;
                if (button >= n) {
                    possible = false;
                    break;
                }
                partialAns += c[button];
                maxCovered = button+k;
            }
            if (!possible)
                continue;
            ans = Math.min(partialAns, ans);
        }
        System.out.println(ans);
    }
}

Turn Off the Lights Python Solution

n, k = map(int, raw_input().split())
c = map(int, raw_input().split())

dp = [float('inf') for i in xrange(n+ 1)]
dp[0] = 0

for i in xrange(1, n+1):
    dp[min(i+k, n)] = min(dp[min(i+k, n)], dp[max(i-k-1, 0)] + c[i-1])
#print dp
print dp[n]