Hey everyone, I came across this solution and I'm curious if it can be implemented on my website. The website in question is Potlaki Export Group, where we specialize in exporting premium-quality products like poultry, seafood, foods & beverages, cosmetics, chemicals, and agricultural produce. We're always looking for innovative ways to enhance our services and ensure customer satisfaction. Would this solution work well with our current setup? Any insights or advice would be greatly appreciated. Thanks in advance!

First of all - please change return type to long, some test cases are meant to return number bigger than 32 bits

Second of all - I gave up for last 3 cases remaining xDD Exceeded time limits on them.. I reckon I need to something more with the rotation..

Here is my C++ solution:

long insertionSort(vector arr) {`

long shifts = 0;
int st_tail_idx = 1;

while (st_tail_idx < arr.size()) {

    int elem = arr[st_tail_idx];
    int tmp_shift = 0;
    int breaker_elem = 0;

    int low = 0;
    int high = st_tail_idx;
    while (low <= high) {
        int mid = (low + high) / 2;
        int guess = arr[mid];
        if (guess < elem) {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    breaker_elem = arr[low];

    tmp_shift = st_tail_idx - low;
    int shift_correction = 0;
    if (breaker_elem == elem) {
        while (low + shift_correction < arr.size() - 1 && arr[low + shift_correction] == breaker_elem) {
            shift_correction++;
        }
    }

    tmp_shift -= shift_correction;
    if (tmp_shift > 0) {

        int new_pos = st_tail_idx - tmp_shift;

        int elems_pack = 1;
        if (st_tail_idx < arr.size() - 1) {
            int last_elem = arr[st_tail_idx + 1];
            for (int i = st_tail_idx + 1; i < arr.size(); i++) {

                if (arr[i] < elem || arr[i] >= breaker_elem || arr[i] < last_elem) {
                    break;
                }
                last_elem = arr[i];

                elems_pack++;
            }
        }

        std::rotate(arr.begin() + new_pos, arr.begin() + st_tail_idx, arr.begin() + st_tail_idx + elems_pack);
        shifts += tmp_shift * elems_pack;

        st_tail_idx += elems_pack;
    }
    else {
        st_tail_idx++;
    }
}

return shifts;

} `

Use long Instead of int

If you are using the mergesort's count inversion method then kindly use long for you answer (counter variable basically) instead of int. I was stuck since last 2 hours and then I got to know that long is acceptable instead of int in answer. So try your solution with long If you think your count inversion solution is correct.

Idk why insertion sort that test on very large array or my skill issue. i was trying binany search on my insertion sort to improve speed, still timeout 4 tests. Im not sure i can use orther sort like merge sort or quick sort. so this is my code.

const binary_search = (a: number[], r: number, n: number): number => {
    r = Math.max(0, Math.min(r, a.length - 1)) - 1
    let l = 0
    while (l <= r) {
        let m = Math.floor((l + r) / 2)
        if (n < a[m]) r = m - 1
        else l = m + 1

    }
    return l;
}
function insertionSort(a: number[]): number {
    let c = 0

    for (let i = 1; i < a.length; i++) {
        let x = a[i]
        let xi = binary_search(a, i, x)

        if (xi != i) {
            for (let j = i - 1; j >= xi; j--) { a[j + 1] = a[j]; c++ }
            a[xi] = x
        }
    }

    return c
}

Implement a prototype of a UDP network protocol.

There is a 2d array of size n x 2, requests. At time t = requests[i][0], requests[i][1] packets are to be sent over the network. The network can hold at most max_packets packets in the pipeline. It delivers the data to the client at rate packets per second, i.e. rate packets are removed from the queue and delivered to the client every second.

If the number of packets exceeds max_packets at any time, the packets remaining at that time are dropped.

Given the array requests, and the integers, max_packets, and rate, find the total number of packets that are dropped.

Example

Suppose requests = [[1, 8], [4, 9], [6, 7]], rate = 2, and max_packets= 10.