Concepts Used

Sorting

Difficulty Level

Hard

Problem Statement (Simplified):

  • For given two arrays, print the score of First Array and Second Array such that their difference is maximum. Scoring can be done in the following ways:
  • 2 points are awarded for the element if the element is less than K.
  • 3 points are awarded for the element if the element is greater than K.
  • K can be any value.
    > NOTE: Print the answers in the given format

See original problem statement here

First Array Score:Second Array Score.

Test Case

Input:
1
3
1 2 3
2
5 6

Output:
9:6

Explanation:
Let L=0,

In the first array, all values are greater than 0, so we get 3 points for each value in the array. Hence, the total points for the first array are 9.

In the second array, all values are greater than 0, so we get 3 points for each value in the array. Hence, the total points for the second array are 6.

So we print 9:6 as our answer.

Solving Approach :

Bruteforce Approach:

1) We can check for all values of K from 0 to maximum value of 1^{st} array, also for every value we check the score from both arrays and find the maximum difference. If found we store the scores in two variables.
2) After the whole array is iterated, we print the final scores.
3) This approach takes total O(N * M * maxValueofArray1) where N and M are sizes of first and second array respectively. As we can see above approach is very inefficient, and can’t produce answers in the given time, so we move to a new efficient approach referred from the best online learning sites for programming.

Efficient Approach:

  • Upper Bound of K: Upper Bound of K in an array is an index at which element is greater than K and element previous to it is smaller than K.
    1) If we sort both arrays, and the current element is set to K, all values before it will get score 2 each, current elements and values after each will score 3 each. So sorting makes it easier to calculate the score in constant time.
    2) After sorting, we calculate scores for both arrays for every element in the first array, where the value of K becomes the current element. Afterward, we print the least difference from all these scores.
    3) For calculating score at any element we set the value of K to the current element, first array’s sum would be 2 points for each element before the current element, and 3 points for each element after it and the current element.
    4) For sum of Second Array, we calculate Upper Bound of K in the second array, below which all elements will score 2 points each and elements from upper bound will carry 3 points each.
    5) We calculate the difference for both arrays and update values if the difference is more than the current difference.

Example

Let first array be [8,9,7,6,10]
and second array be [11,4,2,3,7],

We sort the arrays, where arrays becomes,
first array  = [6,7,8,9,10]
second array = [2,3,4,7,11]

Let the current index is 2, so the element and value of the current element is 8.

So the sum of First Array will be,
sumFirst = 2*(currentIndex) + 3*(sizeFirst-currentIndex)

Hence, 
sumFirst = 2*(2)+3*(3)
sumFirst = 13
So the sum of First Array will be,
sumFirst = 2*(currentIndex) + 3*(sizeFirst-currentIndex)

so,
sumFirst = 2*(2)+3*(3)
sumFirst = 13
Hence, for the sum of Second Array, we calculate the upper Bound of K( K is 8) in the Second Array.
upperBoundK = 4, which means the next greater element to K exists at index 4 in the Second Array.

Hence we have find the upper bound,
sum of Second Array will be,
sumSecond = 2*(upperBoundK)+3*(sizeSecond-upperBoundK)
sumSecond = 2*(4)+3*(1)
sumSecond = 11

hence, we can compare their difference and can update values.

Solutions


#include <stdio.h>
#include <limits.h>

int upperBound(int a[], int n, int x) {
    int l = 0;
    int h = n; // Not n - 1
    while (l < h) {
        int mid =  l + (h - l) / 2;
        if (x >= a[mid]) {
            l = mid + 1;
        } else {
            h = mid;
        }
    }
    return l;
}

void merge(int arr[], int start, int mid, int end){
    int left[mid-start+1];
    int right[end-mid];
    for(int i=start; i<mid+1; i++){
        left[i-start] =  arr[i];
    }
    for(int i=mid+1; i<=end; i++){
        right[i-(mid+1)] = arr[i];
    }
    int leftIndex=0, rightIndex=0, arrIndex=start;
    for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
        if(left[leftIndex]<right[rightIndex]){
            arr[arrIndex] = left[leftIndex++];
        }
        else{
            arr[arrIndex] = right[rightIndex++];
        }
    }

    while(leftIndex<=mid-start){
        arr[arrIndex++] = left[leftIndex++];
    }

    while(rightIndex<end-mid){
        arr[arrIndex++] = right[rightIndex++];
    }

}

void mergeSort(int arr[], int start, int end){
    if(end==start)
        return;
    mergeSort(arr,start,(start+end)/2);
    mergeSort(arr,((start+end)/2)+1,end);
    merge(arr,start,(start+end)/2,end);
}

int main()
{
  int test;
  scanf("%d",&test);

  while(test--){

    int n, m, pos, tempFirst, tempSecond, diff = INT_MIN, first, second;
    int a[200001], b[200001];

    scanf("%d", &n);
    for (int i = 0; i < n; i++)
      scanf("%d", &a[i]);

    scanf("%d", &m);
    for (int i = 0; i < m; i++)
      scanf("%d", &b[i]);

    mergeSort(a,0,n-1);
    mergeSort(b,0,m-1);

    a[n++] = INT_MAX;
    for (int i = 0; i < n; i++) {
      tempFirst = 3 * (n - i - 1) + 2 * i;
      pos = upperBound(b,m,a[i]-1);
      tempSecond = 3 * (m - pos) + 2 * pos;
      if (diff < tempFirst - tempSecond) {
        diff = tempFirst - tempSecond;
        first = tempFirst;
        second = tempSecond;
      }
    }
    printf("%d:%d\n", first, second);
  }
}

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

