Goodland Electricity

Sort by

recency

|

51 Discussions

|

  • + 0 comments
    def main():
        import sys
        input = sys.stdin.read
        data = input().splitlines()
        
        n, k = map(int, data[0].split())
        light = list(map(int, data[1].split()))
        
        # Convert light array to boolean
        light = [True if x == 1 else False for x in light]
        
        k -= 1  # Adjust k to be zero-indexed
        
        result = 0
        last = -1
        index = k
        
        while index < n:
            while index >= 0 and not light[index]:
                index -= 1
            if index == -1 or index <= last:
                print(-1)
                return
            result += 1
            last = index
            index += k * 2 + 1
        
        if last + k + 1 < n:
            result += 1
            l = False
            for i in range(n - 1, n - k - 2, -1):
                if light[i]:
                    l = True
                    break
            if not l:
                print(-1)
                return
        
        print(result)
    
    if __name__ == '__main__':
        main()
    
  • + 0 comments

    Java

    public static int pylons(int k, List<Integer> arr) {
            int ans = 0, n = arr.size();
            for(int i = 0; i < n; i++){
                
                // Power plant should be built on buildIdx
                int buildIdx = Math.min(i + (k - 1), n - 1);
                
                // Keep looking for a power plant
                while(buildIdx >= 0 && buildIdx < n && arr.get(buildIdx) == 0)
                    buildIdx--;
                    
                if(buildIdx >= 0 && buildIdx < n && arr.get(buildIdx) == 1 && Math.abs(buildIdx - i) < k){
                    ans++; // Build here
                    i = buildIdx + (k - 1);
                }
                else
                    return -1;
            }
            return ans;
        }
    
  • + 0 comments

    C#:

    public static int pylons(int k, List<int> arr)
        {
            int p = -1;
            int count = -1;
            p = StartingKIndex(p, arr, k);
            if(p != -1)
            {
                p = MiddleIndexes(p, k, arr, out count);
            }
            if(count != -1 && (p + k - 1) < arr.Count - 1)
            {
                p = arr.Count - 1;
                count  = LastIndex(p, k, arr, count); 
            }
            return count;
        }
        
        public static int StartingKIndex(int p, List<int> arr, int k)
        {
            // Check the first city where Power plant can be built within the distribution range
            
            for(int i = k - 1; i >= 0; i--)
            {
                if(arr[i] == 1)
                {
                    p = i; 
                    break;
                }
            }
            
            return p;
        }
        
        public static int MiddleIndexes(int p, int k, List<int> arr, out int count)
        {   
            // StartIndex function will return a city index so make the count as 1 initially.
            count = 1;
            
            // Check for the next cities where Power plant can be built and increment the count
            while((p + (2 * k) - 1) < arr.Count)
            {
                bool flag = false;
                p = p + (2 * k) - 1;
                for(int i = p; i > p - (2 * k) + 1; i--)
                {
                    if(arr[i] == 1)
                    {
                        p = i;
                        count = count + 1;
                        flag = true;
                        break;
                    }
                }
                
            // if a city cannot be covered withing the distribution range make the count as -1
                if(!flag)
                {
                    count = -1;
                    break;
                }
            }
            return p;
        }
        
        public static int LastIndex(int p, int k, List<int> arr, int count)
        {
         // find the last city where the power plant can be built within the distribution range.   
            
            bool flag = false;
            for(int i = p; i > arr.Count - k + 1; i--)
            {
                if(arr[i] == 1)
                {
                    count += 1;
                    flag = true;
                    break;
                }
            }
            
            // if city is not found make the count as -1
            if(!flag)
            {
                count = -1;
            }
            return count;
        }
    
  • + 0 comments

    My approach for this was essentially: given a city position, find the optimal point to place a power plant for that city position. Once I find a place for it, move to the furthest out city position not covered by the power plant I just placed, and do that again. Continue doing that until I reach the end of the array.

    To find the optimal position for a given city, I use the k value to go as far out as possible (taking care to remain in-bounds of the array). I check if the position can contain a power plant. If it can, I use that position. If not, I reduce the value by one and continue. The lowest value is the previously placed power plant + 1 (or 0 if none has been placed yet).

  • + 1 comment

    Hey, someone can explain why sample test case 2's answer is "3"?

    10 3 0 1 0 0 0 1 1 1 1 1

    The range is 3 so it answer seems 2.

    0 1 0 0| 0 1 1 1| 1 1