ACPC 2024 - Language-Specific Tips & Tricks

After correctness, the main metric of success in competitive programming is runtime duration. Every problem has a static amount of time that all solutions have to run within. However, some languages are faster than others. In order to level the playing field and allow for greater language support in this competition, we are including this document which we hope will provide very simple tips on how to get free performance gains in this contest as well as provide some warnings about pitfalls that might make your solution timeout.

That being said, if you know C++, this is the most common language in competitive programming and all of the problems were designed and tested with this language in mind.

0 All Languages

0.1 Precision

For all typed languages, use 64-bit primitives wherever possible. This will ensure you do not get unexpected overflow issues in your solutions.

C++ – long long and double
Java – long and double

1 C++

1.1 IO

The easiest trick to get IO performance out of your C++ application is to include the following macro at the start of your solution:

#define SPEED \

std::ios::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(0);

void main() {
SPEED;
/* ... */
}

This prevents some default behavior with std::cin where it will force std::cout to flush before reading input. Since competitive programming often involves reading large amounts of data, performing some algorithm on this data, and then producing output, this tying behavior causes unnecessary overhead that can greatly affect performance.

2 Python

2.1 Submission

Codeforces includes a few options for compilers/runtimes when submitting your Python solution. We generally recommend using PyPy as such:

2.2 IO

Python IO is often invoked through the input() and print() functions. However, you can get a large performance increase by using sys.stdin and sys.stdout as such:

import sys

# Parse two integers from the first line
[N, M] = [int(x) for x in sys.stdin.readline().split()]
# ...
# Print an integer and a newline character
sys.stdout.write(str(x))
sys.stdout.write('\n')

These directly access the C standard input and output streams with very little overhead, unlike the standard Python IO functions.

2.3 Strings

Python strings are immutable. As such, if you want to build a string out of smaller results – such as converting a list to a string – then you may be doing a large number of costly copying operations without noticing.

The easiest workaround to this is to build a list of your results instead before converting it into a string all at once with the join() function. This will work for any type of list whether its a list of characters, a list of strings, or a list of integers like in this example:

import sys

# A list of integers
fibo = [1, 1, 2, 3, 5, 8, 13]
# Convert each integer into a string
# Then join the list with spaces in between each value
out_string = ' '.join([str(x) for x in fibo])
sys.stdout.write(out_string)
sys.stdout.write('\n')

Here, we do a list comprehension to convert each of our integers to a string (unnecessary if concatenating strings) and then we call join() on a string containing one whitespace character (which acts as our delimiter). This collects our list of stringified integers into one string where each value is separated by one whitespace character.

3 Java

3.1 IO

For input, a combination of BufferedReader and StringTokenizer is recommended. Here’s a simple static class that utilizes these, where the FastScanner.next() function will return the next space-separated string from the input:

static class FastScanner {
BufferedReader br =

new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer("");
String next() {
while (!st.hasMoreTokens())
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
return st.nextToken();
}
}

For output, it is recommended to combine output into a single string before printing. As is described in the next section, StringBuilder should be used for all string generation:

// Print space-separated elements of integer array on a line
StringBuilder sb = new StringBuilder();
for(int i: array) {
// append() works with Strings and all primitive data types
sb.append(i);
sb.append(' ');
}
System.out.println(sb);

3.2 Strings

Java strings are immutable. As such, if you want to build a string out of smaller results – such as converting an array to a string – then you may be doing a large number of costly copying operations without noticing.

Thankfully, Java includes a class for building strings, conveniently named StringBuilder. This has an append() function that will accept any primitive data type, string, or object with a toString() definition. An example of using StringBuilder is included in the output portion of the IO section.