My O(K) solution for hackercup 2013, qualification round, problem 3: find the min. Ran in 0.3 seconds on my core 2 duo macbook, using Ruby 1.9.3 =update= Unfortunately the code is not fully correct. It failed on 1/20 cases.

3 - find the min.rb

require 'set'

def find_min_better3(a,b,c,r,k,n)

m = []
m << a
(k - 1).times do |k|
  m << ((b * m[k] + c) % r)
end

puts "M items generated by pseudo generator: #{m.size}"
last_k_items = m[-k..-1]
#puts last_k_items.inspect
item_index = (n % k) - (n/k)
negative_index = item_index < 0
item_index = item_index.abs % last_k_items.size
item_index = 0 - item_index if negative_index
if (!negative_index)
  puts "index: #{item_index}"
  puts "k == #{k}"  
  item_index = item_index - (k+1)
end
puts "index = #{item_index}"
k_row = generate_k_row(last_k_items, k, item_index)
puts k_row.size

return k_row[item_index]

end

def generate_k_row(m,k,negative_index)
k_row = (0..k).to_a

deleted = Set.new
puts "calculating down to: #{k + negative_index}"
start = k-1
ending = k + negative_index
(start.downto ending).each do |i|
  #100 - 90
  
  if (i % 250 == 0)
    max = start - ending
    current = i - ending
    puts "#{(((start-current-ending)/max.to_f) * 100).to_i}%"
    
  end
  #puts "#{m[i]} #{k_row[i+1]}"
  m_i = m[i]
  if (m_i > k_row[i+1])
    #let it stay
  #  puts "stay"
  else
   # puts "delete #{m[i]} and insert #{m[i]} at #{i+1}"
    if (!deleted.include?(m_i))
      k_row.delete(m_i)
      deleted << m_i
      k_row.insert(i+1,m_i)
  end
    # puts k_row.inspect
  end
end

#puts k_row.inspect
return k_row

end

data = <<EOF
20
73 26
5 8 4 54214
1000000000 100000
999999999 1 999999999 1000000000
59 26
14 19 681 59
28 21
6 5 1 85919
1000000000 1
12 7 74 12
1000000000 100000
1 1 0 2
640834505 28785
3 9 1 999946125
46 18
7 11 9 46
186 75
68 16 539 186
98 59
6 30 524 98
840698758 13331
8 7 10 999955808
45068754 29153
2 9 5 999904402
232959116 56689
4 9 1 999903057
22 21
1 4 869 22
249718282 93729
1 5 6 999917908
177 73
7 7 5 56401
218492221 46085
3 7 1 999969453
66 39
35 2 589 66
254 99
1 8 9 74990
78 51
3 5 5 51230
EOF


input = data.lines.to_a
cases = ((input.size - 1) / 2)
results = []
cases.times do |case_index|
line1 = input[(case_index * 2) + 1].chomp
line2 = input[(case_index * 2) + 2].chomp
n,k = line1.match(/(\d+) (\d+)/).captures.map{|s|s.to_i}
a,b,c,r = line2.match(/(\d+) (\d+) (\d+) (\d+)/).captures.map{|s|s.to_i}
puts "Case #{case_index + 1}"
puts "a:#{a} b:#{b} c:#{c} r:#{r}"
puts "n:#{n} k:#{k}"
#result = find_min(a,b,c,r,k,n)#WATCH IT: K BEFORE N
#result_2 = find_min_better(a,b,c,r,k,n)
#result_3 = find_min_better2(a,b,c,r,k,n)
result_4 = find_min_better3(a,b,c,r,k,n)
#puts "m[0] = #{a}"
#puts "m[i] = (#{b} * m[i-1] + #{c}) % #{r}"
#puts "(((#{a} * #{b}) + #{c}) % #{r})/#{a} = #{(((a * b) + c)%r).to_f / a}"
#puts "Case \##{case_index + 1}: #{result}"
#puts "Case \##{case_index + 1}: #{result_2}"
#results << "Case \##{case_index + 1}: #{result_3}"
results << "Case \##{case_index + 1}: #{result_4}"



end
puts
puts
puts results.join("\n")
# file = File.new("3-output.txt", "w")
# file << results.join("\n")
# file.close