20 months ago

rahul • 0

Prayagraj

can you specify your college?

1 day ago

Suryansh Rishit • 0

Mysuru

Minimize Total Network Lag Between Data Centers and Servers

Approach / Steps:

1. Understand the Goal:
   You are given n data centers and n servers, placed on a 1D number line.
   You need to pair each data center with exactly one server such that the total lag (absolute difference) is minimized.

2. Key Insight:
   This is a classic case of minimum sum of absolute differences between two arrays with 1:1 mapping.
   To minimize the sum:
   ➤ Sort both arrays
   ➤ Pair i-th element from center[] with i-th element from destination[].

3. Why this works?
   Based on the Rearrangement Inequality, pairing sorted elements minimizes the sum of absolute differences.

4. Steps:

   • Read input arrays center[] and destination[].

   • Sort both arrays.

   • For each index i from 0 to n-1, compute abs(center[i] - destination[i]).

   • Sum up all those values and print the result.

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

int main() {
    int n;
    cin >> n;
    vector<int> d_cen(n), des(n);

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

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

    sort(d_cen.begin(), d_cen.end());
    sort(des.begin(), des.end());

    long long totalLag = 0;
    for (int i = 0; i < n; i++) {
        totalLag += abs(d_cen[i] - des[i]);
    }

    cout << totalLag << endl;
}

Time Complexity (TC):

• Sorting both arrays: O(n log n)

• Computing lag: O(n)

• Total TC = O(n log n)

Space Complexity (SC):

• Using O(n) space for two arrays.

• Total SC = O(n)

1 day ago

Suryansh Rishit • 0

Mysuru

K-Spike (Problem 2)

Approach

The key insight is to efficiently count elements smaller than each array element in two ranges:

1. Left range: For each index i, count elements in [0, i-1] that are smaller than arr[i]
2. Right range: For each index i, count elements in [i+1, n-1] that are smaller than arr[i]

Algorithm Steps:

1. Process left to right: Use a multiset to maintain elements seen so far. For each position i:
   • Count elements in multiset that are smaller than arr[i] using lower_bound()
   • Store this count in left[i]
   • Insert arr[i] into multiset
2. Process right to left: Clear multiset and repeat the process in reverse:
   • For each position i from n-1 to 0, count smaller elements in multiset
   • Store this count in right[i]
   • Insert arr[i] into multiset
3. Count k-Spikes: For each index i, check if both left[i] ≥ k and right[i] ≥ k

#include<bits/stdc++.h>

using namespace std;


int main(){

    int n;
    cin >> n;
    vector<int> arr(n);

    for(int i = 0 ; i < n;i++){
        cin >> arr[i];
    }
    multiset<int> s;
    int k;
    cin >> k;
    vector<int> left(n,0),right(n,0);
 
    for (int i = 0; i < n; ++i) {
        left[i] = distance(s.begin(), s.lower_bound(arr[i]));
        s.insert(arr[i]);
    }

    s.clear();  
 
    for (int i = n - 1; i >= 0; --i) {
        right[i] = distance(s.begin(), s.lower_bound(arr[i]));
        s.insert(arr[i]);
    }
 
    int cnt = 0;
    for (int i = k; i < n-k; ++i) {
        cout << arr[i] << endl;
        cout << left[i] << "  " << right[i] << endl;
        if (left[i] >= k && right[i] >= k)
            cnt++;
    }
    cout << cnt << endl;

}
 

Time Complexity (TC):

O(n log n) - Two passes through array with multiset insert and lower_bound operations

Space Complexity (SC):

O(n) - For multiset, left array, right array, and input storage