How will a solution be judged in a programming competition. ?>

How will a solution be judged in a programming competition.

Assalamualaikum everyone, today’s topic is how a judge software judge a solution. Or in another word, how do you submit the solution for the problem. And also, how do you output your solution for a particular problem.

Introduction

For those of you who did not know, in ACM ICPC, every team will be given a set of problem which the team will need to solve. The way to solve them is by coding the solution. The problem will say that the solution will have to accept some input and it should output according to the input. For example, in the previous Crash Course, we had an A+B question where the program is given some pairs of number in which it will need to output the solution. So, if the input is:

1
1 2
3 4

Then the output is:

3
7

Problem will also come with some sample input and output in which your solution must be able to reproduce the sample output for the given sample input. However, the judge program will test your solution with other sample input which is hidden. So your solution must be robust enough to accept more input.

Using the Command Prompt

To go through the tutorial here, first you need to know how to use a terminal. We will use it for IO redirection. In Windows, to open a terminal, press the home button and search for ‘cmd’. The first search result is the ‘Command Prompt’. That is the terminal we are looking for. Open it and you will see a windows in which you can type commands. By ‘commands’, I mean programs. For example, ‘dir’ and ‘copy’ are name of program. So you can type ‘dir’ and press enter, it will list down the files in the current directory.

Another thing that you need to know is the ‘current directory’. On the left of the prompt, there is a directory path. That is the current directory. To change the current directory, use ‘cd’ command. For example, to change current directory to ‘C:\Windows’, use the command ‘cd C:\Windows’. You can also use a relative path. To auto complete the path, use the TAB key. For example, I could write ‘cd C:\Wind’ and then I press TAB. It will auto complete to ‘cd C:\WIndows\’.

To execute the program that you have compiled, you need to change the directory to the directory that you put your program. Then you can run your program by typing the program name.

The system(“pause”) thingy.

If you use the ‘system(“pause”)’ function in your code, what you basically do is that, you call the program called ‘pause’. This program basically halt the execution of your program. When you execute your program directly with DevC++, the terminal will automatically close when program has finished executing. So you can’t see the result of your program. That is why you put the ‘system(“pause”)’ function. So that it will halt the program and you have some time to see the output of your program. If you open the terminal manually, then execute the program, the terminal will not close when your program exit. So ‘system(“pause”)’ is not needed. More importantly, in competitive programming, this will cause a compilation error as the ‘system’ function is not available in linux environment. If the judge software is running on a Windows machine, it will compile correctly. However, it will cause the program to hang, causing your solution to have a time limit exceeded (TLE) verdict. Moral of the story, don’t use ‘system(“pause”)’.

How do the judge pass the input and get the output?

Back at the Crash Course we held before, one of the question in the contest simulation is an A+B question. Basically the question is, given several pair of number, give the result when the pairs are added.

Example input:

3
1 2
3 4
5 6

Example output

3
7
11

Our sample solution is a simple loop which print the result without storing the numbers first. Which is like this:

#include

using namespace std;

int main(){
  int n;
  cin >> n;
  for(int i=0;i<;n;i++){
    int a,b;
    cin >> a >> b;
    cout << a+b << endl;
  }
  return 0;
}

What happen is that, when we test it by hand, meaning we put the value interatively through the console, it will be like

3
1 2
3
3 4
7
5 6
11

The output is printed as soon as we get the answer. The printed result that you see in the console is different that the sample output, yet it is the correct solution. Why? That is because what you type in the console (the input) is mixed with what you print (the output). But the judge only consider what you print.

To understand why this happen, we need to talk about standard input and standard output, collectively known as the standard stream. The idea of standard stream was popularized around the time of UNIX (I think) way before graphical user interface was invented. UNIX was a very old operating system which can be considered the father of most, if not all operating system. Even Windows was influenced heavily by UNIX. And therefore most operating system nowadays inherit some feature from UNIX, one of those is standard stream.

