Блог пользователя HEIR_OF_SLYTHERIN

Автор HEIR_OF_SLYTHERIN, история, 2 года назад, По-английски

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.

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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} $$$
      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        first one

        • »
          »
          »
          »
          »
          2 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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)

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.