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 ~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 ~O(N \log N)~ worst case performance: much faster than quicksort’s ~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);
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 Integer
s 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
import sys
input = sys.stdin.readline
import sys
all_data = sys.stdin.read().split('\n')
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()
N = int(sys.stdin.readline())
Benchmark data (Python 2), reading a million ints from standard input:
input()
: ~4.87823~ secondsint(raw_input())
: ~4.83112~ secondsraw_input = sys.stdin.readline; int(raw_input())
: ~0.69960~ 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.
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]);
}
int arr[100001];
int main()
{
int N;
scanf("%d", &N);
for(int i = 0; i < N; i++) scanf("%d", &arr[i]);
}
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 _;
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
.