Denis Savchuk Denis Savchuk - 10 months ago 146
Ruby Question

Kattis phone list, time limit exceeded

Description of problem: link

My solution:

# get phone list and return true if list consistent or false if not
def consistent?(phone_list)
index = 0
last_phone = phone_list.last
phone_list.each do |phone|
index += 1
unless last_phone == phone
return true if phone.length == last_phone.length
return false if phone_list.drop(index).find { |ph| ph.start_with? phone }
# read file and parse settings
input ='', &:read).split("\n")
# input ="\n")
settings = input.slice!(0, 2).map(&:to_i)

error_t = 'Testcase numbers need to be in range 1 to 40.'
error_n = 'Phone numbers need to be in range 1 to 10000.'
error_p = 'Phonenumber is longer than 10 digits or less then 1.'
error_u = 'Phonenumbers set is not uniq'

STDERR.puts(error_t) if settings[0] < 1 || settings[0] > 40

# iterate throw input and agregate results to output
settings[0].times do
STDERR.puts(error_n) if settings[1] < 1 || settings[1] > 10_000
phone_set = input.slice!(0, settings[1])
STDERR.puts(error_u) unless phone_set.uniq.length == phone_set.length
result = consistent?(phone_set.sort_by do |phone|
STDERR.puts(error_p) if phone.length > 10 || phone.empty?
puts result ? 'YES' : 'NO'
settings[1] = input.slice!(0).to_i

I use fast-ruby. I am stuck. I will be very appreciated if you help me improve my algorithm.


The bottle neck is not Ruby, it is the algorithm. The reason of TLE is because of the following code.

return false if phone_list.drop(index).find { |ph| ph.start_with? phone }

Assume the phone number length is O(L), phone number is N, then the time complexity of previous code is O(NL), and the overall complexity of the algorithm is O(N^2L), as N is 10000, it will fail the large test.

You should try some string data structures, for this problem, Trie is a good option.

First sort phone number with length decreasing, and insert the number one by one, if some number does not create new tree nodes, it means we find a prefix, and returns false, otherwise returns true. It reduce the complexity to O(NlogN + NL). According to the problem L is at most 10, it should fit the time limit in the problem.