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

Username:   Password: 
 RegisterRegister   
 Questions about CCC
Index -> Contests
Goto page Previous  1, 2
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
ihsh




PostPosted: Fri Feb 03, 2012 9:16 pm   Post subject: Re: Questions about CCC

Thanks. Wink

And how about heuritics (especially the ones that have wrong outputs for many inputs, and are just lucky to have solved each of the test cases correctly)? Would they be frowned upon? And would they be considered as superior to the less efficient but more accurate brute force approaches?

Also, say there's a problem that requires a program to output the sum of all the prime numbers up to an integer n. Can a person just use a highly inefficient program to generate the answers for all possible values of n, and then paste those answers into their actual program? Would this be considered as cheating? (since the program contains like, say, ten million hard-coded answers).
Sponsor
Sponsor
Sponsor
sponsor
coolgod




PostPosted: Fri Feb 03, 2012 9:23 pm   Post subject: Re: Questions about CCC

i would like to know more about the time limits is it 1 min? Also is java supported at stage 2, personally I wouldn't use it but i know a few who might.
mirhagk




PostPosted: Fri Feb 03, 2012 11:56 pm   Post subject: RE:Questions about CCC

@ihsh, I found that generating prime numbers is faster then reading them off a hard drive.
Tony




PostPosted: Sat Feb 04, 2012 2:00 am   Post subject: Re: Questions about CCC

ihsh @ Fri Feb 03, 2012 9:16 pm wrote:
And would they be considered as superior to the less efficient but more accurate brute force approaches?

This would be judged by an assortment of test cases against which your program is graded.
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
ihsh




PostPosted: Sat Feb 04, 2012 9:12 am   Post subject: Re: RE:Questions about CCC

mirhagk @ Fri Feb 03, 2012 11:56 pm wrote:
@ihsh, I found that generating prime numbers is faster then reading them off a hard drive.


Wait... if the person pastes that complete list of prime numbers directly into their program (e.g., into an array), shouldn't that be faster than the sieve of Eratosthenes?
mirhagk




PostPosted: Sat Feb 04, 2012 11:11 am   Post subject: RE:Questions about CCC

Try it for yourself, perhaps your hard drive is faster, but the sieve for a small amount of numbers takes pretty much negligible time. I remember writing a prime number program that was rather slow (checks each number if it's divisible by all the primes found already) and it was faster to regenerate them each time then it was to read them off a hard drive (for numbers up to 2 million at least).

Try it out yourself, but a primality sieve often times is faster than reading numbers in from a hard drive, so it likely would take just as long to compute prime numbers as it would for the program to load them into RAM (although maybe not, but the difference wouldn't be huge, it's not like you'd save a lot of time)
coolgod




PostPosted: Sat Feb 04, 2012 1:58 pm   Post subject: Re: Questions about CCC

for smaller primes generating them is pretty fast, for larger primes reading off harddrive could be faster.
ihsh




PostPosted: Sat Feb 04, 2012 8:35 pm   Post subject: Re: Questions about CCC

Just now it took me less than a second to generate 660000+ prime numbers with the sieve; I never knew it would be so fast. Razz
Also, I just tried pasting a large list of primes into my program, and my program couldn't compile because there were 'too many elements" in it (65535+). The 65535th prime is only 400000 something, so yeah, that copy-and-paste method doesn't really apply to generating prime numbers.

But for Dwite round 1 question 4, this was what one group did:
Python:

QUESTION_NUMBER = 4

def ReadFile():
    for Line in open("data%s.txt"%QUESTION_NUMBER,"r"):
        for Part in Line.split():
            yield Part

Next = ReadFile().next


#=============

def WriteLine(Line):
    open("out%s.txt"%QUESTION_NUMBER,"a").write(str(Line) + "\n")

data = [
( 0 , 1 ),
( 100000 , 38895 ),
( 200000 , 88895 ),
( 300000 , 138895 ),
( 400000 , 188895 ),
( 500000 , 238895 ),
...
...
...
( 9900000 , 5838895 ),
( 10000000 , 5888897 ),
    ]

...rest of code...


That, I think, sped up their program by around 100 times. And for the CCC, can one do the same thing? For n pre-included values, one could speed up their program by n+1 times!
Sponsor
Sponsor
Sponsor
sponsor
mirhagk




PostPosted: Sun Feb 05, 2012 1:46 pm   Post subject: RE:Questions about CCC

Well except for the memory usage, which may be a factor (because restructuring a recursive function to work with a queue means every 4 bytes of memory you save, is potentially another level you can to depth wise
smaxd




PostPosted: Sun Feb 12, 2012 2:34 pm   Post subject: Re: Questions about CCC

Can we use multiple for each question? For example if s3 required a graph would i be able to submit s3.java and s3node.java?
Im not to sure on using nested classes so yeah just wondering if this was acceptable.
crossley7




PostPosted: Sun Feb 12, 2012 4:03 pm   Post subject: RE:Questions about CCC

you would place them within the same program. If you needed it, I'm sure you could have multiple classes in 1 file, but generally that isn't needed in contests. Then again, Java is not my strong point and there might be weird things I do not yet know about.
mirhagk




PostPosted: Sun Feb 12, 2012 7:54 pm   Post subject: RE:Questions about CCC

You'd need to nest the classes in Java in order to have them in one file. Java wants one class per file, (except nested classes).

Nested classes are easy, just don't treat it much differently.
crossley7




PostPosted: Sun Feb 12, 2012 11:30 pm   Post subject: RE:Questions about CCC

I guess I never have more than 1 class per file or used Java for more than 5 days at the beginning of grade 11 before I bailed on course content and did things that were actually challenging so I wouldn't know.
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 2 of 2  [ 28 Posts ]
Goto page Previous  1, 2
Jump to:   


Style:  
Search: