Yes, it does matter.
I tired to implement the isHappy() in Java with
HashMapInteger,Boolean.
It just fail because of OutOfMemoryError(with -Xmx1024MB).
Then after, I checked the source from the top guys.
The algorithm is exactly the same, but he use C++.
I don't think language is a matter, so
For last year, I was sure that computing speed does matter, and setup
a parallel python running environment for the competition (not that it
really helped that much).
This year I have been traveling abroad during the competition, and had
to do round 1B from a computer which is ~7 years old
It took my system to work on the large set around 3 and half hrs...
yep... I used python.. and lists.. that might be the case also!!!
but.. some of those who have made it through.. their code also took 14
minutes!! after some optimization.. I was able to run it within 6
mins...
but.. all after..
Further optimize from top solution, it shows that i can be done in just 8
secs:
#include iostream
#include fstream
#include string
#include vector
#include hash_map
#include hash_set
#include exception
#include cstdio
#include cstdlib
#include cmath
#include set
#include algorithm
#include queue
It can be solved within 20 seconds in C++ .(may be much faster if do
some optimization)
cyberfish 写道:
Just thought I should point out that, for the large input of question
A (round 1A), my program solved it in a little under 7 minutes on my
computer (a Core 2 Duo overclocked to 3.3ghz). A
Sometimes solutions run near the limit, and it can help to have fast
hardware; I'd like to think this is the exception rather than the rule.
With that said, it's a shame when it does happen. I'm hoping you can think
of an optimization or two that would have brought the runtime down by some
I haven't implemented this myself (thought of it over dinner), but
reducing the search space using the fact that permuting digits doesn't
affect the happiness of a number could reduce the runtime over the
check each number in sequence, in each base approach that I used.
i.e. if we consider up to
Hi cyberfish,
7 minutes is much too long. It obviously shows that your algorithm need to be
optimized.
I used to try such an slow algorithm. I am not fortunate as you, my notebook is
so old that if its CPU 100% occupying keeps more than 30 seconds, it must
breakdown at once. So I have to
It seems like we have the same hardware? My Core 2 Duo is a 2.93 Ghz
one overclocked to 3.3 Ghz. You should have tried to use two threads/
processes, it basically makes your algorithm take 3.5 minutes ^^.
Yesterday I made a whole new c++ template that uses a messed up hack
to split the i/o in two
Given that you have a 2 cores, you could've run the program twice in
parallel in about 3.5 minutes. Of course, if you don't plan ahead then
you're pushing your luck hoping it'll work.
On Sep 12, 1:00 am, cyberfish cyberf...@wecheer.com wrote:
Just thought I should point out that, for the large
Yeah exactly. I'm sure there are faster algorithms and slower
algorithms, but the fact that I was only reqiured to find the
mediocre algorithm and not the fast one is an advantage :).
I thought about using 2 threads, too, but much too late. My code has
inter-testcases optimizations, too (if the
yes, that happened to me. my naive solution was processing 350+th case when
8 minutes is up. i have a c2duo 2 ghz
On Sat, Sep 12, 2009 at 5:19 PM, Nate Bauernfeind
nate.bauernfe...@gmail.com wrote:
Given that you have a 2 cores, you could've run the program twice in
parallel in about 3.5
FYI for a solution that runs in less than 20 seconds you need to
memoize using a simple int[11][MAX_V] kind of array.
(Another FYI: hash maps have way too much overhead... Changing the
hash maps in my solution to a simple array drops the run time from 23m
to 18s. Doh!)
Nate
On Sep 12, 1:34 am,
FYI for a solution that runs in less than 20 seconds you need to
memoize using a simple int[11][MAX_V] kind of array.
(Another FYI: hash maps have way too much overhead... Changing the
hash maps in my solution to a simple array drops the run time from 23m
to 18s. Doh!)
Nate
On Sep 12, 1:34 am,
14 matches
Mail list logo
