Last Updated on March 23, 2022 by Ria Pathak
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
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
Kfrom0to maximum value of 1st 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 totalO(N * M * maxValueofArray1)whereNandMare 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.
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 ofKbecomes the current element. Afterward, we print the least difference from all these scores.
3) For calculating score at any element we set the value ofKto 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 calculateUpperBoundofKin 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)
[forminator_quiz id="1337"]
This article tried to discuss Sorting. Hope this blog helps you understand and solve the problem. To practice more problems on Sorting you can check out MYCODE | Competitive Programming.