# Data Types

Author: Darren Yao

### Prerequisites

Learn about the basic data types needed for competitive programming.

C++

Resources | |||
---|---|---|---|

IUSACO | module is based off this | ||

CPPR | sizes + ranges | ||

CPH | Integers, Modular arithmetic, Floating point numbers | ||

PAPS | plenty of exercises |

Java

Resources | |||
---|---|---|---|

IUSACO | module is based off this |

Python

Resources | |||
---|---|---|---|

IUSACO | module is based off this | ||

Python |

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 $−2\,147\,483\,648$ and $2\,147\,483\,647$, which is roughly equal to $\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 $-9\,223\,372\,036\,854\,775\,808$ and $9\,223\,372\,036\,854\,775\,807$ which is roughly equal to $\pm 9 \times 10^{18}$. In Python, `int`

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

- If your output is $x$ and the answer is $y$, the absolute difference is $|x-y|$.
- If your output is $x$ and the answer is $y$, the relative difference is $\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 $10^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.

**Character** variables represent a single Unicode 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`

.

**Strings** are stored as an array of characters. You can easily access the character at a certain index and take substrings of the string. String problems on USACO Bronze or Silver generally don't involve any special data structures, and can be solved using relatively elementary methods.