CONCEPTS USED:

Binary Search

DIFFICULTY LEVEL:

Hard

PROBLEM STATEMENT(SIMPLIFIED):

Given an array H of lengths of Magical Ropes and array R of the rate by which rope increases daily, print the minimum number of days required to collect ropes that sum up to length X

Restrictions:

  1. You cannot cut the rope, you have to take complete rope for collecting it.

  2. You cannot take a rope with length less than K.

See original problem statement here

For Example:

Input : N = 4, X = 100, K = 45
        Heights[] = [2, 5, 2, 6]
           Rate[] = [10, 13, 15, 12]
Output : 4

Explanation :

Day 0 = [2, 5, 2, 6]

Day 1 = [2 + 10, 5 + 13, 2 + 15, 6 + 12]         = [12, 18, 17, 18]

Day 2 = [12 + 10, 18 + 13, 17 + 15, 18 + 12]     = [22, 31, 32, 30]

Day 3 = [22 + 10, 31 + 13, 32 + 15, 30 + 12]     = [32, 44, 47, 42]

Day 4 = [32 + 10, 44 + 13, 47 + 15, 42 + 12]     = [42, 57, 62, 54]

Ans : Day 4 as (57, 62, 54 are all greater than 45 and sum up to value that is greater than equal to 100)

Can we use Binary Search here ?

We need to find the minimum days required to collect ropes that sum up to length X. The required day can be any day between 0 to 1018 We can use Binary Search for finding the right day efficiently in Logarithmic Time Complexity.

SOLVING APPROACH:

NOTE: As the length of rope is increasing by a given pace so we can calculate its length at any particular day by :-

Lenght at ith day = ith day * Rate of Growth + Initial length

  1. The idea is to perform a Binary Search such that whenever we find a day in which ropes length sum up to X, we will save it and search for a even lower value (as Minimum days are needed).

  2. initialize low as 0 and high as 10^{18}, by this we understand that minimum days can be as low as value of low and as high as value of high.

  3. Calculate mid = (low + high)/2, say mid is our desired day.

  4. Now, Linearly traverse and check for all ropes if their length at mid day is greater than or equal to K, if Yes add its value to a variable Sum.

  5. After traversal if Sum becomes greater or equal to X, simply save it, and check for a even lower value in the left half i.e. (low - (mid - 1)).

  6. Else, search in the right half i.e. ((mid + 1) - high).

SOLUTIONS:


#include <stdio.h>
#define ll long long

int main()
{
  ll N, X, K; scanf("%lld %lld %lld", &N, &X, &K);
  ll height[N], rate[N];

  //input heights of ropes
  for(ll i=0; i<N; i++)
    scanf("%lld", &height[i]);

  //input rate of growth of ropes
  for(ll i=0; i<N; i++)
    scanf("%lld", &rate[i]);

  //initialize minimum and maximum days that can be possible as low and high
  ll low = 0;
  ll high = 1000000000000000000;
  ll min_days = 0;

  //Check for a mid value if it is satisfying the conditions
  while(low <= high){
    ll mid = (low + high)/2;
    ll sum = 0, flag = 0;
    for(ll i=0 ;i<N; i++){
      if(K <= (mid*rate[i] + height[i])){
        sum += (mid*rate[i] + height[i]);
        if(sum >= X){
          flag = 1;
          break;
        }
      }
    }

    /* if mid is one of the possible day, save it and 
    keep on checking for more lower values in the left half */
    if(flag == 1){
      min_days = mid;
      high = mid - 1;
    }
    /* if mid is not a possible day skip it and 
      go on searching in the right half */ 
    else
      low = mid + 1;
  }
  printf("%lld", min_days);

  return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main()
{
  ll N, X, K; cin>>N>>X>>K;
  ll height[N], rate[N];

  //input heights of ropes
  for(ll i=0; i<N; i++)
    cin>>height[i];

  //input rate of growth of ropes
  for(ll i=0; i<N; i++)
    cin>>rate[i];

  //initialize minimum and maximum days that can be possible as low and high
  ll low = 0;
  ll high = 1000000000000000000;
  ll min_days = 0;

  //Check for a mid value if it is satisfying the conditions
  while(low <= high){
    ll mid = (low + high)/2;
    ll sum = 0, flag = 0;
    for(ll i=0 ;i<N; i++){
      if(K <= (mid*rate[i] + height[i])){
        sum += (mid*rate[i] + height[i]);
        if(sum >= X){
          flag = 1;
          break;
        }
      }
    }

    /* if mid is one of the possible day, save it and 
    keep on checking for more lower values in the left half */
    if(flag == 1){
      min_days = mid;
      high = mid - 1;
    }
    /* if mid is not a possible day skip it and 
      go on searching in the right half */ 
    else
      low = mid + 1;
  }
  cout<<min_days;

  return 0;
}

import java.io.*;
import java.util.*;
import java.math.*;
public class Main {
    public static void main(String args[]){

      Scanner sc = new Scanner(System.in);
      long N = sc.nextLong();
      long X = sc.nextLong();
      long K = sc.nextLong();

      long height[] = new long[(int)N];
      long rate[] = new long[(int)N];

      //input heights of ropes
      for(int i=0; i<N; i++)
        height[i] = sc.nextLong();

      //input rate of growth of ropes
      for(int i=0; i<N; i++)
        rate[i] = sc.nextLong();

      //initialize minimum and maximum days that can be possible as low and high
      long low = 0;
      long high = 1000000000000000000L;
      long min_days = 0;

      //Check for a mid value if it is satisfying the conditions
      while(low <= high){
        long mid = (low + high)/2;
        long sum = 0, flag = 0;
        for(int i=0 ;i<N; i++){
          if(K <= (mid*rate[i] + height[i])){
            sum += (mid*rate[i] + height[i]);
            if(sum >= X){
              flag = 1;
              break;
            }
          }
        }

        /* if mid is one of the possible day, save it and 
        keep on checking for more lower values in the left half */
        if(flag == 1){
          min_days = mid;
          high = mid - 1;
        }
        /* if mid is not a possible day skip it and 
          go on searching in the right half */ 
        else
          low = mid + 1;
      }
      System.out.print(min_days);  
  }
}

Space Complexity: O(1)

[forminator_quiz id="1111"]

Leave a Reply

Your email address will not be published. Required fields are marked *