Tips

Tips for Java Contestants

Reading Input

Java's java.util.Scanner on System.in is extremely slow, having to do a really large number of highly expensive conversions. If you time out on a problem while using the Scanner class, consider switching to java.io.BufferedReader for reading input.

Scanner in = new Scanner(System.in);
int a = in.nextInt();
int b = in.nextInt();

becomes

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());

You should attempt to use BufferedReader whenever you need to read input. It's over 100 times faster!

Note: the underlying input stream is not a file stream, so polling methods like BufferedReader.ready might spuriously return false even if the end of the input has not been reached.

Sorting Arrays

Java 7 uses a dual-pivot quicksort algorithm to sort primitive arrays. While this provides fast sorting in most cases, it has a worst-case time complexity of \mathcal{O}(N^2) - terrible for large arrays. If your code times out while using Arrays.sort(primitive[]), consider using Collections.sort or Arrays.sort(Object[]). The latter uses a Timsort implementation, which is guaranteed \mathcal{O}(N \log N) worst case performance: much faster than quicksort's \mathcal{O}(N^2). In most cases, converting code using primitive sorting to Object sorting is trivial:

int[] a = new int[N];
for(int i = 0; i < N; i++) {
    a[i] = ...
}
Arrays.sort(a);

becomes

Integer[] a = new Integer[N];
for(int i = 0; i < N; i++) {
    a[i] = ...
}
Arrays.sort(a);

The only difference in the two variations is the change from an int datatype to an Integer datatype. In most aspects they are equivalent, except that Integers are objects (and hence use the Array.sort(Object[]) method overload, instead of the potentially much slower Arrays.sort(int[])).

Do note, however, that sorting on Object arrays is generally much slower than sorting on primitive arrays. When you're sure primitive array sorting will do fine (and it usually does), do not use Object array sorting.

hsa.Console

Some ICS courses teach the usage of the hsa.Console object for doing console manipulation. The DMOJ does not support the hsa.Console class. The DMOJ is primarily a text-based input/output system, so using standard IO methods is required.

Essentially, you should use System.out.print instead of hsa.Console.print, and the BufferedReader or Scanner (discouraged: see above) classes instead of hsa.Console.readChar.

Tips for Python Contestants

Execution Speed

Python, being an interpreted language, is very noticeably slower than compiled languages such as C, C++, or Java. The speed difference is so significant that Python may be up to 100 to 400 times slower than the aforementioned languages.

In the real world, this is less of a problem than on algorithmic competitions and online judges. This issue can be alleviated by the usage of the PyPy interpreter (as opposed to the CPython interpreter), so if you're sure your solution is correct, but times out, try resubmitting with PyPy. Many problems on this judge are designed so that a solution with a good running time in Python can get Accepted, but you should note that for some problems, it is impossible to get Python accepted. The reason is that if the time limits were set so that a correct Python can pass, an incorrect solution in faster languages such as C, C++, or Java would also pass.

Unfortunately, there is nothing we can do with the judge to make your Python submissions run as fast as C, so the best you can do is to learn one of the aforementioned languages (if you haven't already) to use in times when Python just isn't fast enough.

Reading Input

Often, your program will be bottlenecked not by your algorithm's speed but by the speed that you can read and write data from input and to output. You can speed up input by reading directly from sys.stdin.

import sys
for line in sys.stdin:
    # Do something

sys.stdin is a file-like object. That is, you can manipulate it just as you would a file returned by open.

A quick technique for faster input is to simply use sys.stdin.readline in place of all your string input calls.

For Python 2, this means

import sys
raw_input = sys.stdin.readline

For Python 3, this means

import sys
input = sys.stdin.readline

An even faster and better solution is to buffer all of the problem input (if you know the input will be of a manageable size), and parse it yourself:

import sys
all_data = sys.stdin.read().split('\n')

The above example stores all the lines of input in a list all_data. all_data[0] contains the first line of input, all_data[1] contains the second and so on. This is the fastest possible way to input data in Python.

Faster Reading of Real and Integer Values

This section is solely for Python 2 contestants (Python 3 does not have this issue).

If struggling with IO speed, an easy technique is to change all your input calls to sys.stdin.readline calls and perform the casting yourself. If you know that N will be an integer, you can scrap the input call and do the type conversion yourself.

N = input()

becomes

N = int(sys.stdin.readline())

Performing your own casting is much faster! It also protects you from nasty trailing returns in input that may exist on other online judges.

Benchmark data (Python 2), reading a million ints from standard input:

  • input(): 3.064 seconds
  • int(raw_input()): 0.844 seconds
  • raw_input = sys.stdin.readline; int(raw_input()): 0.427 seconds

Benchmark data (Python 3), reading a million ints from standard input:

  • int(input()): 0.879 seconds
  • input = sys.stdin.readline; int(input()): 0.294 seconds

It is without any doubt that int(sys.stdin.readline()) should be used to read integers, float(sys.stdin.readline()) for real numbers and so on. Python 3 contestants should also make use of sys.stdin whenever they can.

Using site functions (like exit)

The DMOJ denies access to the site module, so functions that are injected into the builtin namespace — like exit — are disallowed.

In the case of exit, use sys.exit() instead.

Tips for C/C++ Contestants

Allocating

Refrain from declaring big arrays as local variables, as it will often cause you to run out of stack space and fail with a Runtime Error.

Instead of doing:

int main()
{
    int N;
    scanf("%d", &N);
    int arr[N];
    for(int i = 0; i < N; i++) scanf("%d", &arr[i]);
}

consider:

int arr[100001];
int main()
{
    int N;
    scanf("%d", &N);
    for(int i = 0; i < N; i++) scanf("%d", &arr[i]);
}

Declaring big arrays in global scope is a much safer approach as long as you know the maximum bound of N (and almost all problems give you upper bounds). Be wary of out of bounds array indices, though.

Input and Output

It is recommended for C++ users to use C-style input and output, namely scanf and printf instead of cin and cout for performance reasons.

If you must use cin and cout, you can put these two lines of code at the top of your main function:

int main()
{
    cin.sync_with_stdio(0);
    cin.tie(0);
    ...
}

to speed up the cin stream. This will unsync cin with scanf and cout. Note that you should not use scanf after unsyncing with stdio.

Additionally, you should not use endl, but rather \n to output newlines when flushing is not required. endl's flushing behavior can potentially cause your program to receive TLE instead of AC.

Finally, if the problem only requires unsigned integral data types to be read, you can prepend this macro to the top of your source:

#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;

Instead of std::cin >> n, or scanf("%d", &n), you would use scan(n).

int, long, and long long

On the judge, int is 32-bit, long long is 64-bit, and long can be either 32- or 64-bit depending on which judge your submission is graded on. Therefore, it is recommended to use either int or long long, but not long.