[gcj] Re: Hardware speed advantage
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 I rewrite my program and replace HashMap with byte[]. Finally, it run smoothly with a bit faster. The rule of abstraction does not apply to code competition? On Sep 13, 4:25 am, cyberfish cyberf...@wecheer.com wrote: Ah, that's probably why. I didn't even use a hash map (which would allow O(1) access). I used a set, and it's probably implemented using a tree (so O(logn) access). A hash map would have additional risk of collision, though, that would be hard to detect. But if you give it 2GB of memory or something... luck will probably be on our side. On Sep 12, 9:44 am, Nate Bauernfeind nate.bauernfe...@gmail.com wrote: 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, Bartholomew Furrow fur...@gmail.com wrote: 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 constant factor, so that you could have done it even with 2x slower hardware. Incidentally, an alternative was to do precomputation. I didn't work on that problem myself, but I think it was a way around doing a lot of computation during the 8 minutes. Also it was apparently solvable within 20 seconds in C++, though as I mentioned I don't know how. :-) Terence, would you mind linking your solution? Bartholomew On Fri, Sep 11, 2009 at 11:00 PM, cyberfish cyberf...@wecheer.com wrote: 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 slower computer may not have made it, so I think this gives an unfair advantage to people with fast computers (like myself) :). --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups google-codejam group. To post to this group, send email to google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~--~~~~--~~--~--~---
[gcj] Re: Hardware speed advantage
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 (PIII 700 MHz, 128 MB of RAM). Run-time for the solutions wasn't the problem though - all of them finished within less than a minute, with a rather slow programing language (I use python). Main difficulty was the fact that task switching on this computer takes ages, so I had to wait 30 seconds to switch from browser to editor and back. I will be home for next round :) --Shachar On Sat, Sep 12, 2009 at 8:34 AM, Bartholomew Furrow fur...@gmail.com wrote: 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 constant factor, so that you could have done it even with 2x slower hardware. Incidentally, an alternative was to do precomputation. I didn't work on that problem myself, but I think it was a way around doing a lot of computation during the 8 minutes. Also it was apparently solvable within 20 seconds in C++, though as I mentioned I don't know how. :-) Terence, would you mind linking your solution? Bartholomew On Fri, Sep 11, 2009 at 11:00 PM, cyberfish cyberf...@wecheer.com wrote: 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 slower computer may not have made it, so I think this gives an unfair advantage to people with fast computers (like myself) :). --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups google-codejam group. To post to this group, send email to google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~--~~~~--~~--~--~---
[gcj] Re: Hardware speed advantage
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.. the 1A round ended... :-( Nitin Kumar --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups google-codejam group. To post to this group, send email to google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~--~~~~--~~--~--~---
[gcj] Re: Hardware speed advantage
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
#include sstream
using namespace std;
using namespace stdext;
#define maxj 2000 //magic number, maybe someone could explain this?
char h[11][maxj];
char buffer[10];
int minimum[2048];
int base[10];
//adopt the best solution
char happy(int n, int base)
{
if (h[base][n] =0)
return h[base][n];
h[base][n] = 0;
int m = n;
int k;
int next = 0;
while (m)
{
k=m % base;
m/=base;
next += k*k;
}
return h[base][n] = happy(next, base);
}
//convert array of bases into a bitmap
int basetoi(int* base, int size)
{
int ans = 0;
for (int i=0; isize; i++)
{
ans |= (1base[i]);
}
return ans;
}
//this function return the maximum result from subset of bases previously
done
//e.g. now bases = {2,5,7,10}, previously we have done {2,5}, {2,10},
{5,7,10} (only subsets are considered), surely the solution will be larger
than the max(solution of these subsets)
int getmin(int b)
{
int ans = 2;
for (int i=0; i2048; i++)
{
if ((b i) == i minimum[i] ans)
ans = minimum[i];
}
return ans;
}
int main()
{
freopen(A-large.in, r, stdin);
freopen(A-large.out, w, stdout);
for (int i=0; i11; i++)
for (int j=0; jmaxj; j++)
h[i][j] = -1;
for (int i=0; i11; i++)
h[i][1] = 1;
for (int i=0; i2048; i++)
minimum[i]=-1;
string s;
int T;
int pre=0, pst;
cin T ;
cin.ignore();
int b;
for (int i=1; i=T; i++)
{
//read bases
cin.getline(buffer, 1000);
s.assign(buffer);
pre = 0;
pst = s.find( , pre);
int size=0;
while (pst != -1)
{
int ii = atoi(s.substr(pre, pst - pre).c_str());
base[size++] = ii;
pre = pst + 1;
pst = s.find( , pre);
}
pst = s.length();
int ii = atoi(s.substr(pre, pst - pre).c_str());
base[size++] = ii;
bool state;
int k;
//check whether the bases are done before
b = basetoi(base, size);
if (minimum[b] 0)
k = minimum[b];
else
for (k=getmin(b); ;k++) //the trick here: based on previous cases, find a
higher starting point instead of 2
{
state = true;
for (int j=0; jsize; j++)
{
if (happy(k,base[j]) == false)
{
state = false;
break;
}
}
if (state)
break;
}
minimum[b] = k;
cout Case # i : k endl;
}
return 0;
}
On Sun, Sep 13, 2009 at 4:57 PM, Nitin Kumar nitinkumar...@gmail.comwrote:
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.. the 1A round ended... :-(
Nitin Kumar
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
google-codejam group.
To post to this group, send email to google-code@googlegroups.com
To unsubscribe from this group, send email to
google-code+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en
-~--~~~~--~~--~--~---
[gcj] Re: Hardware speed advantage
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 slower computer may not have made it, so I think this gives an unfair advantage to people with fast computers (like myself) :). --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups google-codejam group. To post to this group, send email to google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~--~~~~--~~--~--~---
[gcj] Re: Hardware speed advantage
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 constant factor, so that you could have done it even with 2x slower hardware. Incidentally, an alternative was to do precomputation. I didn't work on that problem myself, but I think it was a way around doing a lot of computation during the 8 minutes. Also it was apparently solvable within 20 seconds in C++, though as I mentioned I don't know how. :-) Terence, would you mind linking your solution? Bartholomew On Fri, Sep 11, 2009 at 11:00 PM, cyberfish cyberf...@wecheer.com wrote: 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 slower computer may not have made it, so I think this gives an unfair advantage to people with fast computers (like myself) :). --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups google-codejam group. To post to this group, send email to google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~--~~~~--~~--~--~---
[gcj] Re: Hardware speed advantage
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 9 digit numbers (in base ten), there are 18 choose 9 5 possibilities for their digit sequences when put in sorted order. Generate these and isolate the happy ones (I don't know how many there are), and you can now generate the base 10 happy numbers with some kind of priority queue. The same kind of idea applies to the other bases; even though the number of digits increase, the decrease in the number of digit values has a greater effect (the numbers of digit combinations I calculate are [31,210,816,2380,6188,12376,19448,43758,48620] for bases [2..10]; though all base-2 numbers are happy so maybe just leave those out). Then we can do a mergesort-like intersection to find the first common happy number. Not having tested this, I'm not sure if the overhead in this approach makes it worthwhile -- but it's the best I could think of so far. On Sep 12, 12:34 am, Bartholomew Furrow fur...@gmail.com wrote: 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 constant factor, so that you could have done it even with 2x slower hardware. Incidentally, an alternative was to do precomputation. I didn't work on that problem myself, but I think it was a way around doing a lot of computation during the 8 minutes. Also it was apparently solvable within 20 seconds in C++, though as I mentioned I don't know how. :-) Terence, would you mind linking your solution? Bartholomew On Fri, Sep 11, 2009 at 11:00 PM, cyberfish cyberf...@wecheer.com wrote: 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 slower computer may not have made it, so I think this gives an unfair advantage to people with fast computers (like myself) :).- Hide quoted text - - Show quoted text - --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups google-codejam group. To post to this group, send email to google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~--~~~~--~~--~--~---
[gcj] Re: Hardware speed advantage
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 figure out a better algorithm. Fortunately, I succeed after all. Anyway, as a summary of all important algorithm contests, any digital problems should not to be programed like for(i=0; ...;i++). Wish you succeed. Good luck everyone! On 2009-09-12 at 14:24:25, Terencetechnic@gmail.com wrote: 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 slower computer may not have made it, so I think this gives an unfair advantage to people with fast computers (like myself) :). -- Best Regards, Xi Chen 2009-09-12 --- Xi CHEN chenxi...@mails.gucas.ac.cn Institute of Software Chinese Academy of Sciences 地址：北京市海淀区中关村南四街4号8718号邮箱 Address: Institute of Software Chinese Academy of Sciences 4# South Fourth Street, Zhongguan Cun, Beijing P.R.China 100190 --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups google-codejam group. To post to this group, send email to google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~--~~~~--~~--~--~---
[gcj] Re: Hardware speed advantage
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 processes. It really works. Makes me wish I had 32 cores :) . It is a shame I didn't solve A because I didn't want to bother with base arithmetic ... I hope I can use my new template in round 2. On Sep 12, 2:00 am, cyberfish cyberf...@wecheer.com wrote: 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 slower computer may not have made it, so I think this gives an unfair advantage to people with fast computers (like myself) :). --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups google-codejam group. To post to this group, send email to google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~--~~~~--~~--~--~---
[gcj] Re: Hardware speed advantage
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 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 slower computer may not have made it, so I think this gives an unfair advantage to people with fast computers (like myself) :). --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups google-codejam group. To post to this group, send email to google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~--~~~~--~~--~--~---
[gcj] Re: Hardware speed advantage
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 result for bases 2 3 4 is
x, for 2 3 4 8, there is no need to start from anything less than
x).
2 threads would probably have made it faster overall.
My solution was in C++, and I did do the premutations optimization.
My algorithm in pseudo-code:
bool is_happy(number, base) {
if (number == 1) return true;
int64 new_number = 0;
vectorint digits; /* for those not familiar with C++, a vector
is a dynamic array, like ArrayList in Java */
while (number != 0) {
int digit = number % base;
number /= base;
add the element digit to digits
new_number += digit * digit;
}
sort the digits vector
calculate a hash of the sorted vector using precomputed zobrist
keys (http://en.wikipedia.org/wiki/Zobrist_hashing)
/* basically for every element of the vector, xor zobrist
[position][digits[position]] into the hash, where zobrist is a 2D
array of precomputed randomly generated numbers (I used Mersenne
Twister) */
try to find the hash in a set of numbers already seen.
if found, return false;
else
add hash to the set;
return is_happy(new_number, base);
}
-
I'm sure there are ways to make it faster by moving things around...
but I think the general algorithm I have here SHOULD be fast enough,
and having a fast CPU allowed me to not have to spend time optimizing
it.
BTW, my CPU is a C2D 1.86ghz overclocked to 3.3 :). Gotta love early
C2D's.
Ah, adding parallelization to template would be a very good idea. I'll
consider doing that, too. Maybe even adding a little server and client
that would allow you to build a cluster in short order (the server can
dispatch tasks, and clients will just receive and process them, and
send the result back to the server. They can all run the same code,
with a different command line switch or something). If I add all the
computers in the house together, I have 8 cores! (1 P4, 1 Core 2 Solo,
2 Core 2 Duo's, 1 Core 2 based dual core Celeron).
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
google-codejam group.
To post to this group, send email to google-code@googlegroups.com
To unsubscribe from this group, send email to
google-code+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en
-~--~~~~--~~--~--~---
[gcj] Re: Hardware speed advantage
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 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 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 slower computer may not have made it, so I think this gives an unfair advantage to people with fast computers (like myself) :). --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups google-codejam group. To post to this group, send email to google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~--~~~~--~~--~--~---
[gcj] Re: Hardware speed advantage
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, Bartholomew Furrow fur...@gmail.com wrote: 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 constant factor, so that you could have done it even with 2x slower hardware. Incidentally, an alternative was to do precomputation. I didn't work on that problem myself, but I think it was a way around doing a lot of computation during the 8 minutes. Also it was apparently solvable within 20 seconds in C++, though as I mentioned I don't know how. :-) Terence, would you mind linking your solution? Bartholomew On Fri, Sep 11, 2009 at 11:00 PM, cyberfish cyberf...@wecheer.com wrote: 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 slower computer may not have made it, so I think this gives an unfair advantage to people with fast computers (like myself) :). --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups google-codejam group. To post to this group, send email to google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~--~~~~--~~--~--~---
[gcj] Re: Hardware speed advantage
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, Bartholomew Furrow fur...@gmail.com wrote: 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 constant factor, so that you could have done it even with 2x slower hardware. Incidentally, an alternative was to do precomputation. I didn't work on that problem myself, but I think it was a way around doing a lot of computation during the 8 minutes. Also it was apparently solvable within 20 seconds in C++, though as I mentioned I don't know how. :-) Terence, would you mind linking your solution? Bartholomew On Fri, Sep 11, 2009 at 11:00 PM, cyberfish cyberf...@wecheer.com wrote: 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 slower computer may not have made it, so I think this gives an unfair advantage to people with fast computers (like myself) :). --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups google-codejam group. To post to this group, send email to google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~--~~~~--~~--~--~---
