Computer Science Canada

Questions about CCC

Author:	Kongaloosh [ Thu Feb 02, 2012 1:20 pm ]
Post subject:	Questions about CCC
Hey, my school's never participated in the CCC and I'm trying to organize it, but there are a few things I don't know. Do we get to use an IDE, or do we have to write by hand? Do you have to use a specific IDE? Also, I saw a post saying Java is allowed for round 2 now, but I can't find it on the CCC site; anyone know if it's true? thanks -KGL

Author:	ProgrammingFun [ Thu Feb 02, 2012 1:36 pm ]
Post subject:	RE:Questions about CCC
You are allowed to use any IDE as far as I know.

Author:	crossley7 [ Thu Feb 02, 2012 5:14 pm ]
Post subject:	RE:Questions about CCC
You can use any language/compiler/ide you wish for round 1 provided your teacher is fine with it, but I believe only C++ and I guess now Java are accepted at round 2. I don't know of any restrictions on IDE though

Author:	Tony [ Thu Feb 02, 2012 5:35 pm ]
Post subject:	RE:Questions about CCC
There are a few restrictions, the spirit of which is "No DSLs" (Domain Specific Language). If your tools (language, IDE, whatever) gives you functionality that feels like you're not really solving the intended question, then that shouldn't be used.

Author:

ihsh [ Thu Feb 02, 2012 6:20 pm ]

Post subject:

Re: Questions about CCC

I have two more questions...

1. What's the maximum amount of time that a program can use to do the processing (for each test case)? If it's something like 1 minute, then many things can be brute-forced...
2. What kind of program is deemed "invalid"? I know that programs that do no processing and just output random numbers are not accepted, but how about hard-coded programs like the one below?

code:

if (input==1)
output 123

if (input==2)
output 224

if (input==3)
output 0

... (and so on)

Thanks.

Author:	ProgrammingFun [ Thu Feb 02, 2012 6:24 pm ]
Post subject:	RE:Questions about CCC
Your programs are initially scored and checked by your teacher so they would detect hard-coding and just disqualify you for that question.

Author:	Tony [ Thu Feb 02, 2012 6:36 pm ]
Post subject:	RE:Questions about CCC
Your teacher would receive a package with marking instructions; those are authoratative on execution time and code quality. My opinion is that implementing state-machines is a valid approach.

Author:	A.J [ Fri Feb 03, 2012 4:29 pm ]
Post subject:	RE:Questions about CCC
Having marked the CCC before, and being on the committee, I will say that implementing state-machines (as Tony puts it) is valid; however, it is highly unlikely that you'll be considered for any of the regional prizes (or even for Stage 2), as if there's someone else who has achieved a similar score using a more 'standard' algorithm, they would be considered more. Having said that, I do encourage bashing out a question that you can't find an efficient algorithm to (as any points you can get counts), but please refrain from merely outputting random values in hopes of getting one of the test cases right (though most questions that require a single output do test multiple cases for each test case, and thus getting all of them correct by merely guessing is highly improbable).

Author:	ProgrammingFun [ Fri Feb 03, 2012 5:34 pm ]
Post subject:	RE:Questions about CCC
Thanks for the information... ...just to clarify, that means that hard-coding is allowed, and even encouraged if we're lost?

Author:	mirhagk [ Fri Feb 03, 2012 5:37 pm ]
Post subject:	RE:Questions about CCC
Well if you can figure the program out manually, it may not be very complex... also the ones they give you as a sample input aren't the testing input. So no, hardcoding is not really encouraged, random number generators might have a better chance lol.

Author:	A.J [ Fri Feb 03, 2012 5:58 pm ]
Post subject:	RE:Questions about CCC
'Hardcoding' and 'randomly outputting values' are pretty much the same thing, and its not encouraged. However, coding up a brute force solution is highly encouraged, especially if you can't think of the most efficient algorithm.

Author:	ProgrammingFun [ Fri Feb 03, 2012 7:13 pm ]
Post subject:	Re: RE:Questions about CCC
A.J @ Fri Feb 03, 2012 5:58 pm wrote: 'Hardcoding' and 'randomly outputting values' are pretty much the same thing, and its not encouraged. However, coding up a brute force solution is highly encouraged, especially if you can't think of the most efficient algorithm. I fail to see the difference, sorry. How would brute-force work if we're only given one trial of the program once it's submitted? To me, brute force would mean that for arriving at a solution, every combination would be tried by the program until a working one is achieved.

Author:	A.J [ Fri Feb 03, 2012 7:29 pm ]
Post subject:	RE:Questions about CCC
Consider the integer knapsack problem. If one doesn't come up with the more efficient dynamic programming solution, they could always code up the brute force solution of trying all possible subsets of the inputs (i.e. O(2^n)). Although this is highly inefficient, it will pass for small cases. However, randomly outputting '0' in hopes that one of the testcases actually tests a particular case will be frowned upon.

Author:

Tony [ Fri Feb 03, 2012 7:46 pm ]

Post subject:

RE:Questions about CCC

A silly example is for the question "is the number prime?". Lets say that you can't figure out how to algorithmically check a number for being a prime, but you have a few of the cases memorized. Your program could be

code:

if i == 2 then return true
elsif i == 3 then return true
elsif i == 5 then return true
...
else return false
end if

Author:	mirhagk [ Fri Feb 03, 2012 8:30 pm ]
Post subject:	RE:Questions about CCC
Lol I want to see someone do that lol Tony.

Author:	ihsh [ Fri Feb 03, 2012 9:16 pm ]
Post subject:	Re: Questions about CCC
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).

Author:	coolgod [ 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.

Author:	mirhagk [ 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.

Author:	Tony [ 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.

Author:	ihsh [ 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?

Author:	mirhagk [ 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)

Author:	coolgod [ 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.

Author:

ihsh [ 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!

Author:	mirhagk [ 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

Author:	smaxd [ 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.

Author:	crossley7 [ 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.

Author:	mirhagk [ 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.

Author:	crossley7 [ 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.

You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy