Author: Darren Yao
Overview of the basic data types needed for competitive programming.
There are several main data types that are used in contests: integers, floating point numbers, booleans, characters, and strings. Assuming that you are familiar with the language you are using, this should be mostly review.
The normal 32-bit integer data type (
int in C++ and Java) supports values
between and , which is roughly equal to
Some problems require you to use 64-bit integers (
long long in C++ and
long in Java) instead of 32-bit integers (
int). 64-bit integers are less
likely to have overflow issues, since they can store any number between
is roughly equal to . In Python,
have unlimited size.
Sometimes (but not always) a USACO problem statement (ex. Haircut) will contain a warning such as the following:
Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).
Contest problems are usually set such that the 64-bit integer is sufficient, so
it might be a good idea to use 64-bit integers in place of 32-bit integers
everywhere. Of course, you shouldn't do this when time and/or memory limits are
tight, which may be the case in higher divisions of USACO. Also note that in
Java, you will need to cast
long back to
int when accessing array indices.
Floating point numbers are used to store decimal values. It is important to
know that floating point numbers are not exact, because the binary architecture
of computers can only store decimals to a certain precision. Hence, we should
always expect that floating point numbers are slightly off, so it's generally a
bad idea to compare two floating-point numbers for exact equality (
Contest problems will usually accommodate the inaccuracy of floating point numbers by checking if the absolute or relative difference between your output and the answer is less than some small constant like .
- If your output is and the answer is , the absolute difference is .
- If your output is and the answer is , the relative difference is .
This is not the case for USACO, where problems generally have a unique correct output. So when floating point is necessary, the output format will be something along the lines of "Print times the maximum probability of receiving exactly one accepted invitation, rounded down to the nearest integer." (ex. Cow Dating).
Boolean variables have two possible states:
usually use booleans to mark whether a certain process is done, and arrays of
booleans to mark which components of an algorithm have finished.
Character variables represent a single character. They are returned when you
access the character at a certain index within a string. Characters are
represented using the ASCII standard, which assigns each character to a
corresponding integer. This allows us to do arithmetic with them; for example,
cout << ('f' - 'a'); in C++ and
System.out.print('f' - 'a'); in Java
5. In Java, characters are 16 bits, while in C/C++, characters are
Strings are stored as an array of characters. On the back end, there is an
ArrayList (you can think of it as a more flexible array which can change its
size if more space is needed), that automatically updates when two strings are
added. There are a few methods such as
charAt() in Java that
are helpful to know. A loop can be used to access each character of an unknown
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!