My collection of materials for Programing Competitions
All programming content are written in C++.
An online judge is an online system to test programs in programming contests. The system can compile and execute code, and test them with pre-constructed data. - Wikipedia
Suppose a Professor gives you a programming assignment. He gives you a problem (called Problem statement or description) and a sample input and its corresponding output (test cases, explained later). Now, after you have solved a problem and checked it with some of your test cases you give it to the professor. The Professor first checks it with the sample case and a few other test cases. Your grades will solely be based on those test cases that the Professor gives. He/She may check your program and take some other factors into consideration. But what a Professor won’t check is how much time or memory your code consumes for large inputs (input size greater than ). But an Online Judge can do it. It can check whether your code can take large inputs, process it and produce output all within a matter of seconds.
For any given problem a set of input and output files is present with the Online Judge. Let’s call the input file input.txt and the correct output file correct_output.txt. When the user submits its code (after selecting the language of the solution), the Judge will pass the input.txt file to the input of your program and generate the user_output.txt file. The user_output.txt will contain the output of your program for input.txt file. The next step is to match the contents of correct_output.txt and user_output.txt file. If both the files match exactly then it will accept your solution for that problem (giving you an AC for accepted). If, however, both the files mismatch, then you will get a Wrong Answer (or WA). There are other types of errors too like SIGSEGV, TLE, Compilation Error, Runtime Error which we will discuss later.
When you are automating a process then you need to define how it’s supposed to work. Online Judges are used to check thousands of solution within a matter of minutes. Now, let’s take a simple example: Suppose, I tell you to write a program to print the number given in the input. This program can be written in a number of ways.
int main() {
int n;
std::cin >> "Enter a number: ";
std::cin >> n;
std::cout << "The number is: " << n;
return 0;
}
or
int main() {
int n;
std::cin >> "enter a value: ";
std::cin >> n;
std::cout << "the given value is: " << n;
return 0;
}
and a lot more…
The point is when any I/O format is not defined in the problem, the programmer takes the liberty of defining it as it’s own. The Online Judge won’t understand it. After all an Online Judge is also a dumb machine. It only does what we tell it to do. It understands only ‘0’ or ‘1’. Your solution will either be correct or wrong. So, to remove such discrepancy, the I/O format will always be defined in any programming question and the user will have to strictly follow it. You can get WA even for extra newline characters!
Every problem in Online Judge has a defined format. At first you will be given a Problem Description which describes what the problem really wants you to solve. It will also give you the Constraints of all the variables that your are supposed to take input from the user. Then an Input Format and Output Format will be given. Now, as we already discussed that an Online Judge possess two types of file for each problem input.txt and correct_output.txt. The contents of both the files will be arranged in a way do that your code can properly take input. Similar thing goes for Output Format. The correct_output.txt file will be formatted in a way that you can easily reproduce. And finally few Sample Cases will be given so that you can check your code for those input and output and an Explanation (optional) describing those test cases. Let’s understand this with an example:
Jony has number of sticks of heights . He wants to create a single stick of length by joining sticks from his bunch. He wonders whether it’s possible or not make this new stick. Note that two sticks can have the same height, i.e., it is possible that for .
The first line of the input will contain two space separated values and . The next lines will contain a single integer corresponding to the value in the array.
Output Yes if possible else No.
4 6
1
1
2
3
Yes
hence Yes.
A shorter version of the given problem statement is: Given values find whether three of these values can be added to form . The interesting thing to note here is the I/O format and the constraints. Let’s discuss input format first. If we were to see the input.txt file then it would look like this:
N p
a_1
a_2
.
.
a_N
The correct_output.txt file will look like this:
Yes
Now, supposing while taking input you ouput statements like: “Enter the value of N and p” and “Enter N different values”, then your user_output.txt file will look like:
Enter the value of N and p
Enter N different values
Yes
When the Judge will compare these two files, then it will obviously not match and hence you will get a WA or Wrong Answer.
The constraints state that how large or what range of numbers can each input variable encounter.
It is important to note here that the given constraints guarantee that each input variable will never go outside it’s range. Many students confuse constraints with something that they have to check in their program and ensure it never goes outside its range. But it’s not necessary. The Online Judge will always follow it’s given constraints.
This helps to approximate the time your algorithm can take while solving such problems (more on this later) and what data types you need to store such numbers. For example, confirms that will never get a value below and above . Thus, you can safely declare it as int (in C++ atleast). Similar goes for . However, can go outside the range of int and should be declared long long int. It’s safe to consider any value as int and anything above this should be declared long long int.
Yes. There are a few more things that we need to understand. Let’s talk about the different types of messages that you can get after submitting your solution to any problem.
AC (Accepted): This is the result that we all long for. Everything went OK. Code compiled and ran successfully. All the test cases gave correct answers and that too within time and memory limits specified in the question.
WA (Wrong Answer): As the name suggests, your code compiled and ran successfully but gave wrong answer for some test case(s). It is important to note that “some” can vary a huge range. It may be possible that a good portion of the test cases gave wrong answer or just one. Yes, even if a single test case does not match and everything else matches, you’ll get a WA.
Compilation Error: Your code did not compile in the selected language. You may need to cross check whether the solution language and the language you selected are same. Otherwise, you may need to check the exact version of the judge language.
SIGSEGV (Segmentation Fault) or Runtime Error: Your code compiled successfully but generated an error while processing some test case. This can occur due to many reasons. Maybe your code encountered stack overflow or huge memory requirements (beyond the allowed limit), or you tried to access an index in an array that does not exist, etc.
TLE (Time Limit Exceeded): Your code kept executing for a time longer than what is allowed. You may need to apply an efficient algorithm to solve this problem. This comes up a lot of time. One thing to note is that getting TLE does not guarantee that your output is correct. It is possible that you had implemented your solution incorrectly and inefficiently (which is very bad).
General Computer Science resources: https://gist.github.com/shubhambhattar/8f47141d5b89cfbc818e45176249e1be
Competitive Programming resources: https://gist.github.com/shubhambhattar/bc461d622e181cdb9a737d58ad574d5b