Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 changing java heap space? legit for contests?
Index -> Contests
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
chopperdudes




PostPosted: Sat Sep 05, 2009 12:16 am   Post subject: changing java heap space? legit for contests?

before now, declaring a 9999x9999 int array was an impossibility in jgrasp, which was a real pain since many of the contest questions have bounds at least 9999, and creating an adj matrix to store the info is more or less the most appropriate way to do it. you can do it with a char array, but that was rather cumbersome. but now by changing the settings in jgrasp, i was able to set the available heap memory to 512mb, which would let me declare an array of that size. however, is this a legit thing to do for contests such as CCC? and how would you assure that the testing computer will have the same settings?
Sponsor
Sponsor
Sponsor
sponsor
bbi5291




PostPosted: Sat Sep 05, 2009 9:49 am   Post subject: Re: changing java heap space? legit for contests?

You are wrong, adjacency matrix is not the right approach when V ~ 10000. With a 10000x10000 array of 4-byte ints, you'll be using 400 MB. You should be using adjacency lists, which take O(E+V) space. When E is small compared to V^2 (sparse graph) almost all simple graph algorithms (DFS, BFS, Dijkstra's, Prim's, maxflow, etc.) are also sped up by the use of adjacency lists.

If you insist on using this approach I'm sure it's ok - just insert comments into your code explaining what has to be done in order for the program to properly compile and run. However be advised that if you make stage 2 then there will probably be problems with V ~ 100000 and you'll have to learn adjacency lists.

Did you have any other contests in mind? (Other than CCC)? I can't think of another contest in which this would be an issue.
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 2 Posts ]
Jump to:   


Style:  
Search: