Questions about CCC

[ihsh]

Thanks.

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).

[coolgod]

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]

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

[Tony]

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.

[ihsh]

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]

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]

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

[ihsh]

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.
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!

[mirhagk]

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]

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]

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]

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]

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.