int upperBound(int a[], int n, int x) {
    int l = 0;
    int h = n; // Not n - 1
    while (l < h) {
        int mid =  l + (h - l) / 2;
        if (x >= a[mid]) {
            l = mid + 1;
        } else {
            h = mid;
        }
    }
    return l;
}

void merge(int arr[], int start, int mid, int end){
    int left[mid-start+1]={0};
    int right[end-mid]={0};
    for(int i=start; i<mid+1; i++){
        left[i-start] =  arr[i];
    }
    for(int i=mid+1; i<=end; i++){
        right[i-(mid+1)] = arr[i];
    }
    int leftIndex=0, rightIndex=0, arrIndex=start;
    for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
        if(left[leftIndex]<right[rightIndex]){
            arr[arrIndex] = left[leftIndex++];
        }
        else{
            arr[arrIndex] = right[rightIndex++];
        }
    }

    while(leftIndex<=mid-start){
        arr[arrIndex++] = left[leftIndex++];
    }

    while(rightIndex<end-mid){
        arr[arrIndex++] = right[rightIndex++];
    }

}

void mergeSort(int arr[], int start, int end){
    if(end==start)
        return;
    mergeSort(arr,start,(start+end)/2);
    mergeSort(arr,((start+end)/2)+1,end);
    merge(arr,start,(start+end)/2,end);
}

int main()
{
  int test;
  cin>>test;

  while(test--){

    int n, m, pos, tempFirst, tempSecond, diff = INT_MIN, first, second;
    int a[200001], b[200001];

    cin>>n;
    for (int i = 0; i < n; i++)
      cin>>a[i];

    cin>>m;
    for (int i = 0; i < m; i++)
      cin>>b[i];

    mergeSort(a,0,n-1);
    mergeSort(b,0,m-1);

    a[n++] = INT_MAX;
    for (int i = 0; i < n; i++) {
      tempFirst = 3 * (n - i - 1) + 2 * i;
      pos = upperBound(b,m,a[i]-1);
      tempSecond = 3 * (m - pos) + 2 * pos;
      if (diff < tempFirst - tempSecond) {
        diff = tempFirst - tempSecond;
        first = tempFirst;
        second = tempSecond;
      }
    }
    cout<<first<<":"<<second<<endl;
  }
}

import java.util.*;
import java.io.*;

public class Main {
  static int upperBound(int a[], int n, int x) {
      int l = 0;
      int h = n; // Not n - 1
      while (l < h) {
          int mid =  l + (h - l) / 2;
          if (x >= a[mid]) {
              l = mid + 1;
          } else {
              h = mid;
          }
      }
      return l;
  }

  static void merge(int arr[], int start, int mid, int end){
      int left[] = new int[mid-start+1];
      int right[] = new int[end-mid];
      for(int i=start; i<mid+1; i++){
          left[i-start] =  arr[i];
      }
      for(int i=mid+1; i<=end; i++){
          right[i-(mid+1)] = arr[i];
      }
      int leftIndex=0, rightIndex=0, arrIndex=start;
      for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
          if(left[leftIndex]<right[rightIndex]){
              arr[arrIndex] = left[leftIndex++];
          }
          else{
              arr[arrIndex] = right[rightIndex++];
          }
      }

      while(leftIndex<=mid-start){
          arr[arrIndex++] = left[leftIndex++];
      }

      while(rightIndex<end-mid){
          arr[arrIndex++] = right[rightIndex++];
      }

  }

  static void mergeSort(int arr[], int start, int end){
      if(end==start)
          return;
      mergeSort(arr,start,(start+end)/2);
      mergeSort(arr,((start+end)/2)+1,end);
      merge(arr,start,(start+end)/2,end);
  }

  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
    int test = sc.nextInt();

    while(test-->0){

      int pos, tempFirst, tempSecond, diff = -99999999, first=0, second=0;

      int n = sc.nextInt();
      int a[] = new int[n+1];
      for (int i = 0; i < n; i++)
        a[i] = sc.nextInt();

      int m = sc.nextInt();
      int b[] = new int[m];
      for (int i = 0; i < m; i++)
        b[i] = sc.nextInt();

      mergeSort(a,0,n-1);
      mergeSort(b,0,m-1);

      a[n++] = 99999999;
      for (int i = 0; i < n; i++) {
        tempFirst = 3 * (n - i - 1) + 2 * i;
        pos = upperBound(b,m,a[i]-1);
        tempSecond = 3 * (m - pos) + 2 * pos;
        if (diff < tempFirst - tempSecond) {
          diff = tempFirst - tempSecond;
          first = tempFirst;
          second = tempSecond;
        }
      }

      System.out.println(first+":"+second);
    }

  }
}

Space Complexity : O(1)

Previous post Aman Arithmetic progression
Next post Prizes

Leave a Reply

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