Fast Input & Output

C++

Method 1: freopen with cin

The slowest method.

Method 2: freopen with scanf

Significantly faster.

Method 3: ifstream and ofstream

About as fast.

Method 4: fread and fwrite

Using FastIO from here further reduces the runtime.

Optimizations

ios::sync_with_stdio(0)

From the second resource:

This disables the synchronization between the C and C++ standard streams. By default, all standard streams are synchronized, which in practice allows you to mix C- and C++-style I/O and get sensible and expected results. If you disable the synchronization, then C++ streams are allowed to have their own independent buffers, which makes mixing C- and C++-style I/O an adventure.

Adding this immediately after main() significantly reduces the runtime of method 1.

You may also see cin.sync_with_stdio(0) and ios_base::sync_with_stdio(0). These function calls are all equivalent.

Java

Keep in mind that a Java program that only reads in $N$ and outputs a number takes 138ms on USACO.

Method 1 - Scanner

Probably the easiest way to read input in Java, though it is also extremely slow.

Method 2 - BufferedReader and .split()

BufferedReader reads line-by-line with the .readLine() method, which returns a string. Methods like Integer.parseInt() are used to convert strings into primitives, and they can directly convert a line into a number, like in Integer.parseInt(br.readLine()).

Reading input is more complicated when multiple, space-separated values are placed in a single line. In order to individually read the values in each line, the programmer usually uses the .split() method in String.

Method 3 - BufferedReader and StringTokenizer

Notice that StringTokenizer's .nextToken() for splitting strings is slightly faster than .split().

As Kattio is just a wrapper around BufferedReader and PrintWriter, it performs similarly. This method is usually fast enough and doesn't require too much typing, so we recommend that you go with this.

Method 4 - BufferedReader and StreamTokenizer

Apparently this is even faster! Though properly reading in longs would require additional work (since they are interpreted as doubles by default).

Method 5 - InputStream

Even faster than BufferedReader is a custom-written Fast I/O class that reads bytes directly from an InputStream, similarly as FastIO.h in the C++ section.

Python

Faster than the first C++ method! Significantly less if $P$ does not need to be stored.

C++

The following solution has the right time complexity, but it TLEs despite including cin.sync_with_stdio(0).

Rewriting with scanf and printf is an option:

But what if we want to stick with cin and cout?

Method 1 - Print a Single String

In general, it may be faster to store the answer in a single string and output it with a single function call. This method avoids the overhead of calling an output method many times, especially if the output is generated in many parts.

Note that the above TLEs on test 5 if cin.sync_with_stdio(0) is not included.

Also, the change in runtime if we use scanf and printf appears to be negligible.

Method 2 - cin.tie(0)

From the second resource:

This unties cin from cout. Tied streams ensure that one stream is flushed automatically before each I/O operation on the other stream.

By default cin is tied to cout to ensure a sensible user interaction. For example:

std::cout << "Enter name:";
std::cin >> name;

If cin and cout are tied, you can expect the output to be flushed (i.e., visible on the console) before the program prompts input from the user. If you untie the streams, the program might block waiting for the user to enter their name but the "Enter name" message is not yet visible (because cout is buffered by default, output is flushed/displayed on the console only on demand or when the buffer is full).

So if you untie cin from cout, you must make sure to flush cout manually every time you want to display something before expecting input on cin.

cin.tie(0), cout.sync_with_stdio(0);

Output streams in C++ (such as cout and ofstream) are buffered, meaning that they don't immediately print their output, but store some of it. At some point, the buffer's contents are written (i.e. "flushed") to the output device (e.g the standard output stream or a file). Buffering the output helps with efficiency if accessing the output device (like a file) is slow.

Because endl always flushes the output, using \n instead may avoid unnecessary flushes.

• With endl in place of \n, the above code TLEs on test 3.
• \n may also flush the output if cin.tie(0) is not present, so removing cin.tie(0) from the above code also TLEs on test 3.

Java

In general, it may be faster to store the answer in a single StringBuilder and output it with a single function call. This method avoids the overhead of calling an output method many times, especially if the output is generated in many parts.

When printing to the standard output stream in Java, it is faster to use new PrintWriter(System.out) than System.out (as all the methods above do). The syntax for PrintWriter is equivalent to that of System.out so it should be easy to use. The only difference is that one has to call .flush() or .close() on the PrintWriter at the very end of the program in order to write the output.