We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Angry Children 2
  5. Discussions

Angry Children 2

Sort by

recency

|

81 Discussions

|

  • thiruak1024
     + 0 comments
    def angryChildren(k, packets):
    packets.sort()
    mini = sys.maxsize
    for i in range(len(packets) - k + 1):
        st = i
        ed = i + k - 1
        mul = k - 1
        t = 0
        while st < ed:
            t += mul * (packets[ed] - packets[st])
            mul -= 2
            st += 1
            ed -= 1
        mini = min(t, mini)

  • apkworldsites77
     + 0 comments

    Why Children is angry?

  • svinther
     + 0 comments

    The solutions to this does not occur to me as "Dynamic Programming", yet this problem is grouped under algorithms/dynamic programming ?

  • svetlinka7878
     + 1 comment

    Hi, when I start with sample input 1 [10,4,1,2,3,4,10,20,30,40,100,200] it should be chosen packets with index 2,3,4,5 and values 1,2,3,4 => unfairness sum is 10, but my code with the same input shows packets with index 1,3,4,5 and values 4,2,3,4 => sum 7. Еven if I accept the relative difference between the value of the packages=> for example to take packets with index 0,6,8,7 with values 10,10,30,20 => unfairness sum is 70 but relative ufairness sum is 7 is still below the test output in the problem Difference between each element is 10 times more than my first example with values 4,2,3,4 but relativly the difference between 4 elements is the same.

    Where is the problem? Can I take the packeges with the same value?

  • dehaka
     + 0 comments

    O(n* log(n)), the actual algo takes O(n) time, but it requires packets to be sorted, which takes n*log(n)

    long angryChildren(int k, vector<long> packets) {
    long L = 0, current = 0;
    vector<long> partialSum = {0};
    sort(packets.begin(), packets.end());
    for (int x : packets) partialSum.push_back(partialSum.back() + x);
    for (int i=1; i < k; i++) current = current + i * packets[i] - partialSum[i];
    L = current;
    for (int i=1; i <= packets.size()-k; i++) {
        current = current + (k-1) * (packets[i+k-1] + packets[i-1]) - 2 * (partialSum[i+k-1] - partialSum[i]);
        L = min(L, current);
    }
    return L;
}