Mr. Moneybag's Money Piles

Question

Mr. Moneybags is a very rich man. He has an assistant Mr. Perfect, who one day, got very mad, and shredded some of Mr. Moneybag’s $100 bills! Mr. Moneybags decided to punish Mr. Perfect.

Mr. Moneybags tells Mr. Perfect to stack his money into different piles.

He starts with N (1 <= N <= 1,000,000, N odd) empty stacks, numbered 1..N. Mr. Moneybags then gives him a sequence of K instructions (1 <= K <= 25,000), each of the form "A B", meaning that Mr. Perfect should add one new bill to the top of each stack in the range A to B, inclusive. For example, if Mr. Perfect is told "11 13", then he should add a bill to each of the stacks 11, 12, and 13.

After Mr. Perfect finishes stacking the money according to his instructions, Mr. Moneybags would like to know the median height of his N stacks -- that is, the height of the middle stack if the stacks were to be arranged in sorted order (N is odd, so this stack is unique). Please write an efficient program to help Mr. Perfect determine the answer to Mr. Moneybag’s question.

INPUT FORMAT:

• Line 1: Two space-separated integers, N K.
• Lines 2..1+K: Each line contains one of Mr. Moneybag’s instructions in the form of two space-separated integers A B (1 <= A <= B <= N).

SAMPLE INPUT:

7 4                                                                             
5 5                                                                             
2 4
4 6
3 5

INPUT DETAILS:

There are N=7 stacks, and Mr. Moneybags issues K=4 instructions. The first instruction is to add a bill to stack 5, the second is to add a bill to each stack from 2..4, etc.

OUTPUT FORMAT:

• Line 1: The median height of a stack after Mr. Perfect completes the instructions.

SAMPLE OUTPUT:

1

The winner is the one with the "most efficient" algorithm. So, if someone posts an O(N) solution, then it will beat any O(N^2). If there is a tie, aka, two or more people who post an O(N) solution, for example, then whoever has is the shortest code (code-golfed) wins.

So, your purpose is to write a efficient algorithm, and to prevent possible ties with other people, try to code-golf it as well.

Another thing, the input is to be read from a file and the output must be written to a file.

EDIT Also, the solution must be returned under or equal to 2 seconds. If it is not, you will receive a T. A wrong answer is an X. Which means, if no one can get it under time, then the most efficient algorithm sigh score of T can win.

EDIT #2 Here are some more samples:

1. http://pastebin.com/x88xAyPA
2. http://pastebin.com/y6Cuxm7W
3. http://pastebin.com/kgbeiQtd

EDIT #3 Bonus: (subtract 100 chars from total)

Solve this under 2 seconds :)

1. http://pastebin.com/3uT9VSzv

Answer 1

O(K log N), many characters of Python

Edit: Improved by replacing merge sort with radix sort.

This is an improvement over my previous answer, but I'm posting it separately because it's a different strategy, and so the post doesn't get super-long.

This is now optimal because simply reading the input can take 2*K*lg N time in the worst case -- 2*K numbers each with lg N bits.

The goal is to have minimal dependence on N. To do this, rather than store counts for each pile index, we realize that all piles in a contiguous cluster unaffected by the endpoints of any interval must have the same counts. So, if we see that an interval starts with 5, and there's no changes until 15, then those 10 piles have the same value.

Each change in pile size from a pile to the next one is caused by an interval starting or ending. We call these "events". Each event increases or decreases the current pile size by 1. If, from one event to the next, there's some number of piles, each of those piles has the current size.

We extract the 2*k events from the intervals, and sort them using a radix sort, taking advantage of the values being 1 through N. This take takes O(K*log(N)) because the numbers have O(lg N) bits.

We then run over the events, and for each one, update the list of counts to the previous event, which requires adding a number up to N (so lg N bits). This takes O(log(N)) per step, and so O(K*log(N))

Finally, having gotten the counts of the pile sizes, it's easy to quickly find the median by computing the cumulative number of piles up to a given size (or, rather, we subtract it from our desired count). This also takes O(K*log(N)).

The algorithm does the huge test case in under a second.

The code (ungolfed) is below with comments.

# Process input
def get_ints(line):
 vals = line.split()
 return (int(vals[0]),int(vals[1]))

s = input()

lines = s.split("\n")
N,K = get_ints (lines[0])
intervals = [get_ints(line) for line in lines[1:]]

mins,maxes=map(list,zip(*intervals))

#Each event will represent an increase or decrease of a pile from the previous one
#Each min increases the count by 1
#Each max causes the count to decrease by 1, starting with the next pile
events = [(a,1) for a in mins] + [(b+1,-1) for b in maxes]
events.append((N+1,0))

#Do a radix sort on the first element of each pair 
#Each number has O(lg N) digits, so this takes O(k lg N) 
events.sort()

