title: how to calculate the minimum unfairness sum of a list
body: <p>I have tried to summarize the problem statement something like this::</p>
  <p>Given <code>n</code>, <code>k</code> and an array(a list) <code>arr</code> where <code>n = len(arr)</code> and <code>k</code> is an <code>integer</code> in <code>set (1, n) inclusive</code>.</p>
  <p>For an array (or list) <code>myList</code>, The Unfairness Sum is defined as the <code>sum</code> of the absolute differences between all possible pairs (combinations with 2 elements each) in <code>myList</code>.</p>
  <p><strong>To explain</strong>: if <code>mylist = [1, 2, 5, 5, 6]</code> then <em>Minimum unfairness sum</em> or MUS. Please note that elements are considered unique by their <code>index</code> in list not their values</p>
  <pre><code>MUS = |1-2| + |1-5| + |1-5| + |1-6| + |2-5| + |2-5| + |2-6| + |5-5| + |5-6| + |5-6|
  </code></pre>
  <p>If you actually need to look at the problem statement, It's <a href="https://hackerrank-challenge-pdfs.s3.amazonaws.com/1049-angry-children-2-English?AWSAccessKeyId=AKIAR6O7GJNX5DNFO3PV&amp;Expires=1599467959&amp;Signature=Ii5wb%2BCp6NkNYETH0unOyAmh95M%3D&amp;response-content-disposition=inline%3B%20filename%3Dangry-children-2-English.pdf&amp;response-content-type=application%2Fpdf" rel="nofollow noreferrer">HERE</a></p>
  <p><strong>My Objective</strong></p>
  <p>given <code>n, k, arr</code>(as described above), find the <code>Minimum Unfairness Sum</code> out of  all of the unfairness sums of sub arrays possible with a  constraint that each <code>len(sub array) = k</code> [which is a good thing to make our lives easy, I believe :) ]</p>
  <p><strong>what I have tried</strong></p>
  <p>well, there is a lot to be added in here, so I'll try to be as short as I can.</p>
  <p><em><strong>My First approach</strong></em> was this where i used <code>itertools.combinations</code> to get all the possible combinations and <code>statistics.variance</code> to check its <code>spread of data</code> (yeah, I know I'm a mess).<br />
  Before you see the code below, Do you think these variance and unfairness sum are perfectly related (i know they are strongly related) i.e. the sub array with <code>minimum variance</code> has to be the sub array with <code>MUS</code>??</p>
  <p>You only have to check the <code>LetMeDoIt(n, k, arr)</code> function. If you need <a href="https://stackoverflow.com/help/minimal-reproducible-example">MCVE</a>, check the second code snippet below.</p>
  <pre><code>from itertools import combinations as cmb
  from statistics import variance as varn
  
  def LetMeDoIt(n, k, arr):
      v = []
      s = []
      subs = [list(x) for x in list(cmb(arr, k))]  # getting all sub arrays from arr in a list
  
      i = 0
      for sub in subs:
          if i != 0:
              var = varn(sub)  # the variance thingy
              if float(var) &lt; float(min(v)):
                  v.remove(v[0])
                  v.append(var)
                  s.remove(s[0])
                  s.append(sub)
              else:
                  pass
  
          elif i == 0:
              var = varn(sub)
              v.append(var)
              s.append(sub)
              i = 1
  
      final = []
      f = list(cmb(s[0], 2))  # getting list of all pairs (after determining sub array with least MUS)
      
      for r in f:
          final.append(abs(r[0]-r[1]))  # calculating the MUS in my messy way
  
      return sum(final)
  </code></pre>
  <p>The above code works fine for <code>n&lt;30</code> but raised a <code>MemoryError</code> beyond that.
  In Python chat, Kevin suggested me to try <code>generator</code> which is <code>memory efficient</code> (it really is), but as generator also generates those combination on the fly as we <code>iterate</code> over them, it was supposed to take over 140 hours (:/) for n=50, k=8 as estimated.</p>
  <p>I posted the same as a question on SO <a href="https://stackoverflow.com/q/63698650/10145519">HERE</a> (you might wanna have a look to understand me properly - it has discussions and an answer by fusion which takes me to my second approach - a better one(i should say fusion's approach xD)).</p>
  <p><em><strong>Second Approach</strong></em></p>
  <pre><code>from itertools import combinations as cmb
  
  def myvar(arr):   # a function to calculate variance
      l = len(arr)
      m = sum(arr)/l
      return sum((i-m)**2 for i in arr)/l
  
  def LetMeDoIt(n, k, arr):
      sorted_list = sorted(arr)  # i think sorting the array makes it easy to get the sub array with MUS quickly
      variance = None
      min_variance_sub = None
      
      for i in range(n - k + 1):
          sub = sorted_list[i:i+k]
          var = myvar(sub)
          if variance is None or var&lt;variance:
              variance = var
              min_variance_sub=sub
              
      final = []
      f = list(cmb(min_variance_sub, 2))  # again getting all possible pairs in my messy way
  
      for r in f:
          final.append(abs(r[0] - r[1]))
  
      return sum(final)
  
  def MainApp():
      n = int(input())
      k = int(input())
  
      arr = list(int(input()) for _ in range(n))
  
      result = LetMeDoIt(n, k, arr)
  
      print(result)    
  
  if __name__ == '__main__':
      MainApp()
  </code></pre>
  <p>This code works perfect for <code>n up to 1000</code> (maybe more), but terminates due to <code>time out</code> (5 seconds is the limit on online judge :/ ) for n beyond <code>10000</code> (the biggest test case has <code>n=100000</code>).</p>
  <p>=====</p>
  <p>How would you approach this problem to take care of all the test cases in given time limits (5 sec) ? (problem was listed under <code>algorithm</code> &amp; <code>dynamic programming</code>)</p>
  <p>(for your references you can have a look on</p>
  <ol>
  <li><a href="https://paste.atilla.org/paste/0K9PFA" rel="nofollow noreferrer">successful submissions</a>(py3, py2, C++, java) on this problem by other candidates - <strong>so that you can
  explain that approach for me and future visitors</strong>)</li>
  <li><a href="https://paste.atilla.org/paste/RYUP00" rel="nofollow noreferrer">an editorial</a> by the problem setter explaining how to approach the question</li>
  <li><a href="https://paste.atilla.org/paste/31PSXK" rel="nofollow noreferrer">a solution code</a> by problem setter himself (py2, C++).</li>
  <li><a href="https://anonfiles.com/f9K02eSbo8/angry-children-2-testcases_zip" rel="nofollow noreferrer">Input data (test cases) and expected output</a></li>
  </ol>
  <hr />
  <p>Edit1 ::</p>
  <p>For future visitors of this question, the conclusions I have till now are,<br />
  that <code>variance</code> and <code>unfairness sum</code> are not <code>perfectly</code> related (they are <code>strongly</code> related) which implies that among a lots of lists of integers, a list with <code>minimum variance</code> doesn't always have to be the list with <code>minimum unfairness sum</code>. If you want to know why, I actually asked that as a separate question on math stack exchange <a href="https://math.stackexchange.com/q/3817341/822711">HERE</a>  where one of the mathematicians proved it for me xD (and it's worth taking a look, 'cause it was unexpected)</p>
  <p>As far as the question is concerned overall, you can read answers by archer &amp; Attersson below (still trying to figure out a naive approach to carry this out - it shouldn't be far by now though)</p>
  <hr />
  <p>Thank you for any help or suggestions :)</p>