On Sat, 5 May 2018 13:13:17 -0700 (PDT)
"'[email protected]' via Google Code Jam"
<[email protected]> wrote:
> Thanks a lot! I will try to keep those optimzations in mind when I
> try again next year.
>
> I have the feeling that in previous years (when we just computed and
> submitted the output file) as long as you got the optimal asymptotic
> complexity (like sth in O(NK) in this case), you were guaranteed to
> solve the inputs in the appropiate time.
>
> My guess is now that since we now just have to submit a program, the
> available time for the large datasets is much less than 8 min, so we
> have much less time. So the N is much smaller in our O(NK) Algorithm
> and that sadly makes sure that the constant in front of the NK
> matters much more.
>
> And that constant seems to be quite high for python.
Hi!
I have already complained earlier about the unfair setup for Ruby
and Python programming languages after the Qualification round:
https://groups.google.com/d/msg/google-code/nBxLsGD9XFQ/sSOOzaUXBwAJ
Now your code is an even better example. I have converted it to Ruby
and tried to do some tests and benchmarks with it. First, a Ruby
conversion of your original solution:
INF = 2 ** 63 - 1
t = gets.to_s.to_i
1.upto(t) do |casenum|
n = gets.to_s.to_i
ww = gets.to_s.strip.split.map {|x| x.to_i }
d = [INF] * 140
d[0] = 0
ww.each do |w|
h = d.size - 1
while d[h] > 6 * w
h -= 1
end
h.downto(0) {|h2| d[h2 + 1] = [d[h2 + 1], d[h2] + w].min }
end
mh = d.map.with_index {|x, i| x < INF ? i : 0 }.max
puts "Case ##{casenum}: #{mh}\n"
end
And then Xiongqi ZHANG's variant, also converted to Ruby/Crystal and
adapted a bit to use 64-bit floating point numbers for the values in
the 'd' array:
t = gets.to_s.to_i
1.upto(t) do |casenum|
n = gets.to_s.to_i
ww = gets.to_s.strip.split.map {|x| x.to_i }
d = [-1.0] * 141
d[0] = 0.0
mh = 0
ww.each do |w|
h = mh
while d[h] > 6.0 * w
h -= 1
end
mh += 1 if h == mh
h.downto(0) do |h2|
if d[h2 + 1] < 0 || d[h2 + 1] > d[h2] + w
d[h2 + 1] = d[h2] + w
end
end
end
puts "Case ##{casenum}: #{mh}\n"
end
The first variant passes small set, but times out on the large set
if submitted to the GCJ server in the practice mode. The second
variant passes all tests, just like its Python counterpart.
Then I tried to run some benchmarks on my own 8 years old desktop
computer with a 2.8GHz Intel Core i7 processor. Using the output
of the following script as input:
puts 100
100.times do |i|
n = i < 6 ? 10 ** 5 : rand(499) + 2
puts n
puts n.times.map { rand(10 ** 9) + 1 }.join(" ")
end
Benchmarks using different compilers and interpreters for your
original solution produce the following results:
Python 2.7.14 = 31.2s
Ruby 2.2.9 = 21.3s
PyPy 5.10.0 = 0.5s
And the Xiongqi ZHANG's variant:
Python 2.7.14 = 13.0s
Ruby 2.2.9 = 7.9s
PyPy 5.10.0 = 0.4s
Crystal 0.24.2 = 0.2s
Considering that the GCJ server has a 15 seconds time limit when
judging solutions, looks like the performance of their hardware is
very similar to mine (the solution which runs 21.3s on my computer
timeouts on the GCJ server and the solution which runs 13.0s on my
computer passes on the GCJ server).
PyPy is a high performance Python implementation, which uses JIT.
And Crystal is a high performance native compiler for a statically
typed dialect of Ruby.
The current GCJ2018 rules are very unfair to Python and Ruby because
we have no access to high performance implementations of these
programming languages. Your original solution runs fast enough
in PyPy and has a huge performance headroom.
--
Best regards,
Siarhei Siamashka aka 'ssvb'
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/20180507200357.5ad2c0b3%40i7.
For more options, visit https://groups.google.com/d/optout.
