12 May 2015

Coding Contests: Everything you need to know

What in the world is a Coding Contest??

It's a contest where you write code.
Okay, it's a contest where you're given a question, then you type your code and send it to the organizers. Then, your program is tested with different input to make sure you got it right.

What do you mean by "tested"?

The contest organizers have their own programs called graders, which run your program multiple times with different inputs. If the output of your program matches the correct answer in all cases, your program is correct!

But I thought a human tests my program. I even gave helpful output hints for the user like "Enter the number here: "!

Nope, humans usually don't test the code. In fact, if you display those "helpful output hints for the user", your program is wrong. Your program's output should match the answer exactly.

How do I know what my output should look like?

Read the question again. Usually, everything you need is specified in the question.
For example, look at SRS 008.

SRS 008

The questions specifies both how the input will be typed, and how the output should look.
If the answer is 2 and 4, like in the Sample Output, display only that. If there's anything else in the output, that answer is wrong.

Your program is being graded by a computer. You don't need to be nice to them! If you still want to include extra comments in your output, be prepared for a "WRONG ANSWER" comment from the grader.

Fine, I got the idea. But how do I take the input? Should I accept the input before anything else in the program is done?

No, you don't have to. The graders separate your input and output into two separate "streams". All the output is collected in one 'file', and the input is from another 'file'.
You can collect the necessary input from anywhere in the program. But you need to accept it in the right order, exactly as it is specified in the question.

Think of it this way. After you send me your code for SRS 008, I first compile it and get an executable. I have some input in input.txt, which I feed into your program. 

input.txt looks like this:

I specify that whatever your program displays is saved into a file called output.txt. Then I run your program.

I compare your output from output.txt to the answer output in answer.txt. If they match exactly, then your program worked properly.

You don't actually need to worry about any of this. Contest graders automatically take this into consideration. You can continue to use cin, cout, print, display and any other commands you usually use.

Cool. Can I get started now?

Well, you also need to know about test cases, constraints and time-limits.

[*Sigh*] What are test cases?

The graders test your program with different input. This is to make sure that your program works for every single type of input.
For example, the grader for SRS 008 would test your code with different input numbers, just to make sure that you didn't cheat and make the program display the same output every time. Graders also use multiple input to check if you took care of the constraints.

This is annoying. What are constraints?

The range of the input. For example:

Sample Question
When you submit your code, the grader will test your program for different values of A and B. You know the ranges of the two numbers. You shouldn't have made B an "unsigned int" because it needs to hold negative numbers too. Also, you need to make sure that you use a large enough data-type to accommodate large values of B.

In some problems, where the constraints are extremely large, the contest questions might try to make your life more difficult by adding time-limits...

Come on! What are time-limits?

Calm down! Time-limits just tell you how long your program has to give the right answer. Don't bother too much about this to begin with.
If you ever get a grader error saying "TIME LIMIT EXCEEDED", then your algorithm (the way you solved the problem) was too slow. You'll have to find a way to reduce the number of loops, and optimize your algorithm.

But for now, don't worry too much about it.

Okay, got it. Are we done now?

Yes, we're done.

Finally! Now I'm going to try out SRS 008.

Great! Message me if you have any questions.

No comments:

Post a Comment