Puzzle - A surpassing problem

March 18th, 2013

Another week, another interesting puzzle. This puzzle is taken from a programming exercise posed by Martin Rem in 1988

A Surpassing Problem

By definition, a surpasser of an element of an array is a greater element to the right, so x[j] is a surpasser of x[i] if i < j and x[i] < x[j]. The surpasser count of an element is the number of surpassers. For example, the surpasser count of the string GENERATING are given by

G E N E R A T I N G

5 6 2 5 1 4 0 I 0 0

The maximum surpasser count is 6. The first occurrence of the letter E has six surpassers, namely N, R, T, I, N, and G. Rem’s problem is to compute the maximum surpasser count of an array of length n > 1 and to do so with an O(n log n) algorithm.

Click to view my solution

Not the most succint solution, but it does match the O(n logn) criteria. Infact I am using the same RangeCountTree used in the last puzzle.

Here's what I am doing (assuming word only contains capital letters):

1. Start iterating from the reverse of the string. For the current example, you first see a G so insert a range A,G in the tree. The range A,G in the tree would now have count 1. This just means that surpassers count for letters A to F is 1. Please note that A,G means letters A to F(G is excluded).

2. Now let's build this tree for NERATING. See it below:

The representation is such, that for any new character, the corresponding range in the tree would give the count of surpassers.

3. Calculate the max_surpassers while building the tree itself. So now when you see E next after NERATING, the matching range for E in the above tree is E,G -> 6. Therefore the current max_surpassers is now 6

Let's see how the tree looks for the whole string GENERATING:

Now if the string was changed to REGENERATING, you would see that the current tree has E,G -> 7 , so the max surpassers calculated would be 7

We could do the same thing for finding max surpassers in a list of numbers, only difference being that we would insert each range as (-Infinity, current_number)

Code here:

require './range_count_tree'

data = "REGENERATING"

rtree = RangeCountTree.new
max_surpassers = 0

data.reverse.each_char do |char|
  # Set range_start to A for the min possible range
  range_start = ?A.ord
  range_end = char.ord

  # Find the surpassers for the current character in the current tree
  current_max_node = rtree.find(range_end)

  # set max surpassers if current surpassers is larger
  max_surpassers = current_max_node.count if current_max_node && current_max_node.count > max_surpassers

  # Do not add this range to the tree, since we will not encounter any characters in this range
  # This is just an optimization and not necessary
  next if range_start == range_end

  # Update the current tree for the next stream of characters
  rtree.add([range_start, range_end])
end

puts "Max surpassers is #{max_surpassers}"

I think there is a much better solution which would put my verbose approach to shame with its simplicity

algorithms (5)