Difference between revisions of "Judge:Help"

From PEGWiki
Jump to: navigation, search
m (Execution discrepancies)
Line 247: Line 247:
 
* Memory: 2 GB physical RAM, 1 GB swap
 
* Memory: 2 GB physical RAM, 1 GB swap
  
=="My program compiles (or is correct) on my computer but not on the judge."==
+
==Compilation discrepancies==
===For loop variable scoping===
+
Sometimes, your program may compile on your computer but not on the Judge.
 +
 
 +
===C++===
 
This type of code compiles in Microsoft Visual C++ 6.0 (but not here):
 
This type of code compiles in Microsoft Visual C++ 6.0 (but not here):
 
<syntaxhighlight lang="cpp">
 
<syntaxhighlight lang="cpp">
Line 261: Line 263:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
This is because in this case g++ conforms to the standard, which indicates that a variable declared as <code>i</code> is above is local to the for loop, whereas MSVC6 fails to conform to this part of the standard.
+
This is because in this case g++ conforms to the standard, which indicates that a variable declared as <code>i</code> is above is local to the for loop, whereas MSVC6 fails to conform to this part of the standard. '''If you are still using MSVC6, for God's sake, stop.''' You can download the latest version of VC from [http://www.microsoft.com/express here].
  
===Strange C++ compilation errors===
 
 
C++ compilers tend to give notoriously unhelpful error messages. (It is claimed that Apple's clang++ has better error messages than g++, but often you will still be quite out of luck, such as if you try to declare a vector of const ints.) For example:
 
C++ compilers tend to give notoriously unhelpful error messages. (It is claimed that Apple's clang++ has better error messages than g++, but often you will still be quite out of luck, such as if you try to declare a vector of const ints.) For example:
 
<pre>/usr/include/c++/4.1.3/bits/stl_iterator_base_types.h: In instantiation of 'std::iterator_traits'</pre>...
 
<pre>/usr/include/c++/4.1.3/bits/stl_iterator_base_types.h: In instantiation of 'std::iterator_traits'</pre>...
Line 270: Line 271:
 
Also, if you somehow make a mistake with templates, such as by specifying the wrong number of template arguments, or specifying the template arguments in an order that doesn't make sense, g++ is likely to produce extremely long (and thus rather unhelpful) error messages. If you see huge error messages with lots of angle brackets, check your template usage. (Note that many of the functions in the <code>algorithm</code> header are templated so that they can work with generalized iterator ranges; the most common example is <code>std::sort()</code>.)
 
Also, if you somehow make a mistake with templates, such as by specifying the wrong number of template arguments, or specifying the template arguments in an order that doesn't make sense, g++ is likely to produce extremely long (and thus rather unhelpful) error messages. If you see huge error messages with lots of angle brackets, check your template usage. (Note that many of the functions in the <code>algorithm</code> header are templated so that they can work with generalized iterator ranges; the most common example is <code>std::sort()</code>.)
  
===Execution discrepancies===
+
==Execution discrepancies==
 
If your program runs correctly on your computer but produces the wrong answer on the Judge, one of the following is usually the cause:
 
If your program runs correctly on your computer but produces the wrong answer on the Judge, one of the following is usually the cause:
 
* Printing to standard error (at this time, whatever you print to standard error will end up in standard output, and hence cause your program to fail the test data.)
 
* Printing to standard error (at this time, whatever you print to standard error will end up in standard output, and hence cause your program to fail the test data.)

Revision as of 19:31, 2 July 2012

Overview

On the problems page (which is accessible from any page on the Judge by clicking "problems" on the black navigation bar at the top of the page), you will find a list of problems to which you can submit solutions. Clicking the problem name on this page will link you to the problem's description. Note that each problem also has a unique alphanumeric problem code, which you might have to specify when you're ready to submit your solution.

When on a problem description page, you will find a link that reads "Submit" on the right of the problem statement. Clicking this takes you to the submission page and automatically fills in the "Problem code" field of the submission form with the code of the problem you were just viewing. You can also reach the submission form by clicking "submit" on the black navigation bar, but then you will have to fill in the problem code manually.

On the submission form, paste your solution in the box labelled "Code". You can also upload a source file from your computer. After you click "Submit", your program will be compiled (if applicable), run, and evaluated, and you will be taken to a page that shows the results of the evaluation.

Whenever you submit, a copy of your source code, and the date and time and results of your submission, are saved permanently on the server. To view your past submissions, go to the main Submissions page by clicking "submissions" on the navigation bar, and then click "My Submissions" on the right. To view your submissions to a particular problem, navigate to that problem's description page, and then click "My Submissions" on the right.

You can see a list of your solved problems under "My Account".

On the main Judge archive, you can submit as many solutions to any problem as you want. Feel free to solve a problem again in a different language, or using a different algorithm. You'll only get the points for it once, though.

Guidelines for submitting

  • Read all input from standard input, and output to standard output, even if the problem statement says otherwise. This means that you should submit the program as though it would read from the keyboard and write to the screen.
  • But don't take this literally! The input is a sequence of characters given left to right, top to bottom, and not a sequence of keystrokes. Don't use functions like getch() or readkey; they won't work. The output is likewise a sequence of characters given left to right, top to bottom, and those characters must be outputted in that order; commands that change the cursor position on the screen will not work. This is because your program will actually be reading from a file and writing to a file.
  • Input and output are to be in the exact format indicated on the problem description. Do not prompt for input by printing lines such as "Enter the number of points"; these will end up in the output and your program will be graded incorrect.
  • If you are using Java, the name of the class containing main() must match the problem code exactly.
  • For most problems, the judge will mark your solution correct regardless of how much trailing space appears in the output. Likewise, empty lines are simply ignored.
  • The judge does care about spelling and punctuation. Forgetting commas, for example, will cause your program to be marked wrong.
  • Unless there is a good reason to do so, DO NOT read in multiple test cases in one shot, store them in an array, and then output their answers all in one shot. Instead, process the test cases one by one. See below for more details.

If you're not getting accepted, don't blame the judge; it's usually your fault. However, if nobody has yet solved the problem you're trying to do (or very few), and you think there might actually be a bug, contact Brian.

Important note: Suppose that the problem A plus B had multiple test cases. So, the first line of the input file would be N (1 ≤ N ≤ 100), the number of test cases to follow, and each subsequent line would contain two integers. For each line containing a pair of integers in the input file, the corresponding line in the output file should contain their sum. For example:

Sample Input

3
1 2
3 4
5 6

Sample Output

3
7
11

Here is how a good solution might look (in C++):

#include <iostream>
using namespace std;
int main()
{
	int N,i,a,b;
	cin >> N;
	for (i=0; i<N; i++)
	{
		cin >> a >> b;
		cout << a+b << endl;
	}
	return 0;
}

And here is how an unnecessarily complicated solution might look:

#include <iostream>
using namespace std;
int main()
{
	int array[100];
	int N,i,a,b;
	cin >> N;
	for (i=0; i<N; i++)
	{
		cin >> a >> b;
		array[i]=a+b;
	}
	for (i=0; i<N; i++)
		cout << array[i] << endl;
	return 0;
}

The first solution runs a for loop N times, and in each iteration it reads two integers and then prints out their sum. The second solution reads all the input into an array and only starts printing output after all the input has been read.

Some people are tempted to write the second solution because they imagine that input and output occur on a terminal and that the contents of the terminal after the program has completed must be the input followed by the output. This is not the case; input will come from a file and output will go to a file, and the two will never interfere with each other.

Thus, it is allowed (and encouraged, in fact) to print the answer to each test case as soon as you get it.

Forbidden actions

Your program shall not do, or attempt to do, any of the following:

  • fork,
  • access the network,
  • open, create, delete, rename, move, or examine any file or directory, or examine or change any file or directory's attributes, or change its current working directory, or otherwise examine or interact with the filesystem,
  • write to standard input,
  • interact with any other process, except by interacting with the grader for an interactive task by reading from standard input and writing to standard output,
  • examine any other process,
  • read, write, or execute memory from the address space of any other process or any shared library that your program has not loaded,
  • execute any other program, or dynamically load a shared library from disk that is not automatically loaded by the programming language runtime or standard libraries,
  • technically circumvent the grader in order to exceed the stated time or memory limits, or do, or attempt to do, any of the above.

About the test cases

The sample test cases are shown for two reasons. One is to help you ascertain that you have correctly interpreted the problem statement and the input and output format. The other is to discourage you from submitting solutions that are obviously wrong (because they don't even process the sample input correctly). Please take advantage of the sample test cases! Please don't complain that your program is failing the actual test data unless you've at least managed to pass the sample test data.

Also, be aware that the actual test data will most likely be quite a bit more difficult than the sample test data, meaning that it will often:

  • contain a large number of data points or large number of lines of input, so your program will have to be very efficient in terms of time and memory;
  • contain tricky "edge cases" and "corner cases" that tend to expose bugs in many attempts at solution implementations;
  • contain difficult test cases that cannot be solved using naive algorithmic reasoning that might work for the sample.

Please don't ask whether so-and-so-difficult-test-case might show up in the test data. The answer is probably yes; why shouldn't problems be challenging? You should always assume that any test case that is not explicitly forbidden by the problem statement can and will appear in the test data.

Summary of supported languages

Language Compiler/Interpreter Compiler switches Runtime switches Sample A Plus B code
C++ g++ 4.1.3 g++-4.1 -O2 -DONLINE_JUDGE None
#include <iostream>
using namespace std;
int main()
{
	int a, b;
	cin >> a >> b;
	cout << a+b << endl;
}
Pascal Free Pascal 2.4.0-2 fpc -So -dONLINE_JUDGE -O2 None
var
	a,b: integer;
begin
	readln(a,b);
	writeln(a+b);
end.
C gcc 4.4.3 gcc -O2 -lm -DONLINE_JUDGE None
main() {
	int a, b;
	scanf("%d %d", &a, &b);
	printf("%d\n", a+b);
	return 0;
}
Haskell ghc-6.12.1 ghc -O -fvia-c +RTS -V0 None
main = do
        x <- getLine
        y <- getLine
        print (read x + read y)
Assembly (Intel x86) nasm 2.07 nasm -f elf
ld -s
None See aplusb.asm
Ruby ruby 1.8.7 N/A None
puts Integer(gets) + Integer(gets)
Python python 2.6.5 N/A None
print int(raw_input()) + int(raw_input())
Java Java version 1.6.0_18: OpenJDK (IcedTea6 1.8.1) javac -client
import java.util.Scanner;
public class aplusb
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.println(sc.nextInt()+sc.nextInt());
        sc.close();
    }
}
PHP PHP 5.3.2 N/A -n
<?php
echo fgets(STDIN) + fgets(STDIN) . "\n";
?>
Output-only N/A N/A N/A 1111
OCaml OCaml 3.11.2 ocamlc None
print_int (read_int()+read_int());;
print_newline ();;
Perl perl v5.10.1 N/A None
print <> + <> . "\n";

Output-only problems

An output-only problem is a problem in which you are given all the test input during the contest and merely required to submit the correct output at some point before the end of the contest. Contrast this with ordinary ("batch") problems in which you do not get to see the test data during the contest and must submit a program to generate the output.

Problems that are intended to be output-only may generally be submitted in only one language, which is called "TEXT" on the problem page and submission status page, and "Output-only" in long form on the submission form. Simply paste or upload the correct output.

Language restrictions

The sidebar on the right of each problem description page shows a list of languages that can be used to solve that problem. The language codes used are the same as those shown on the submissions page. (Hover over a language code to see its full description.)

Most problems can be solved in every language except TEXT. The TEXT (output-only) language is usually reserved for output-only problems (see above). There are, however, cases in which not all languages may be used. In general:

  • Some problems, such as Shortest Code Contest, only make sense if solutions are to be written in one (or a few) particular language(s) (here, C or C++). These problems are expected to be very rare on the PEG Judge, since they are mostly nonalgorithmic in nature.
  • In some problems the main algorithmic challenge results from such tasks as manipulating large integers (see Bignum), parsing strings (see Regex), or dynamically evaluating expressions. In such cases, languages with built-in facilities for performing these operations are disallowed. For example, A Plus B 2 is very easy in any language with built-in bignums. The vast majority of problems on the PEG Judge are not of this variety.
  • It might be argued that C++ should not be allowed on some problems because it has the algorithmically complex std::set and std::map (see dynamic set, map) in its standard library, whereas C and Pascal do not. However, C++ is allowed in every major programming competition, including the IOI, all major national olympiads, the ACM ICPC, and TopCoder. (On the other hand, whereas most competitions allow Java, not all of them do.) Therefore, C++ should always be allowed, and so should C and Pascal, which are allowed at every major programming competition except TopCoder. (It should also be pointed out that C is minimal by design, and hence restricting oneself to using it to write algorithms is nearly as pointless as writing in assembly language (which is also supported); although this is likely to be a controversial point.)

Judge system specifications

  • Operating system: Ubuntu 11.04 (Natty Narwhal) 32-bit
  • Processor: Intel® Xeon® CPU X3440 @ 2.53 GHz
  • The CPU is dual-core, but multiprocessing has been disabled because it interferes with timing on the Judge server. Dedicated server machines do not suffer from the same issue, despite having multiple cores.
  • Memory: 2 GB physical RAM, 1 GB swap

Compilation discrepancies

Sometimes, your program may compile on your computer but not on the Judge.

C++

This type of code compiles in Microsoft Visual C++ 6.0 (but not here):

for (int i = 0; i < N; i++)
{
	...
}
if (i == N)
{
	...
}

This is because in this case g++ conforms to the standard, which indicates that a variable declared as i is above is local to the for loop, whereas MSVC6 fails to conform to this part of the standard. If you are still using MSVC6, for God's sake, stop. You can download the latest version of VC from here.

C++ compilers tend to give notoriously unhelpful error messages. (It is claimed that Apple's clang++ has better error messages than g++, but often you will still be quite out of luck, such as if you try to declare a vector of const ints.) For example:

/usr/include/c++/4.1.3/bits/stl_iterator_base_types.h: In instantiation of 'std::iterator_traits'
...

Often, this means that one of your variables is using the name of an existing function. Even if you have only included iostream, the Judge uses an old version of g++ that is less stanards-compliant than newer versions, and algorithm will automatically be included, so that names like count, fill, and transform, functions declared in that header, can trigger this error.

Also, if you somehow make a mistake with templates, such as by specifying the wrong number of template arguments, or specifying the template arguments in an order that doesn't make sense, g++ is likely to produce extremely long (and thus rather unhelpful) error messages. If you see huge error messages with lots of angle brackets, check your template usage. (Note that many of the functions in the algorithm header are templated so that they can work with generalized iterator ranges; the most common example is std::sort().)

Execution discrepancies

If your program runs correctly on your computer but produces the wrong answer on the Judge, one of the following is usually the cause:

  • Printing to standard error (at this time, whatever you print to standard error will end up in standard output, and hence cause your program to fail the test data.)
  • Misunderstanding the input and/or output format.
  • Failure to initialize a variable.
  • Accessing an array out-of-bounds.
  • Doing something you shouldn't be doing, such as popping from an empty stack, or trying to take the log of a negative number.
  • Doing something you really shouldn't be doing, such as making weird system calls.
  • Assuming that standard input and standard output are terminals (whereas in actual fact they are generally regular files), or assuming they are regular files (they might in some cases be pipes).
  • Assuming the grader is a 64-bit machine. (It isn't; most major olympiads are using 32-bit environments, simply because switching to 64-bit environments at this point would require a lot of work and provide no real advantage; and so we follow suit.)

Status Codes (and their likely meanings)

If your program is Accepted, congratulations!

The status codes WA (Wrong Answer) and CE (Compile Error) have very obvious meanings.

RE (Runtime Error) can have a variety of meanings. When a runtime error occurs, more information is often available:

  • SIGSEGV - Invalid memory access: you're going out of bounds on an array, string, vector, etc.
  • SIGFPE - Division by zero, square root of a negative, etc.
  • SIGABRT - Uncaught exception or failed assertion in C++; can also be caused by popping empty stacks and the like
  • Memory Corruption - same as SIGSEGV, but for other programming languages
  • Uncaught Exception - same as SIGABRT, but for other programming languages

IR (Invalid Return) usually occurs only for programs submitted in interpreted languages, and may indicate a compile-time error (i.e., syntax error) or a runtime error.

TLE (Time Limit Exceeded) means that your code is too slow. (Note that the time limit is per test case). Often, this may mean that your code contains an infinite loop, and your program will never stop executing. In other cases it may mean that your program will terminate, but not within the time limit indicated. (Distinguishing between the two is the famous Halting Problem, which is impossible to solve.)

MLE (Memory Limit Exceeded) means that your program tried to allocate memory beyond the memory limit indicated. This can occur if you declare a very large array, or if a data structure in your program becomes too large.

OLE (Output Limit Exceeded) occurs very rarely, and indicates that your program tried to print an unacceptably large number of characters to standard output (i.e., more than 16 million). This usually means you have an infinite loop.

IE (Internal Error) is not your fault, and usually occurs during maintenance. Contact an admin if you are concerned; they will eventually rejudge your submission.

Note for Java users: The only error message that can be trusted is Accepted. All other error messages either do not occur or may not mean what they seem to. For example, you will probably never see Memory Limit Exceeded; instead, you will simply get Wrong Answer. This is because the JVM makes it difficult to determine what actually happened.

Grading

For regular problems, the judge compares your output character for character - except that it ignores the amount of whitespace. The file check.cpp contains the source code to the judge program used for the vast majority of problems in the archive.

OK OK NOT OK NOT OK
A B C
vs.
A B C
A
B

C

vs.
A
B
C
A
B C

vs.
A B C
A BC
vs.
A B C

Some problems have special graders that take care of multiple outputs. For these, the above rules usually still apply. To be safe, though, try to match the output format shown in the sample cases exactly, in the spirit of Postel's Law: Be generous in what you accept, rigorous in what you emit. (Usually, the guy before you will follow Postel's Law too; the problem setters do their best not to put trailing spaces and extra blank lines in the input.)

Flushing output

On interactive problems such as Guess the Number, it is very important that you flush the standard output stream before each occasion on which you expect a response from the grader. For example, in Guess the Number, you have to flush after each guess, because after each guess, you expect the grader to tell you whether it was correct, too high, or too low. If you fail to do this, the grader might never receive your output, which means your program will time out while waiting for a response from the grader that will never come. This is done as follows:

  • C:
    fflush(stdout);
  • C++:
    cout.flush();
  • Pascal:
    flush(output);
  • Java:
    System.out.flush();
  • Haskell:
    hFlush stdout
  • Assembly: Output is written immediately at each sys_write call, so there is no need to flush.
  • Ruby:
    $stdout.flush
  • Python:
    sys.stdout.flush()
  • PHP:
    flush(); ob_flush();
  • OCaml:
    flush stdout;;
  • Perl:
    $stdout->flush;
    Note: This code assumes that $stdout is an IO::Handle object. Alternatively, you can use
    autoflush STDOUT 1;
    if you want to have standard output flushed after every write operation.

Often, flushes will occur automatically after each time a newline is printed, and, unless something really bad happens, standard streams are automatically flushed when a program terminates. However, do not rely on this being the case on the Judge, which may be configured differently.

BBCode

Tags

  • [quote]...[/quote] to quote a post
  • [code]...[/code] for code (language automatically detected)
  • [url]...[/url] for a link
  • [i]...[/i] italic
  • [b]...[/b] bold
  • [u][/u] underline
  • [color=red]...[/color] color
  • [size=5]...[/size] size
  • [sup]...[/sup] superscript
  • [s]...[/s] strikethrough
  • [list][*]A [*]B[/list]: list
  • A
  • B

Emoticons

Encase certain keywords between a pair of :: to make an emoticon. Here are the currently supported keywords:

 :angel: AngelSmiley.gif
 :applause: ApplauseSmiley.gif
 :biggrin: BiggrinSmiley.gif
 :confused: ConfusedSmiley.gif
 :cool: CoolSmiley.gif
 :eh: EhSmiley.gif
 :fear: FearSmiley.gif
 :impressed: ImpressedSmiley.gif
 :kidding: KiddingSmiley.gif
 :mad: MadSmiley.gif
 :naughty: NaughtySmiley.gif
 :neutral: NeutralSmiley.gif
 :rolleyes: RolleyesSmiley.gif
 :sad: SadSmiley.gif
 :sick: SickSmiley.gif
 :silenced: SilencedSmiley.gif
 :smile: SmileSmiley.gif
 :think: ThinkSmiley.gif
 :tongue: TongueSmiley.gif
 :twisted: TwistedSmiley.gif
 :whistle: WhistleSmiley.gif
 :wink: WinkSmiley.gif