ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1044. Lucky Tickets. Easy!

Ruby non, C++ oui
Posted by Donald Cameron 14 Mar 2015 08:08
For my first try I wrote this:

def sum_of_digits(n)
sum = 0
while (n > 0)
sum += n % 10
n /= 10
end
sum
end

num_digits = gets.chomp.to_i

exponent = num_digits/2
divisor = 10**exponent

limit = (10**num_digits) - 1
total = 0

0.upto(limit) do |cur|
upper = cur / divisor
lower = cur % divisor
total += 1 if sum_of_digits(upper) == sum_of_digits(lower)
end

puts total

# eof

For 2, 4 and 6 digits it got the requisite answers of 10, 670, and 55252.  There was a bit of a pause while it crunched away at the 6-digit case, though.

For 8 digits it … well, I let it run and went to do something else.  Then I had the bright idea to time it (on mac OS X, using the time command):

4816030

real    1m42.596s
user    1m34.222s
sys    0m1.837s

The right answer, but the last time I checked, one minute anything was greater than two seconds.  What to do?

It’s pretty clear that calling sum_of_digits a bunch more times than necessary is the biggest problem. For try #2, I precomputed the sums and stuffed them into an array, and indexed the array in place
of calling sum_of_digits in the main loop.  Here’s the result:

time ruby lucky.rb < t8.txt
4816030

real    0m19.176s
user    0m18.017s
sys    0m0.313s

A better than 80% speedup.  Most times I would kill for that, but I still need to lose 95% of the remaining run time.  How to do it?

I checked … initializing the array of sums takes virtually no time, even if I write out the entire array contents to a file.

So the main loop is killing me, and unfortunately I need a dramatic change of algorithm but I
don’t see one. So …

1. Recode in C or C++
2. Hell if I know

Taking option 1, I got Accepted, with run times around 1.1 seconds or so for 8 digits.  It's a straightforward translation to C++, very brute force.