The idea is that, the sole purpose of a software is (usually) to get a particular input, process it and output something. We are not talking about graphical software which you can see user friendly interface. We are talking about a software at its most basic form. To simplify the input and output, every program will have a standard input and standard output without any setup required. In C++, these are the purpose of cin and cout. cin get data from the standard input and cout output data to the standard output.

By default, the standard input is your input from the terminal and the standard output is also the terminal. So when using cin, it expect input from terminal and when using cout it output data to the terminal. The standard input and standard output do not need to be from the terminal. The standard input can be from a file or another program and the standard output can be put into another file or another program. These act of changing the source and target of the standard streams is called IO redirection.

For example, if you put all the sample input from the same question (A+B question) into a file called ‘A.input’, you can use that file as an input instead of typing in the terminal. Example, if your solution file is called solutionA.exe, you can using A.input as the standard input of solutionA.exe by using the command ‘solutionA.exe < A.input’ in a terminal. This time it will not prompt for any input, and it will output the solution. This is the solution that will be judge. The symbol ‘<‘ shows that the program will get its input from a file.

You can also redirect the output to a file. To do that I can use the ‘>’ symbol. For example, if I want to save the output of the previous command into a file called A.output, the command that I need to use is ‘solutionA.exe < A.input > A.output’. When I run it, nothing will show up. But a file called ‘A.output’ is created and inside the file is the output that you see earlier. If the file already exist, the file will be overwritten.

One more thing. You can use a program’s output as another program’s input. This is called ‘piping’. For example, if I have a program called ‘gen_rand.exe’ whose sole purpose is to print 10 random numbers, and another program called ‘sort.exe’ whose sole purpose is to sort 10 number from input in an increasing order, I can use the command ‘gen_rand.exe | sort.exe’ to redirect the output of gen_rand.exe and feed it to sort.exe. It will output 10 sorted random number.

So how do the judge, judge it?

That depends on the type of judge. Generally you should expect it to redirect the real input of a problem into your solution and redirect the output of the solution to a file. Then, the file will be compared with the correct output for the problem. If there is no different between the two file, the solution is considered correct.

Sometimes a problem may have more than one correct output. Codeforces have a lot of this type of problem. I don’t know the exact way of judging it, but I guess it will pipe the output of your solution into a special custom made program for each solution. If the program says it is correct, then it is correct.

For PC^2 software, the software that is in ACM ICPC, that depends on what the problem setter has set. The problem setter may check the code manually, or he can set a ‘validator’ that automatically check the different between your solution’s output and the expected output. It can do both (if I’m not mistaken), making the validator as a pre-test and then checking the source code manually if the pre-test pass. Or the problem setter may make their own ‘validator’ program.

Other verdict.

Aside from ‘Accepted’ and ‘Wrong’ verdict. There are other type of verdict.

  • Compilation Error
    • This happen because the judge computer fail to compile your solution. Remember, the judge computer is (usually) a Linux machine.
    • This can also happen if you have a space in your source code filename when using with PC^2. This happened in the Crash Course.
    • For java user, make sure your class name is the same as your source code name. Also it may be safer to use ‘Main’ as your class name.
  • Time Limit Exceeded
    • This happen when your solution took too long to execute.
    • Check your code complexity, make sure it can run fast enough, if not, your solution is not the right solution.
    • The sample input is not the real input. The real input is designed to fail your solution by having very large input or some ‘edge’ cases.
    • Check for infinite loop.
  • Runtime Error
    • This indicate an error during the execution of your solution. Or more formally, the executable return a nonzero status code.
    • For C++ this usually happen when you have segmentation fault. That usually means you are trying to access element out of array size. For example, if you define an array like ‘int arr[100]’, but you try to access it using ‘arr[100000]’. Sometime this also happen when you incorrectly initialize a pointer.
    • For JAVA user. This usually means a NullPointerException or IndexOutOfBoundException.
    • To fix it, just check your code thoroughly for bugs that may crash it.
  • Output Format Error
    • This rarely happens because most judge just check the different of your output with the sample output.
    • This means the way you represent the code is wrong. For example, if you are suppose to output in a format like ‘Case #1:’ but you output ‘case #1:’.