Data Types

Author: Darren Yao

Overview of the basic data types needed for competitive programming.


C++

Resources
CPPR

sizes + ranges

IUSACO

module is based off this

CPH

Integers, Modular arithmetic, Floating point numbers

PAPS

plenty of exercises


C++: Common Fundamental Data Types

Note: These numbers may vary depending on your machine and/or compiler. For more fundamental data types, check the the first resource in the table above.

Typesintlong longdoubleboolchar
Description32-bit integer64-bit integerDouble-precision floatTrue/False value8-bit character
Size (bytes)48811
Range231-2^{31} to 23112^{31}-1263-2^{63} to 26312^{63}-1-1.7E+308 to +1.7E+30800 or 11 (true or false)27-2^7 to 2712^7-1

Java

Resources
JavaDocs
IUSACO

module is based off this

Java: Common Primitive Data Types

For more primitive data types, check the the first resource in the table above.


Typesintlongdoublebooleanchar
Description32-bit integer64-bit integerDouble-precision floatTrue/False value16-bit Unicode character
Size (bytes)4881 bit(*)2
Range231-2^{31} to 23112^{31}-1263-2^{63} to 26312^{63}-1-1.7E+308 to +1.7E+308true/false\u0000 to \uffff (0655350-65535)

*Note: It's unlikely that booleans will actually use only 1 bit of memory, as in most cases data types must be aligned to bytes. However, only one bit of information can be stored in them.

Python

Resources
IUSACO

module is based off this

Python

Typesintfloatboolstr
DescriptionArbitrary-size integerDouble-precision (64 bit) IEEE 754 floatTrue/False valueString
ValuesAny integer-1.7E+308 to +1.7E+308true/falseAny length of text

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 2147483648-2\,147\,483\,648 and 21474836472\,147\,483\,647, which is roughly equal to ±2109\pm 2 \cdot 10^9.

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 9223372036854775808-9\,223\,372\,036\,854\,775\,808 and 92233720368547758079\,223\,372\,036\,854\,775\,807 which is roughly equal to ±9×1018\pm 9 \times 10^{18}. In Python, ints 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 for lower divisions 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.

Additionally, there exist 16-bit integers (short in C++ and Java). However, these are generally not useful as the extra memory saved by using them is usually negligible. Unsigned integers (unsigned int, unsigned long long, etc.) also exist. They aren't used as frequently, though the 2-fold increase in size is sometimes the difference between overflowing and not overflowing.

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 ϵ=109\epsilon=10^{-9}.

  • If your output is xx and the answer is yy, the absolute difference is xy|x-y|.
  • If your output is xx and the answer is yy, the relative difference is xyy\frac{|x-y|}{|y|}.

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 10610^6 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: true and false. We'll usually use booleans to mark whether a certain process is done, and arrays of booleans to mark which components of an algorithm have finished. Booleans require 1 byte (8 bits) of storage, not 1 bit, wasting the other 7 bits of storage. To use less memory, one can use bitsets (std::bitset in C++ / BitSet in Java). Unfortunately, bitsets are not available in Python.

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, both cout << ('f' - 'a'); in C++ and System.out.print('f' - 'a'); in Java will print 5. In Java, characters are 16 bits, while in C/C++, characters are 8 bits.

Strings are effectively arrays of characters. You can easily access the character at a certain index and take substrings of the string (charAt() and substring() in Java).

Module Progress:

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!