HEIR_OF_SLYTHERIN's blog

Help required in a question
By HEIR_OF_SLYTHERIN, history, 2 years ago, In English

Question: A global distribution company has a stack of many items in its warehouse. Each stack is stored in the form of piles. The height of some ples is very high, and the height of some piles is very low and this unevenness is causing problems in the warehouse. To solve this, the company has developed a robot which will help in arranging all the piles property. To do it the company has prepared a list of N piles which contains the total number of items in each pile, each pile in the text has been identified by a unique to ranging from 0 to (N-1). The robot will go through this list first and then remove the items from the piles in such a manner that after removing all the items, the difference between the total items of any two piles is at most K. The robot can also remove a pile completely or left a pile complimely untouched if a pile has been removed completely than that pile will automatically get deleted from the list and will not be used in farther calculation.

Werse an algorithm for the robot to calculate how many items it will remove in seal from the piles

Input: The first line of the input consists of an integer — totalPiles, representing total number of piles in the warehouse(N). The secondline of the input consists of N space seperated integers representing the total number of items in each pile The thirdline of the input consists of an Integer- represents maximum difference between any two piles(K).

Sample testcase input:
4
3 1 5 1
2
output:
2

My idea: Every time we have two choices either remove the smallest element or subtract the excessive items wrt the minimum. Can some one help me with the idea or psuedo code?

Thanking you in Advance.

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
2 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Bro it's called a "problem" not a "question"!!!!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What are the limits on N and the sizes of piles?

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    1<=totalpiles<=10^6
    1<=totalitem0,totalitem1...<=10^6
    0<=difference<=10^6

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Also, just to clarify, if I completely remove a pile, say pile $$$i$$$, then which of the following must hold:

      1. $$$| \textit{objectCount}[i-1] - \textit{objectCount}[i+1] | \leq \textit{maximumDifference} $$$, or
      2. $$$| \textit{objectCount}[i-1] - \textit{objectCount}[i] | \leq \textit{maximumDifference} $$$ and $$$| \textit{objectCount}[i] - \textit{objectCount}[i+1] | \leq \textit{maximumDifference} $$$
      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        first one

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Wait I think I misunderstood initially -- we have to have this property for all pairs of (nonempty) piles? (I initially thought it would only be for adjacent piles xD)

          → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

OK, if the property must hold between all pairs of piles, not only adjacent ones, I think this is a solution.

Suppose first we sort the sizes of the piles (the property doesn't care about the order of the piles so we can do this. Suppose the sizes are $$$v[1] ... v[N]$$$. Now suppose that we fix the size of the smallest pile that we will have after we finish our operations, say it's $$$v[i]$$$. Then we must do the following

  1. We completely remove all piles with size less than $$$v[i]$$$.
  2. All piles with size greater than $$$v[i] + \textit{maximumDifference}$$$ are set to size $$$v[i] + \textit{maximumDifference}$$$.

Now let $$$f(i)$$$ be the index of the smallest item that is greater than $$$v[i] + \textit{maximumDifference}$$$. All values of $$$f(i)$$$ can be computed in linear time by the 2-pointers technique, or in linearithmic time by binary search. For some fixed $$$i$$$ by the previous discussion the result will be

$$$ \sum_{j=1}^{i-1} v[i] + \sum_{j = f(i)}^n (v[j] - (v[i] + \textit{maximumDifference})) $$$

=

$$$ (f(i) - n + 1) (\textit{maximumDifference} - v[i])) + \sum_{j=1}^{i-1} v[i] + \sum_{j = f(i)}^n v[j] $$$

=

$$$ (f(i) - n + 1) (\textit{maximumDifference} - v[i])) + (v[1] + ... + v[n]) - (v[i] + ... + v[f(i) - 1]). $$$

And this can be calculated using, say, partial sums.

→ Reply