#Count of the number of piles of each size
#pile_sizes[size] counts the number of piles of that size
pile_sizes = [0]*K
cur_pile = 1
cur_size = 0

#For each event, we track the pile size after the event
#Then, on the next event, we know there were some number of piles of that size
#The number of piles equals the distance between events
#Multiple events on the same pile have zero distance and don't affect the counts
for event in events:
 event_pile = event[0]
 piles_current_size = event_pile - cur_pile
 pile_sizes[cur_size] += piles_current_size
 cur_pile = event_pile
 cur_size += event[1]

#Get the i_th largest pile size from a list of pile size counts
def get_order_stat(counts,i):
 for val in range(len(counts)):
  cur_count = counts[val]
  if i<cur_count:
   return val
  i-=cur_count
 return None

median = get_order_stat(pile_sizes,N//2)

print(median)

Answer 2

O((N + K) * log(N)), many chars of Python

(See my improved solution.)

Edit: I realized that I wasn't accounting for operations with numbers taking log(N) time. For example, I think the linear time median, despite its name, is actually N log N once you take into account the time to compare numbers bit by bit.

Edit: Improved sorting. Thanks to isaacg.

The idea is to make a list of the size of each pile 1...N, and then take the median of this list. The key is to obtain the size of a pile from the size of the pile before by adding the number of intervals that start at that value, and subtracting the number that end at the previous value. By sorting the lists of interval-starts and interval-ends, we can quickly query how many intervals start and end.

See the code for more detailed comments. I didn't golf it.

The code has no problem with the huge test case, taking <1 second on my machine.

# Process input
def get_ints(line):
 vals = line.split()
 return (int(vals[0]),int(vals[1]))

s=input()

lines = s.split("\n")
N,K = get_ints (lines[0])
intervals = [get_ints(line) for line in lines[1:]]

# Separate out the starts and ends of the intervals. 
# Sort each, which takes O((K + N) * log(N)) with a counting sort.
mins,maxes=map(list,zip(*intervals))
mins.sort()
maxes.sort()

#Make a running list of the sizes of each pile
size_list = []
cur_size = 0
for i in range(1,N+1):
 #Update the size of the next pile by adding one for each interval that starts here
 #Each number in min can only can one update, so this contributes O(k) total
 while mins and mins[0]==i:
  mins.pop(0)
  cur_size+=1
 #Likewise, subtract one for each interval that ended at the previous number
 while maxes and maxes[0]==i-1:
  maxes.pop(0)
  cur_size-=1
 size_list.append(cur_size)

#Now, we compute the median of size_list
#The naive median algorithm sorts and take the middle element, taking O(N*log(N)) time
#But, there's a linear-time algorithm to select the median (or any order statistic) of    a list
linear_time_median = lambda L: select(L, 0, len(L), len(L)//2)

#I didn't want to write my own linear median algorithm, as it standard but long. 
#So, I use the linear median code from https://gist.github.com/boyers/7233877
median = linear_time_median(size_list)

print(median)

Here's the code for linear-time-median from https://gist.github.com/boyers/7233877.

#### Code credit: https://gist.github.com/boyers/7233877

# partition A[p:r] in place about x, and return the final position of the pivot
def partition(A, p, r, x):
  # find the index of the pivot
  i = -1
  for j in range(p, r):
    if A[j] == x:
      i = j
      break

  # move the pivot to the end
  if i != -1:
    t = A[r - 1]
    A[r - 1] = A[i]
    A[i] = t

  # keep track of the end of the "less than" sublist
  store_index = p

  # iterate
  for j in range(p, r - 1):
    if A[j] < x:
      t = A[j]
      A[j] = A[store_index]
      A[store_index] = t
      store_index += 1

  # put the pivot in its final place
  if i != -1:
    t = A[r - 1]
    A[r - 1] = A[store_index]
    A[store_index] = t

  # return the store index
  return store_index

# find the ith biggest element in A[p:r]
def select(A, p, r, i):
  # make a copy of the array
  A = A[:]

  # divide the n elements of A into n / 5 groups
  groups = [[]] * (((r - p) + 4) // 5)
  for x in range(p, r):
    groups[(x - p) // 5] = groups[(x - p) // 5] + [A[x]]

  # find the median of each group
  medians = [sorted(l)[(len(l) - 1) // 2] for l in groups]

  # find the median of medians
  if len(medians) == 1:
    median_to_rule_them_all = medians[0]
  else:
    median_to_rule_them_all = select(medians, 0, len(medians), (len(medians) - 1) // 2)

  # partition A around the median of medians
  partition_index = partition(A, p, r, median_to_rule_them_all)

  # base case
  if p + i < partition_index:
    return select(A, p, partition_index, i)
  if p + i > partition_index:
    return select(A, partition_index + 1, r, p + i - partition_index - 1)
  return A[p + i]

Answer 3

C#

307 273 281 283 characters. A complexity of O(K) I'm not sure but could be O(K*N).

void m() 
{ 
    var r = new StreamReader("in.txt"); 
    var m = new int[int.Parse(r.ReadLine().Split(' ')[0]) + 1]; 
    string l; 
    while ((l = r.ReadLine()) != null) 
    { 
        var t = l.Split(' '); 
        for (var i = int.Parse(t[0]); i <= int.Parse(t[1]); i++) 
        { 
            m[i]++; 
        } 
    } 
    Array.Sort(m); 
    File.WriteAllText("out.txt", m[m.Length / 2].ToString()); 
}

The character count is after deleting all new lines/unnecessary whitespaces...

PS: Your input example has an even amount of stacks, which violates your rule.

PPS: I answered the wrong question in my first try.

Second version little bit bigger but faster. If compiled without debug symbols (ctrl + f5 in visual studio 2013) 2.5 seconds for the last example.

But 318 characters...

void m()
{
    var r=new StreamReader("in.txt");
    var m=new int[int.Parse(r.ReadLine().Split(' ')[0])];
    string l;
    while((l=r.ReadLine())!=null)
    {
        var t = l.Split(' ');
        var e=Array.ConvertAll(t,int.Parse);
        m=m.Select((c,i)=>i>=e[0]&i<=e[1]?++m[i]:m[i]).ToArray();
    }
    Array.Sort(m);
    File.WriteAllText("out.txt",m[m.Length/2].ToString());
}

Answer 4

C# - 374 Characters

Shamelessly lifted from Armin, and probably possible to micro-optimize even further. However, I saw his post and thought "Low hanging fruit" so hey, may as well.

void Main(){var r=new StreamReader("i");var m=new int[f(r.ReadLine())[0]];string l;while((l=r.ReadLine())!=null){var t=f(l);for(var i=t[0];i<=t[1];i++){m[i]++;}}Array.Sort(m);File.WriteAllText("o",m[m.Length/2].ToString());}static int[]f(string n){int[]b=new int[2];int r=0;for(int i=0;i<n.Length;i++){char c=n[i];if(c!=32){r=10*r+(c-48);}else{b[0]=r;r=0;}}b[1]=r;return b;}

Ungolfed

void Main()
{
    var r = new StreamReader("i"); 
    var m = new int[f(r.ReadLine())[0]]; 
    string l; 
    while ((l = r.ReadLine()) != null) 
    { 
        var t = f(l);
        for (var i = t[0]; i <= t[1]; i++) 
        { 
            m[i]++; 
        } 
    } 
    Array.Sort(m);
    File.WriteAllText("o", m[m.Length/2].ToString());
}
static int[] f(string n)
{
    int[] b = new int[2];
    int r = 0;
    for (int i = 0; i < n.Length; i++)
    {
        char c = n[i];
        if (c != 32)
        {
            r = 10 * r + (c - 48);
        }
        else
        {
            b[0] = r;
            r=0;
        }
    }
    b[1] = r;
    return b;
}

Using LinqPad and the third pastebin link from the op, running a GC/warmup, and taking the average of 10 runs I get the following comparison times:

• Armin first answer: 3229ms average
• Armin second answer: 2601ms average
• My answer: 18ms average

First submission so I can't wait to see how badly the more seasoned posters can beat this!

Also, now that the bonus was added I can test mine against that! However, sadly over an average of 10 runs on my computer it takes 4293ms to come up with 9314. So I have quite a ways to go yet.

Answer 5

Lua, 247 bytes

The program constructs a frequency table and finds the median from that. I don't know what that would be in the complexity notation. For the sake of code-golfing, the output is appended to the end of the input file. If that's a problem, I'll change it.

s="*n"f=io.open(--[[FILE NAME--]],"a+")t,i=f:read(s,s)b={}c={}d={}for x=1,i do
y,z=f:read(s,s)for w=y,z do
q=b[w]or 0
if c[q]then
c[q]=c[q]-1
end
b[w]=q+1
c[q+1]=1+(c[q+1]or 0)end
end
n=0
for _,i in pairs(c)do
for w=1,i do
d[n]=_
n=n+1
end
end
f:write(d[#d/2])f:flush()

Ungolfed

s="*n"
f=io.open("input.txt")
t,i=f:read(s,s)
b={}
c={}
d={}
for x=1,i do
  y,z=f:read(s,s)
  for w=y,z do
    q=b[w]or 0
    if c[q]then
      c[q]=c[q]-1
    end
    b[w]=q+1
    c[q+1]=1+(c[q+1]or 0)
  end
end
n=0
for _,i in pairs(c)do
  for w=1,i do
    d[n]=_
    n=n+1
  end
end
f:write(d[#d/2])
f:flush()