cholerikasi's blog

By cholerikasi, 9 years ago, In English

In the previous contest I experimented with Ruby and was surprised how quickly you run into TLE (Time Limit Exceeded) when dealing with larger inputs.

Example: 157C — Message (#110 Div-2 Problem C)

My solution:

orig = gets.chomp
targ = gets.chomp

plh = []
targ.length.times{plh << '*'}
plh_str = plh.join
orig = [plh_str, orig].join

max_matches = 0
(0..orig.length-1).each{|i|
  matches = 0
  (0..targ.length-1).each{|j|
    matches += 1 if orig[i+j] == targ[j]
  }
  max_matches = matches if matches > max_matches
}
puts targ.length - max_matches

The big caveat is that looping takes a long time (actually, everything seems to take a long time). For example having 2M iterations (which is certainly possible for this problem scenario) takes already 0.5 seconds. The conditional increment in the solution above adds another 1.5 seconds.

I suppose that the problem cannot be solved with Ruby under the time constraints (if you disagree I would love to see a solution!).

My general experience is, that Ruby can be very convenient for the Div-2 A and B problems (solutions with only a couple of lines of code) but for the other ones which require more processing it is necessary to switch to languages with higher performance.

Read more »

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it