In this comprehensive guide, we delve into the world of Competitive Programming with C++. Learn the core principles of Competitive Programming, explore various algorithmic examples, and understand performance differences through detailed code comparisons. Perfect for developers looking to optimize their coding skills and boost algorithm efficiency.

1. Introduction

C++ remains one of the most popular languages in competitive programming due to its performance, flexibility, and rich standard library. Mastering efficient C++ techniques is crucial for success in programming contests, where solving complex problems under strict time and memory constraints is the norm. This guide delves into advanced C++ programming strategies, focusing on Dynamic Programming - a powerful algorithmic paradigm that solves complex problems by breaking them down into simpler subproblems. By optimizing input/output operations, leveraging modern C++ features, and utilizing efficient data structures and algorithms, we’ll explore how to apply Dynamic Programming techniques to tackle a wide range of computational challenges.

For instance, one common optimization in competitive programming is to speed up input/output operations. By default, C++ performs synchronized I/O with C’s standard I/O libraries, which can be slower. A simple trick to improve I/O speed is disabling this synchronization:

    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

This small change can make a significant difference when dealing with large input datasets. Throughout this guide, we will cover similar techniques, along with advanced input/output operations, efficient use of data structures like arrays and vectors, and modern C++20 features that help streamline your code. You’ll also learn optimizations to minimize overhead and how to effectively leverage STL containers and algorithms to improve both runtime performance and code readability. Whether you are solving large-scale data processing problems or optimizing for time-critical solutions, the strategies in this guide will equip you to perform at a high level in programming contests.

We begin by exploring various methods to strengthen file I/O and array handling, which are fundamental to processing large datasets quickly. The guide then progresses through different looping constructs, from basic for and while loops to more advanced C++20 features like range-based for loops with views and parallel execution policies. We also cover important optimizations such as minimizing typing overhead, utilizing the Standard Template Library (STL) effectively, and employing memory-efficient techniques like std::span. Throughout this journey, we’ll focus on how these C++ features and optimizations can be applied to implement efficient Dynamic Programming solutions, enabling you to solve complex algorithmic puzzles with improved performance and reduced memory usage.

C++ is particularly effective for solving a wide range of problems in competitive programming. Some common types of problems where C++ excels include:

1. Array Manipulation: Efficiently processing and querying large arrays or sequences.
2. Graph Algorithms: Implementing complex graph traversals and shortest path algorithms.
3. String Processing: Handling string matching, parsing, and manipulation tasks.
4. Data Structures: Implementing and utilizing advanced data structures like segment trees or Fenwick trees.
5. Computational Geometry: Solving geometric problems with high precision and efficiency.

These problem types demonstrate how C++’s performance and rich standard library can be leveraged to create optimal solutions in competitive programming scenarios.

By mastering these C++20 techniques, you’ll be well-equipped to tackle a wide range of competitive programming challenges. Whether you’re dealing with large-scale data processing, intricate algorithmic puzzles, or time-critical optimizations, the strategies outlined in this guide will provide you with the tools to write faster, more efficient code. This knowledge not only boosts your performance in competitions but also deepens your understanding of C++ and algorithmic thinking, skills that are valuable beyond the competitive arena.

2. C++ Competitive Programming Hacks

In this section, we’ll cover essential tips and tricks that will help you improve your efficiency and performance in competitive programming using C++. From mastering typing speed to reducing code verbosity and handling complexity, each aspect plays a crucial role in gaining a competitive edge.

C++ is known for its speed and flexibility, but using it effectively requires a deep understanding of both the language and the common pitfalls that arise in competitive programmings. The goal here is to help you streamline your coding process, minimize errors, and ensure that your solutions run as efficiently as possible.

We’ll break down these tips into the following areas:

• Typing Efficiency: How to type faster and more accurately, which can save you valuable time during competitive programming.
• Code Reduction Techniques: Ways to reduce code size without sacrificing clarity or correctness, using C++ features like the Standard Template Library (STL).
• Managing Complexity: Strategies to handle the time and space complexity of algorithms, ensuring that your solutions scale efficiently with larger inputs.

By applying these hacks, you’ll be better equipped to tackle the challenges of competitive programming with C++ and improve your overall performance. Keep in mind that the code and techniques discussed here are optimized specifically for competitive programming environments, where the code is written for single-use and will not be maintained or reused. These approaches may not be suitable for professional development, where code readability, maintainability, and long-term reliability are critical.

2.1 Typing Tips

If you don’t type quickly, you should invest at least two hours per week on the website: https://www.speedcoder.net. Once you have completed the basic course, select the C++ lessons and practice regularly. Time is crucial in competitive programming, and slow typing can be disastrous.

To expand on this, efficient typing isn’t just about speed; it’s about reducing errors and maintaining a steady flow of code. When you’re in a competitive programming, every second matters. Correcting frequent typos or having to look at your keyboard will significantly slow down your progress. Touch typing—knowing the layout of the keyboard and typing without looking—becomes a vital skill.

2.2 Why Typing Speed Matters

In a typical programming competitive programming, you’ll have to solve several problems within a fixed time frame. Faster typing allows you to focus more on problem-solving rather than struggling to input the code. However, typing speed without accuracy is meaningless. Accurate and fast typing ensures that once you have the solution, you can implement it efficiently.

Typing slow or with many errors leads to:

• Lost time correcting mistakes
• Distractions from your problem-solving process
• Higher risk of failing to complete solutions on time

You should aim for a typing speed of at least 60 words per minute (WPM) with high accuracy. On platforms like https://www.speedcoder.net, you can practice typing specific code syntax, which is more effective for programmers compared to general typing lessons. For example, learning C++ or Python shortcuts helps improve your typing speed in actual coding scenarios.

2.3 Advanced Typing Techniques for Programmers

Here are some additional tips to improve your typing for competitive programming:

1. Use IDE shortcuts: 1. Use IDE shortcuts: Learn keyboard shortcuts for your favorite Integrated Development Environment (IDE). Navigating and editing code using shortcuts reduces time spent moving between mouse and keyboard. In the case of ICPC contests, the IDE provided will typically be Eclipse, so it’s crucial to familiarize yourself with its shortcuts and navigation to maximize efficiency during the competitive programming. However, it’s important to note that the choice of IDE may change, and contestants should always check the specific rules and environments for each competition.
2. Focus on frequent patterns: As you practice, focus on typing patterns you use frequently, such as loops, if-else conditions, and function declarations. Automating these patterns in your muscle memory will save valuable time.
3. Practice algorithm templates: Some problems require similar algorithms, such as dynamic programming, sorting, or tree traversal. By practicing typing these algorithms regularly, you’ll be able to quickly implement them during competitive programmings.

In competitive programming, every second counts, and being proficient with your typing can give you a significant advantage.

2.4 Typing Less in Competitive Programming

In competitive programming, time is a critical resource. Therefore, optimizing typing speed and avoiding repetitive code can make a significant difference. Below, we will discuss strategies to minimize typing when working with std::vector during competitive programmings, where access to the internet or pre-prepared code snippets may be restricted.

2.4.1. Using #define for std::vector Abbreviations

We can use #define to create short aliases for common vector types. This is particularly useful when you need to declare multiple vectors throughout the code.

#define VI std::vector<int>
#define VVI std::vector<std::vector<int>>
#define VS std::vector<std::string>

With these definitions, declaring vectors becomes much faster:

VI numbers;  // std::vector<int> numbers;
VVI matrix;  // std::vector<std::vector<int>> matrix;
VS words;    // std::vector<std::string> words;

However, it’s important to note that in larger, professional projects, using #define for type aliases is generally discouraged because it does not respect C++ scoping rules and can lead to unexpected behavior during debugging. In competitive programming, where speed is essential, this technique can be useful, but it should be avoided in long-term or collaborative codebases.

2.4.2. Predefined Utility Functions

Another effective strategy is to define utility functions that you can reuse for common vector operations, such as reading from input, printing, or performing operations like sorting or summing elements.

Reading Vectors:

#define FAST_IO std::ios::sync_with_stdio(false); std::cin.tie(nullptr);

void read_vector(VI& vec, int n) {
    if (n > 0) vec.reserve(static_cast<size_t>(n));
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        vec.push_back(x);
    }
}

With the read_vector function, you can quickly read a vector of n elements:

FAST_IO

VI numbers;
read_vector(numbers, n);

Printing Vectors:

void print_vector(const VI& vec) {
    for (const int& x : vec) {
        std::cout << x << " ";
    }
    std::cout << "\n";
}

This function allows you to easily print the contents of a vector:

print_vector(numbers);

2.4.3. Predefining Common Operations

If you know that certain operations, such as sorting or summing elements, are frequent in a competitive programming, consider defining these operations at the beginning of the code.

Sorting Vectors:

#define SORT_VECTOR(vec) std::sort(vec.begin(), vec.end())

You can then sort any vector quickly:

SORT_VECTOR(numbers);

Summing Elements:

int sum_vector(const VI& vec) {
    return std::accumulate(vec.begin(), vec.end(), 0);
}

To calculate the sum of a vector’s elements:

int total = sum_vector(numbers);

2.4.4. Using Lambda Functions

In C++11 and later versions, lambda functions can be a quick and concise way to define operations inline for vectors:

auto print_square = [](const VI& vec) {
    for (int x : vec) {
        std::cout << x * x << " ";
    }
    std::cout << "\n";
};

These inline functions can be defined and used without the need to write complete functions:

print_square(numbers);

While lambda functions can be very useful for quick, one-off operations, it’s important to note that excessive use of lambdas, especially complex ones, can make code harder to read and maintain. In competitive programming, where code clarity might be sacrificed for speed, this may be less of a concern. However, it’s a good practice to be mindful of code readability, especially when debugging complex algorithms.

2.4.5 Prefer Not to Use #define

Another way to reduce typing time is by using typedef or using to create abbreviations for frequently used vector types:

typedef std::vector<int> VI;
typedef std::vector<std::vector<int>> VVI;
using VS = std::vector<std::string>;

In many cases, the use of #define can be replaced with more modern and safe C++ constructs like using, typedef, or constexpr. #define does not respect scoping rules and does not offer type checking, which can lead to unintended behavior. Using typedef or using provides better type safety and integrates smoothly with the C++ type system, making the code more predictable and easier to debug.

1. Replacing #define with Type Aliases

   For example:

   #define VI std::vector<int>
   #define VVI std::vector<std::vector<int>>
   #define VS std::vector<std::string>
   

   Can be replaced with using or typedef to create type aliases:

   using VI = std::vector<int>;
   using VVI = std::vector<std::vector<int>>;
   using VS = std::vector<std::string>;
   
   // Or using typedef (more common in C++98/C++03)
   typedef std::vector<int> VI;
   typedef std::vector<std::vector<int>> VVI;
   typedef std::vector<std::string> VS;
   

   using and typedef are preferred because they respect C++ scoping rules and offer better support for debugging, making the code more secure and readable.

2. Replacing #define with Constants

3. Using constexpr in Functions

   If you have macros that perform calculations, you can replace them with constexpr functions:

   Example:

   #define SQUARE(x) ((x) * (x))
   

   Can be replaced with:

   constexpr int square(int x) {
       return x * x;
   }
   

   constexpr functions provide type safety, avoid unexpected side effects, and allow the compiler to evaluate the expression at compile-time, resulting in more efficient and safer code.

For competitive programming, using #define might seem like the fastest way to reduce typing and speed up coding. However, using typedef or using is generally more efficient because it avoids potential issues with macros and integrates better with the compiler. While reducing variable names or abbreviating functions might save time during a competitive programming, remember that in professional code, clarity and maintainability are far more important. Therefore, avoid using shortened names and unsafe constructs like #define in production code, libraries, or larger projects.

3. Optimizing File I/O in C++ for competitive programmings

In many competitive programming contests, especially those involving large datasets, the program is required to read input from a file that can be very large. For this reason, it is crucial to optimize how files are read. Efficient file handling can make the difference between a solution that completes within the time limits and one that does not. Implementing techniques to speed up file I/O is indispensable for handling such cases effectively.

3.1 Disabling I/O Synchronization

To improve the performance of input/output (I/O) operations, we disable the synchronization between the standard C and C++ I/O libraries:

std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

• The function std::ios::sync_with_stdio(false) disables the synchronization of the C++ streams with the C streams, allowing the program to perform I/O operations more quickly.
• std::cin.tie(nullptr) detaches the input stream (std::cin) from the output stream (std::cout), preventing automatic flushes that can cause delays.

When we disable synchronization with std::ios::sync_with_stdio(false);, the program benefits from better performance in I/O operations since it no longer needs to synchronize the C++ input/output functions (std::cin, std::cout) with the C functions (scanf, printf).

This synchronization, when enabled, introduces overhead because the system ensures that both libraries can be used simultaneously without conflict. By removing this synchronization, we eliminate that overhead, allowing I/O operations to be processed more directly and faster.

This optimization is particularly beneficial in programs that perform a large number of read and write operations, such as when processing large amounts of data from files. Additionally, by using std::cin.tie(nullptr);, we prevent std::cout from being automatically flushed before each input operation, avoiding another form of latency that could impact performance in I/O-heavy contexts.

3.2 Command Line Argument Checking

Before proceeding with execution, the code checks if exactly one argument was passed through the command line, which represents the name of the file to be read:

if (argc != 2) {
    std::cerr << "Usage: " << argv[0] << " <file_name>\n";
    return 1;
}

• argc is the number of arguments passed to the program, including the name of the executable.
• argv is an array of strings containing the arguments.
• If the number of arguments is not 2, the program prints an error message and exits with return 1, indicating failure.

3.3 Opening and Verifying the File

The code attempts to open the specified file and checks whether the opening was successful:

std::ifstream file(argv[1]);
if (!file) {
    std::cerr << "Error opening file: " << argv[1] << "\n";
    return 1;
}

• std::ifstream file(argv[1]); attempts to open the file for reading.
• If file is not in a valid state (i.e., the file couldn’t be opened), an error message is displayed, and the program terminates.

While good practice in general software development, is usually unnecessary in competitive programming contests. Instead, you can often assume the file exists and start reading from it directly. This saves valuable coding time and simplifies your solution.

4. Introduction to File I/O in C++

In C++, file input and output (I/O) operations are handled through classes provided by the <fstream> library. The three main classes used for this purpose are std::ifstream, std::ofstream, and std::fstream. Each of these classes is specialized for different types of I/O operations.

4.1 std::ifstream: File Reading

The std::ifstream class (input file stream) is used exclusively for reading files. It inherits from std::istream, the base class for all input operations in C++.

4.1.1 Opening Files for Reading

In our code, we use std::ifstream to open a text file and read its contents:

std::ifstream file(argv[1]);

• std::ifstream file(argv[1]);: Tries to open the file whose name is passed as a command-line argument. If the file cannot be opened, the file stream will be invalid.

Off course we can use std::ifstream to read files from command line:

#include <fstream>
#include <iostream>
#include <string>

int main(int argc, char* argv[]) {
    if (argc != 2) {
        std::cerr << "Usage: " << argv[0] << " <filename>\n";
        return 1;
    }

    // Abre o arquivo apenas para leitura
    std::ifstream file(argv[1]);

    if (!file.is_open()) {
        std::cerr << "Error: Could not open the file " << argv[1] << "\n";
        return 1;
    }

    std::string line;

    // Lê o conteúdo do arquivo linha por linha e exibe no console
    std::cout << "Contents of the file:\n";
    while (std::getline(file, line)) {
        std::cout << line << "\n";
    }

    file.close();
    return 0;
}

4.1.2 Verifying File Opening

After attempting to open the file, it’s crucial to check whether the opening was successful:

if (!file) {
    std::cerr << "Error opening file: " << argv[1] << "\n";
    return 1;
}

• if (!file): Checks if the file stream is in an invalid state (which indicates the file was not opened correctly). If the file can’t be opened, an error message is displayed, and the program exits.

Again, in competitive programmings, the input file will most often be handled by an automated testing system, so you probably won’t need to check whether the file opened correctly or not.

4.1.3 File Reading

Once the file is successfully opened, we can read its contents:

std::getline(file, line);
while (file >> num) {
    vec.push_back(num);
}

• std::getline(file, line);: Reads a full line from the file and stores it in the string line.
• file >> num: Reads numbers from the file and stores them in num, which are then added to the vector vec using vec.push_back(num);.

4.1.4 File Closing

After finishing with a file, it should be closed to free the associated resources. This happens automatically when the std::ifstream object is destroyed, but it can also be done explicitly:

file.close();

• file.close();: Closes the file manually. Although the file is automatically closed when the object goes out of scope, explicitly closing the file can be useful to ensure the data is correctly released before the program ends or before opening another file.

4.1.5 File Writing - std::ofstream

While we didn’t use std::ofstream in the provided code, it’s important to mention it. The std::ofstream class (output file stream) is used for writing to files. It inherits from std::ostream, the base class for all output operations in C++.

1. Opening Files for Writing

   The syntax for opening a file for writing using std::ofstream is similar to that of std::ifstream:

   std::ofstream outFile("output.txt");
   

   • std::ofstream outFile("output.txt");: Opens or creates a file called output.txt for writing. If the file already exists, its contents will be truncated (erased).

4.1.6 File Reading and Writing - std::fstream

The std::fstream class combines the functionality of both std::ifstream and std::ofstream, allowing for both reading from and writing to files. It inherits from std::iostream, the base class for bidirectional I/O operations.

An example of how to open a file for both reading and writing would be:

std::fstream file("data.txt", std::ios::in | std::ios::out);

• std::fstream file("data.txt", std::ios::in | std::ios::out);: Opens data.txt for both reading and writing. The parameter std::ios::in | std::ios::out specifies that the file should be opened for both input and output.

Or to use files read from command line we could use:

#include <fstream>
#include <iostream>
#include <string>

int main(int argc, char* argv[]) {
    if (argc != 2) {
        std::cerr << "Usage: " << argv[0] << " <filename>\n";
        return 1;
    }

    // Abre o arquivo com leitura e escrita
    std::fstream file(argv[1], std::ios::in | std::ios::out);

    if (!file.is_open()) {
        std::cerr << "Error: Could not open the file " << argv[1] << "\n";
        return 1;
    }

    std::string line;

    // Lê o conteúdo do arquivo e exibe no console
    std::cout << "Contents of the file:\n";
    while (std::getline(file, line)) {
        std::cout << line << "\n";
    }

    // Reposiciona o ponteiro para o início do arquivo
    file.clear(); // Limpa qualquer flag de erro
    file.seekg(0, std::ios::beg);

    // Adiciona uma nova linha ao final do arquivo
    file << "\nNew line added to the file.\n";

    // Reposiciona o ponteiro para o início novamente para leitura após a escrita
    file.clear();
    file.seekg(0, std::ios::beg);

    std::cout << "\nUpdated contents of the file:\n";

    // Lê e exibe o conteúdo atualizado do arquivo
    while (std::getline(file, line)) {
        std::cout << line << "\n";
    }

    file.close();
    return 0;
}

4.1.7 File Opening Modes

When opening files, we can specify different opening modes using values from the std::ios_base::openmode enumeration. Some of the most common modes include:

• std::ios::in: Open for reading (default for std::ifstream).
• std::ios::out: Open for writing (default for std::ofstream).
• std::ios::app: Open for writing at the end of the file, without truncating it.
• std::ios::ate: Open and move the file pointer to the end of the file.
• std::ios::trunc: Truncate the file (erase existing content).
• std::ios::binary: Open the file in binary mode.

4.2 Advanced File I/O Techniques in C++

There are faster ways to open and process files in C++, which can be especially useful in competitive programming when dealing with large data sets. Here are some techniques that can improve the efficiency of file handling:

1. Disable I/O Synchronization

   As mentioned previously, disabling the synchronization between the C and C++ I/O libraries using std::ios::sync_with_stdio(false) and unlinking std::cin from std::cout with std::cin.tie(nullptr) can significantly speed up data reading.

2. Use Manual Buffering

   Manual buffering allows you to read the file in large chunks, which reduces the overhead of multiple I/O operations. Below is the code, followed by a detailed explanation of how we efficiently read the entire file into a buffer:

   #include <fstream>
   #include <iostream>
   #include <vector>
   
   int main(int argc, char* argv[]) {
       if (argc != 2) {
           std::cerr << "Usage: " << argv[0] << " <file_name>\n";
           return 1;
       }
   
       std::ifstream file(argv[1], std::ios::in | std::ios::binary);
       if (!file) {
           std::cerr << "Error opening file: " << argv[1] << "\n";
           return 1;
       }
   
       // Move file pointer to the end to determine file size
       file.seekg(0, std::ios::end);
       size_t fileSize = file.tellg();
       file.seekg(0, std::ios::beg);
   
       // Create buffer and read file in one go
       std::vector<char> buffer(fileSize);
       file.read(buffer.data(), fileSize);
   
       // Process buffer contents
       // Example: Print the first 100 characters of the file
       for (int i = 0; i < 100 && i < fileSize; ++i) {
           std::cout << buffer[i];
       }
   
       return 0;
   }
   

   Let’s break down the most important lines used to read the file efficiently:

   file.seekg(0, std::ios::end);
   

   This line moves the file pointer to the end of the file. The seekg function (seek “get” position) is used to set the position of the next read operation. Here, the first argument 0 means no offset, and the second argument std::ios::end moves the pointer to the end of the file. This allows us to calculate the size of the file, which is essential for creating a buffer that will hold the entire file’s content.

   size_t fileSize = file.tellg();
   

   After moving the pointer to the end of the file, we use tellg() (tell “get” position) to retrieve the current position of the pointer, which is now at the end. Since the file pointer is at the end, the value returned by tellg() represents the total size of the file in bytes. This value is stored in the variable fileSize, which we will use to allocate a buffer large enough to hold the file’s contents.

   file.seekg(0, std::ios::beg);
   

   Now that we know the file’s size, we move the file pointer back to the beginning of the file using seekg(0, std::ios::beg). The argument std::ios::beg means we are setting the pointer to the start of the file, where the reading will begin. This ensures we are ready to read the file from the first byte.

   std::vector<char> buffer(fileSize);
   

   We then create a std::vector<char> buffer with the size fileSize. This buffer will store the contents of the entire file in memory. Using a std::vector is convenient because it automatically manages memory and provides access to the underlying data using the data() method.

   file.read(buffer.data(), fileSize);
   

   Finally, we use file.read() to read the entire file into the buffer. The method buffer.data() provides a pointer to the beginning of the buffer where the file’s contents will be stored. The second argument, fileSize, specifies how many bytes to read from the file. Since fileSize equals the total size of the file, the entire file is read into the buffer in one go.

   By using seekg() to calculate the file size and then reading the file all at once into a buffer, we avoid multiple I/O operations, which would otherwise slow down the process. Reading the file in one operation reduces system calls and minimizes overhead, making the process faster, especially when dealing with large files.

3. Reading Lines More Efficiently

   Instead of using std::getline(), which can be relatively slow for large files, you can implement a custom buffer to store multiple lines at once, reducing the overhead of repeatedly calling the I/O functions.

4.2.1 Using mmap for Faster File I/O in Unix-Based Systems

In competitive programming, especially in contests like ICPC where the environment is Unix-based (typically Linux), it is crucial to explore every possible optimization for handling large input files. One such technique is using the mmap system call, which provides an extremely fast option for reading large files by mapping them directly into memory. This allows almost instantaneous access to the file’s content without multiple read operations, significantly reducing I/O overhead.

The mmap function maps a file or device into memory. Once the file is mapped, it behaves as if it’s part of the program’s memory space, allowing you to access file contents through pointer arithmetic rather than explicit file read operations. This eliminates the need for repeated system calls for reading file data, as you access the file as if it were a simple array in memory.

This approach is useful in environments like ICPC, where files can be very large, and efficiency is paramount. However, it’s important to note that mmap is specific to Unix-based systems and is not portable across all operating systems, such as Windows.

4.2.1.1 How to Use mmap

Here’s an example of how you can use mmap to read a file efficiently in C++ on a Unix-based system:

#include <sys/mman.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/stat.h>
#include <iostream>

int main(int argc, char* argv[]) {
    if (argc != 2) {
        std::cerr << "Usage: " << argv[0] << " <file_name>\n";
        return 1;
    }

    // Open the file
    int fd = open(argv[1], O_RDONLY);
    if (fd == -1) {
        std::cerr << "Error opening file: " << argv[1] << "\n";
        return 1;
    }

    // Get the size of the file
    struct stat sb;
    if (fstat(fd, &sb) == -1) {
        std::cerr << "Error getting file size\n";
        close(fd);
        return 1;
    }
    size_t fileSize = sb.st_size;

    // Memory-map the file
    char* fileData = (char*)mmap(nullptr, fileSize, PROT_READ, MAP_PRIVATE, fd, 0);
    if (fileData == MAP_FAILED) {
        std::cerr << "Error mapping file to memory\n";
        close(fd);
        return 1;
    }

    // Process the file data (example: print the first 100 characters)
    for (size_t i = 0; i < 100 && i < fileSize; ++i) {
        std::cout << fileData[i];
    }

    // Unmap the file and close the file descriptor
    if (munmap(fileData, fileSize) == -1) {
        std::cerr << "Error unmapping file\n";
    }
    close(fd);

    return 0;
}

Explanation of Key Steps:

1. Opening the File:

   int fd = open(argv[1], O_RDONLY);
   

   The open() function opens the file specified in the command-line arguments in read-only mode. The file descriptor fd is returned, which is later used to map the file into memory.

2. Getting the File Size:

   struct stat sb;
   fstat(fd, &sb);
   

   The fstat() function retrieves the size of the file and stores it in the stat structure. The file size is crucial for knowing how much memory to map.

3. Mapping the File into Memory:

   char* fileData = (char*)mmap(nullptr, fileSize, PROT_READ, MAP_PRIVATE, fd, 0);
   

   The mmap() function maps the entire file into memory. The PROT_READ flag allows read-only access, and MAP_PRIVATE ensures that any modifications to the memory are private to this process (although we won’t modify the file in this example). Once the file is mapped, fileData points to the beginning of the file’s contents in memory.

4. Processing the Data: After mapping the file, you can access the file’s content using fileData as if it were an array. For example, the above code prints the first 100 characters from the file.

5. Unmapping and Closing:

   munmap(fileData, fileSize);
   close(fd);
   

   After processing the file, it is important to unmap the memory with munmap() and close the file descriptor with close(). This ensures that system resources are properly freed.

mmap provides several advantages when it comes to handling large file I/O. First, it offers speed by allowing direct access to file contents in memory, eliminating the need for repeated system calls, which significantly reduces overhead. Additionally, simplicity is a key benefit, as the file can be accessed like a normal array after mapping, streamlining file processing logic. Finally, memory efficiency is improved, as mmap only loads the required parts of the file into memory, avoiding the need to load the entire file into a buffer, which is especially useful for large files.

portability: it’s important to note that the mmap function is specific to POSIX-compliant operating systems such as Linux, macOS, and other Unix-like systems. This function is not natively available on Windows platforms, which may limit the portability of code that uses it. For cross-platform development or in environments that include Windows systems, it’s advisable to provide an alternative implementation or use libraries that offer similar functionality in a portable manner. In programming competitive programmings that occur in controlled environments, such as ICPC, where the operating system is usually specified (often Linux), the use of mmap may be appropriate. However, for code that needs to run on multiple platforms, consider using more universal I/O methods, such as std::ifstream or fread, which are supported on a wider range of operating systems.

4.2.2 Parallel Input/Output with Threads (C++20)

C++20 introduced several improvements for parallel programming, including the efficient use of threads and asynchronous tasks with std::async. In many competitive programming scenarios, input and output (I/O) operations are performed sequentially. However, despite it being quite rare for input files to be very large in competitive programmings, in cases of intensive I/O or when there is a need to process large volumes of data simultaneously, parallel I/O can be an advantageous strategy.

In situations with heavy I/O workloads, such as reading and processing large input files or performing intensive calculations while still reading or writing data, std::async and threads can be used to split operations and execute different tasks simultaneously, making the best use of available time.

Example of Parallel I/O Using std::async

Below is a simple example of how to use std::async to perform input and output operations in parallel. In this example, while data is being read, another thread can be used to process or display the data simultaneously, optimizing the time spent on I/O operations:

#include <iostream>
#include <future>
#include <vector>

// Function to read input from the user
void read_input(std::vector<int>& vec, int n) {
for (int i = 0; i < n; ++i) {
std::cin >> vec[i];
}
}

// Function to process and print the output
void process_output(const std::vector<int>& vec) {
for (int i : vec) {
std::cout << i << " ";
}
std::cout << std::endl;
}

int main() {
int n;
std::cin >> n;

    // Create a vector of size 'n'
    std::vector<int> numbers(n);

    // Use std::async to read the input asynchronously
    auto readTask = std::async(std::launch::async, read_input, std::ref(numbers), n);

    // Wait for the input reading to complete before proceeding
    readTask.wait();

    // Process and print the vector after reading
    process_output(numbers);

    return 0;
}

In this example, the std::async function is used to run the read_input function asynchronously on a separate thread. This means that the data can be read in the background while other operations are prepared or started.

std::async executes the read_input function in a new thread, passing the numbers vector and the number of inputs n as parameters. The std::launch::async option ensures that the function is run in parallel, and not lazily (i.e., when the result is needed). The call to readTask.wait() ensures that the asynchronous read operation is completed before the program continues. This synchronizes the operation, ensuring that the input is fully read before trying to process the data.

Although this example uses the main thread to process the output after reading, in more complex scenarios, both processing and reading could be parallelized, or even multiple reads could occur simultaneously, depending on the needs:

#include <iostream>
#include <future>
#include <vector>

// Function to read input from the user
void read_input(std::vector<int>& vec, int n) {
    for (int i = 0; i < n; ++i) {
        std::cin >> vec[i];
    }
}

// Function to process and sum the input
void process_output(const std::vector<int>& vec) {
    int sum = 0;
    for (int i : vec) {
        sum += i;
    }
    std::cout << "Sum of elements: " << sum << std::endl;
}

int main() {
    int n;
    std::cin >> n;

    // Vectors to store the input data
    std::vector<int> numbers1(n);
    std::vector<int> numbers2(n);

    // Asynchronous read of the first data set
    auto readTask1 = std::async(std::launch::async, read_input, std::ref(numbers1), n);

    // Asynchronous read of the second data set in parallel
    auto readTask2 = std::async(std::launch::async, read_input, std::ref(numbers2), n);

    // Asynchronous processing of the first data set in parallel
    auto processTask = std::async(std::launch::async, [&]() {
        readTask1.wait(); // Wait for the first read to complete before processing
        process_output(numbers1); // Process the first data set
    });

    // Wait for both reads to finish
    readTask1.wait();
    readTask2.wait();

    // Output the second set of numbers
    std::cout << "Second set of numbers: ";
    for (int i : numbers2) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    // Wait for the asynchronous processing to finish
    processTask.wait();

    return 0;
}

Using threads for parallel I/O can improve performance in scenarios where there is a large volume of data to be read or written, especially if the reading time can be masked while another thread is processing data or preparing the next phase of the program.

However, this technique should be used with care. Adding threads and asynchronous operations increases code complexity, requiring careful synchronization to avoid race conditions or data inconsistencies. That’s why we should avoid this technique in competitive programming. While parallelism can improve execution time, creating and managing threads also has a computational cost. In some cases, the gain may not justify the added complexity. In many competitive programming environments, I/O is simple and sequential, meaning that this technique may not always be necessary or beneficial. It should be used in scenarios with extremely heavy I/O workloads or when processing and reading/writing can be separated.

The use of parallel I/O in programming competitive programmings typically applies to scenarios where there are many read/write operations or when the program needs to process large volumes of data while still reading or writing files. This situation is usual in AI competitive programmings and in hackatons. This technique can be useful in problems involving the manipulation of large datasets or intensive input/output processing, such as in “big data” challenges or reading/writing from disks. However, due to its complexity, the use of std::async and threads should be reserved for cases where parallelism offers a significant advantage over traditional sequential I/O.

4.3 Efficient Techniques for File I/O and Array Handling in Competitive Programming

5. Maximizing Input/Output Efficiency in Competitive Programming (Windows and Linux)

In some competitive programming environments, inputs are provided via the command line. The first input is the size of the array, followed by the array elements separated by spaces. Efficiently reading this data and outputting the result is crucial, especially when dealing with large datasets. Below is an approach to handle input and output in the fastest way for both Windows and Linux.

5.1 Optimized Input and Output

The following example demonstrates how to read inputs and output results efficiently in C++ using the fastest I/O methods available on both Windows and Linux.

#include <iostream>
#include <vector>
#include <cstdio>

int main() {
    // Disable synchronization for faster I/O
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    // Read the size of the array
    int n;
    std::cin >> n;

    // Create a vector to store the array elements
    std::vector<int> arr(n);

    // Read the elements of the array
    for (int i = 0; i < n; ++i) {
        std::cin >> arr[i];
    }

    // Output the array elements
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }

    std::cout << std::endl;
    return 0;
}

5.2 Key Techniques for Faster I/O

1. Disabling I/O Synchronization: The line std::ios::sync_with_stdio(false); disables the synchronization between the C and C++ I/O streams. This allows the program to perform I/O operations faster because it no longer needs to synchronize std::cin and std::cout with scanf and printf.

2. Unlinking cin and cout: The line std::cin.tie(nullptr); ensures that std::cout will not be flushed automatically before every std::cin operation, which can slow down the program. By unlinking them, you have more control over when output is flushed.

5.3 Differences Between Windows and Linux

On both Windows and Linux, the above code will work efficiently. However, since competitive programming platforms often use Linux, the synchronization of I/O streams plays a more significant role in Linux environments. Disabling synchronization is more crucial on Linux for achieving maximum performance, while the effect may be less noticeable on Windows. Nevertheless, the method remains valid and provides optimal speed in both environments.

Input: and Output Through Standard Methods

While std::cin and std::cout are often fast enough after synchronization is disabled, some competitive programmings on Unix-based systems like ICPC allow even faster input methods using scanf and printf. Below is an alternative version that uses scanf and printf for faster input/output handling:

#include <cstdio>
#include <vector>

int main() {
    // Read the size of the array
    int n;
    scanf("%d", &n);

    // Create a vector to store the array elements
    std::vector<int> arr(n);

    // Read the elements of the array
    for (int i = 0; i < n; ++i) {
        scanf("%d", &arr[i]);
    }

    // Output the array elements
    for (int i = 0; i < n; ++i) {
        printf("%d ", arr[i]);
    }

    printf("\n");
    return 0;
}

It is important to highlight that scanf and printf are widely recognized as insecure functions due to their lack of built-in protections against common vulnerabilities such as buffer overflows. We are discussing them here only because the code created for competitive programming is typically used only once during a contest, and the primary focus is on speed and efficiency. However, these functions — and any others considered unsafe (see stackoverflow)— should never be used in production code, libraries, or any other software outside the competitive programming environment. In professional development, you should always prefer safer alternatives such as std::cin and std::cout, which provide better type safety and avoid common vulnerabilities associated with older C-style I/O functions.

5.4 Using Manual Buffers with fread and fwrite

While functions like scanf and printf are fast, using fread and fwrite allows reading and writing data in large blocks, reducing the number of system calls for I/O. This is particularly useful when dealing with large volumes of data, as the overhead of multiple read and write operations can be significant.

The fread function is used to read a specified number of bytes from a file or stdin (standard input) and store that data in a buffer you define. By performing a single read of a large block of data, you minimize system calls, which reduces overhead and increases efficiency.

Example of reading with fread:

#include <cstdio>
#include <vector>

int main() {
    char buffer[1024];  // 1 KB manual buffer
    size_t bytesRead = fread(buffer, 1, sizeof(buffer), stdin);

    // Process the read data
    for (size_t i = 0; i < bytesRead; ++i) {
        // Use putchar to print the data from the buffer
        putchar(buffer[i]);
    }

    return 0;
}

The fread function reads up to a specified number of items from a data stream and stores them in the provided buffer. In the example above, fread(buffer, 1, sizeof(buffer), stdin) reads up to 1024 bytes from the standard input (stdin) and stores this data in the buffer. The number of bytes read is returned as bytesRead.

The putchar function prints one character at a time to stdout (standard output). In the example, we use putchar(buffer[i]) to print each character stored in the buffer. This function is efficient for handling low-level data, especially in situations where you are processing individual characters.

Compared to scanf and printf, which are more convenient when specific formatting is needed, such as reading integers or strings, fread and fwrite are more efficient for large volumes of unformatted “raw” data, like binary files or large blocks of text.

If you need to write data equally efficiently, you can use fwrite to write data blocks to a file or to stdout.

Example of writing with fwrite:

#include <cstdio>
#include <vector>

int main() {
    const char* data = "Outputting large blocks of data quickly\n";
    size_t dataSize = strlen(data);

    // Write the data buffer to stdout
    fwrite(data, 1, dataSize, stdout);

    return 0;
}

The fwrite function works similarly to fread, but instead of reading data, it writes the content of a buffer to a file or to standard output. In the example above, fwrite(data, 1, dataSize, stdout) writes dataSize bytes from the data buffer to stdout.

Using manual buffers with fread and fwrite can significantly improve performance in competitions by reducing the number of system calls, which is particularly useful when dealing with large volumes of data. This technique offers greater control over the I/O process and allows for optimizations in high-performance scenarios. However, when advanced formatting is required, scanf and printf might still be more convenient and suitable.

6. Introduction to Namespaces

In C++, namespaces are used to organize code and prevent name conflicts, especially in large projects or when multiple libraries are being used that may have functions, classes, or variables with the same name. They provide a scope for identifiers, allowing developers to define functions, classes, and variables without worrying about name collisions.

A namespace is a declarative region that provides a scope to the identifiers (names of types, functions, variables, etc.) inside it. This allows different parts of a program or different libraries to have elements with the same name without causing ambiguity.

6.1 Basic Syntax of a Namespace

namespace MyNamespace {
    void myFunction() {
        // Implementation
    }

    class MyClass {
    public:
        void method();
    };
}

The MyNamespace namespace encapsulates myFunction and MyClass, preventing these names from conflicting with others of the same name in different namespaces.

6.2 Using Namespaces

To access elements inside a namespace, you can use the scope resolution operator ::.

The scope resolution operator (::) in C++ is used to define or access elements that are within a specific scope, such as namespaces or class members. It allows the programmer to disambiguate between variables, functions, or classes that might have the same name but are defined in different contexts. For example, if a function is defined in a specific namespace, the scope resolution operator is used to call that function from the correct namespace. Similarly, within a class, it can be used to define a function outside the class declaration or to refer to static members of the class.

In competitive programming, the scope resolution operator is often used to access elements from the std namespace, such as std::cout or std::vector. This ensures that the standard library components are used correctly without introducing ambiguity with any other variables or functions that might exist in the global scope or within other namespaces. Although not as common in short competitive programming code, the operator becomes critical in larger projects to maintain clear and distinct references to elements that may share names across different parts of the program.

6.2.1 Accessing Elements of a Namespace

int main() {
    // Calling the function inside MyNamespace
    MyNamespace::myFunction();

    // Creating an object of the class inside the namespace
    MyNamespace::MyClass obj;
    obj.method();

    return 0;
}

6.2.2 using namespace std;

The std namespace is the default namespace of the C++ Standard Library. It contains all the features of the standard library, such as std::vector, std::cout, std::string, and more.

The statement using namespace std; allows you to use all elements of the std namespace without needing to prefix them with std::. This can make the code more concise and readable, especially in small programs or educational examples. Additionally, it reduces typing, which is beneficial when time is limited and valuable, such as during competitive programmings.

Example Without using namespace std;:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    for (const int& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

Example With using namespace std;:

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> numbers = {1, 2, 3, 4, 5};
    for (const int& num : numbers) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

6.3 Disadvantages of Using using namespace std;

While using using namespace std; makes your code shorter and easier to read, it comes with some drawbacks. In larger projects or when working with multiple libraries, it increases the likelihood of name conflicts, where different namespaces contain elements with the same name. It can also lead to ambiguity, making it less clear where certain elements are coming from, which complicates code maintenance and comprehension. Because of these risks, using using namespace std; is generally discouraged in production code, especially in large projects or collaborative settings.

6.4 Alternatives to using namespace std;

To avoid the risks associated with using namespace std;, one option is to import specific elements from the std namespace. For example, instead of importing the entire namespace, you can import only the functions and types you need, such as std::cout and std::vector. This approach reduces the risk of name conflicts while still allowing for more concise code.

#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

int main() {
    vector<int> numbers = {1, 2, 3, 4, 5};
    for (const int& num : numbers) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

Another option is to keep using the std:: prefix throughout your code. Although it requires more typing, this approach makes it clear where each element comes from and completely avoids name conflicts.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    for (const int& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

To maintain clean, maintainable code, it’s recommended to avoid using namespace std; in header files, as this can force all files that include the header to import the std namespace, increasing the risk of conflicts. If you decide to use using, it is better to do so in a limited scope, such as inside a function, to minimize its impact. Adopting a consistent approach to namespaces throughout your project also improves readability and makes collaboration easier.

6.4.1 Advanced Example: Nested Namespace

Namespaces can also be nested to better organize the code.

namespace Company {
    namespace Project {
        class ProjectClass {
        public:
            void projectMethod();
        };
    }
}

int main() {
    Company::Project::ProjectClass obj;
    obj.projectMethod();
    return 0;
}

Nested namespaces allow for a more hierarchical organization of code, which is particularly useful in large projects with multiple modules. However, it can make accessing elements more complex, as the full namespace hierarchy must be used.

In competitive programming, it is generally unnecessary and inefficient to create or use custom namespaces beyond the standard std namespace. Since competitive programming code is typically small and written for single-use, the overhead of managing custom namespaces adds complexity without providing significant benefits. Additionally, custom namespaces are designed to prevent name conflicts in large projects with multiple libraries, but in competitive environments where the focus is on speed and simplicity, such conflicts are rare. Therefore, it is best to avoid using namespaces beyond std in competitive programming, and reserve namespace management for larger codebases with extensive dependencies and libraries.

7. Working with Vector and Matrix

Vectors are one of the most versatile data structures used in competitive programming due to their dynamic size and ease of use. They allow for efficient insertion, removal, resizing, and access operations, making them suitable for a wide range of applications. Not only can vectors handle single-dimensional data, but they can also represent more complex structures, such as matrices (2D vectors), which are often used to solve grid-based problems, dynamic table calculations, or simulations of multi-dimensional data.

Matrices, represented as vectors of vectors, are particularly useful in problems involving multi-dimensional data manipulation, such as game boards, adjacency matrices in graphs, and dynamic programming tables. Vectors and matrices enable frequent operations like row and column manipulation, matrix transposition, and access to specific submatrices, providing flexibility and control over data arrangement and processing.

7.1 Vectors

In C++, the vector class, part of the Standard Template Library (STL), is a dynamic array that provides a versatile and efficient way to manage collections of elements. Unlike traditional arrays, vectors can automatically resize themselves when elements are added or removed, making them particularly useful in competitive programming where the size of data structures may vary during execution.

Vectors offer several advantages: they provide random access to elements, support iteration with iterators, and allow dynamic resizing, which is crucial for managing datasets of unknown or varying lengths. They also support a range of built-in functions for modifying the collection, such as push_back, pop_back, insert, erase, and resize, allowing developers to manage data efficiently without needing to manually handle memory allocations.

The vector class is particularly useful in scenarios involving frequent insertions, deletions, or resizes, as well as when working with dynamic data structures like lists, queues, stacks, or even matrices (2D vectors). Its simplicity and flexibility make it an indispensable tool for implementing a wide range of algorithms quickly and effectively in C++.

7.1.1 Inserting Elements at a Specific Position

This code inserts a value into a vector at position 5, provided that the vector has at least 6 elements:

Standard Version:

if (vec.size() > 5) {
    vec.insert(vec.begin() + 5, 42);
}

• $ \text{vec.insert(vec.begin() + 5, 42);} $ inserts the value 42 at position 5 in the vector.

Optimized for Minimal Typing:

if (vec.size() > 5) vec.insert(vec.begin() + 5, 42);

By removing the block braces ${}$, the code remains concise but still clear in cases where simplicity is essential. Alternatively, you can use the #define trick:

#define VI std::vector<int>
VI vec;
if (vec.size() > 5) vec.insert(vec.begin() + 5, 42);

7.1.2 Removing the Last Element and a Specific Element

The following code removes the last element from the vector, followed by the removal of the element at position 3, assuming the vector has at least 4 elements:

Standard Version:

if (!vec.empty()) {
    vec.pop_back();
}

if (vec.size() > 3) {
    vec.erase(vec.begin() + 3);
}

• $ \text{vec.pop_back();} $ removes the last element from the vector.
• $ \text{vec.erase(vec.begin() + 3);} $ removes the element at position 3.

Optimized for Minimal Typing:

if (!vec.empty()) vec.pop_back();
if (vec.size() > 3) vec.erase(vec.begin() + 3);

Using predefined macros, we can also reduce typing for common operations:

#define ERASE_AT(vec, pos) vec.erase(vec.begin() + pos)
if (!vec.empty()) vec.pop_back();
if (vec.size() > 3) ERASE_AT(vec, 3);

7.1.3 Creating a New Vector with a Default Value

The following code creates a new vector with 5 elements, all initialized to the value 7:

Standard Version:

std::vector<int> vec2(5, 7);

• $ \text{std::vector vec2(5, 7);} $ creates a vector `vec2` with 5 elements, each initialized to 7.

Optimized for Minimal Typing:

No significant reduction can be achieved here without compromising clarity, but using #define can help in repetitive situations:

#define VI std::vector<int>
VI vec2(5, 7);

7.1.4 Resizing and Filling with Random Values

The vector vec2 is resized to 10 elements, and each element is filled with a random value between 1 and 100:

Standard Version:

vec2.resize(10);

unsigned seed = static_cast<unsigned>(std::chrono::high_resolution_clock::now().time_since_epoch().count());
std::mt19937 generator(seed);
std::uniform_int_distribution<int> distribution(1, 100);

for (size_t i = 0; i < vec2.size(); ++i) {
    vec2[i] = distribution(generator);
}

• $ \text{vec2.resize(10);} $ resizes the vector to contain 10 elements.
• The generator $ \text{std::mt19937} $ is seeded based on the current time, and the distribution generates random integers between 1 and 100.

Optimized for Minimal Typing:

vec2.resize(10);
std::mt19937 gen(std::random_device{}());
std::uniform_int_distribution<int> dist(1, 100);
for (auto& v : vec2) v = dist(gen);

By using modern C++ constructs such as ranged-based for loops, we reduce the complexity of the loop and the generator initialization, making the code cleaner and more efficient to type.

7.1.5 Sorting the Vector

The following code sorts the vector vec2 in ascending order:

Standard Version:

std::sort(vec2.begin(), vec2.end());

• $ \text{std::sort(vec2.begin(), vec2.end());} $ sorts the vector in ascending order.

*### Optimized for Minimal Typing with constexpr

We can replace the #define with a constexpr function, which provides type safety and integrates better with the C++ type system.

Using constexpr for Sorting a Vector:

constexpr void sort_vector(std::vector<int>& vec) {
    std::sort(vec.begin(), vec.end());
}

sort_vector(vec2);

• $ \text{constexpr void sort_vector(std::vector<int}\& vec)$ is a type-safe way to define a reusable sorting function.
• This method avoids the pitfalls of #define, such as lack of scoping and type checking, while still minimizing the amount of typing.

7.1.6 Vectors as Inputs and Outputs

In competitive programming, a common input format involves receiving the size of a vector as the first integer, followed by the elements of the vector separated by spaces, with a newline at the end. Handling this efficiently is crucial when dealing with large inputs. Below is an optimized version using fread for input and putchar for output, ensuring minimal system calls and fast execution.

This version reads the input, processes it, and then outputs the vector’s elements using the fastest possible I/O methods in C++.

#include <cstdio>
#include <vector>

int main() {
    // Buffer for reading input
    char buffer[1 << 16]; // 64 KB buffer size
    int idx = 0;

    // Read the entire input at once
    size_t bytesRead = fread(buffer, 1, sizeof(buffer), stdin);

    // Parse the size of the vector from the input
    int n = 0;
    while (buffer[idx] >= '0' && buffer[idx] <= '9') {
        n = n * 10 + (buffer[idx++] - '0');
    }
    ++idx; // Skip the space or newline after the number

    // Create the vector and fill it with elements
    std::vector<int> vec(n);
    for (int i = 0; i < n; ++i) {
        int num = 0;
        while (buffer[idx] >= '0' && buffer[idx] <= '9') {
            num = num * 10 + (buffer[idx++] - '0');
        }
        vec[i] = num;
        ++idx; // Skip the space or newline after each number
    }

    // Output the vector elements using putchar
    for (int i = 0; i < n; ++i) {
        if (vec[i] == 0) putchar('0');
        else {
            int num = vec[i], digits[10], digitIdx = 0;
            while (num) {
                digits[digitIdx++] = num % 10;
                num /= 10;
            }
            // Print digits in reverse order
            while (digitIdx--) putchar('0' + digits[digitIdx]);
        }
        putchar(' '); // Space after each number
    }
    putchar('\n'); // End the output with a newline

    return 0;
}

In the previous code, we have the following functions:

1. Input with fread:
   • fread is used to read the entire input into a large buffer at once. This avoids multiple system calls, which are slower than reading in bulk.
2. Parsing the Input:
   • The input is parsed from the buffer using simple character arithmetic to convert the string of numbers into integers.
3. Output with putchar:
   • putchar is used to print the numbers, which is faster than std::cout for individual characters. The digits of each number are processed and printed in reverse order.

The previous code method minimizes system calls and avoids using slower I/O mechanisms like std::cin and std::cout, making it highly optimized for competitive programming scenarios where speed is crucial.

In competitive programming, it’s also common to handle input from a file provided via the command line. This scenario requires efficient reading and processing, especially when dealing with large datasets. Below is the optimized version using fread to read from a file specified in the command line argument and putchar for output.

7.1.6.1 Optimized Version Using fread and putchar with Command-Line File Input

This version reads the input file, processes it, and outputs the vector’s elements, ensuring fast I/O performance.

#include <cstdio>
#include <vector>

int main(int argc, char* argv[]) {
    // Check if the filename was provided
    if (argc != 2) {
        return 1;
    }

    // Open the file from the command line argument
    FILE* file = fopen(argv[1], "r");
    if (!file) {
        return 1;
    }

    // Buffer for reading input
    char buffer[1 << 16]; // 64 KB buffer size
    int idx = 0;

    // Read the entire input file at once
    size_t bytesRead = fread(buffer, 1, sizeof(buffer), file);
    fclose(file); // Close the file after reading

    // Parse the size of the vector from the input
    int n = 0;
    while (buffer[idx] >= '0' && buffer[idx] <= '9') {
        n = n * 10 + (buffer[idx++] - '0');
    }
    ++idx; // Skip the space or newline after the number

    // Create the vector and fill it with elements
    std::vector<int> vec(n);
    for (int i = 0; i < n; ++i) {
        int num = 0;
        while (buffer[idx] >= '0' && buffer[idx] <= '9') {
            num = num * 10 + (buffer[idx++] - '0');
        }
        vec[i] = num;
        ++idx; // Skip the space or newline after each number
    }

    // Output the vector elements using putchar
    for (int i = 0; i < n; ++i) {
        if (vec[i] == 0) putchar('0');
        else {
            int num = vec[i], digits[10], digitIdx = 0;
            while (num) {
                digits[digitIdx++] = num % 10;
                num /= 10;
            }
            // Print digits in reverse order
            while (digitIdx--) putchar('0' + digits[digitIdx]);
        }
        putchar(' '); // Space after each number
    }
    putchar('\n'); // End the output with a newline

    return 0;
}

In the previous code we have:

1. File Input with fread:

   • The input is read from a file specified in the command line argument using fread. This reads the entire file into a buffer in one go, improving efficiency by reducing system calls.

2. File Handling:

   • The file is opened using fopen and closed immediately after reading the data. This ensures that system resources are released as soon as the file reading is complete.

3. Parsing and Output:

   • The rest of the program processes the input similarly to the previous version, parsing the numbers from the buffer and outputting them efficiently using putchar.

This approach remains highly optimized for competitive programming environments where fast I/O handling is critical. But, in Linux we can use mmap

#include <sys/mman.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/stat.h>
#include <vector>
#include <iostream>

int main(int argc, char* argv[]) {
    if (argc != 2) {
        return 1;
    }

    // Open the file
    int fd = open(argv[1], O_RDONLY);
    if (fd == -1) {
        return 1;
    }

    // Get the file size
    struct stat sb;
    if (fstat(fd, &sb) == -1) {
        close(fd);
        return 1;
    }
    size_t fileSize = sb.st_size;

    // Memory-map the file
    char* fileData = static_cast<char*>(mmap(nullptr, fileSize, PROT_READ, MAP_PRIVATE, fd, 0));
    if (fileData == MAP_FAILED) {
        close(fd);
        return 1;
    }

    close(fd); // The file descriptor can be closed after mapping

    // Parse the vector size
    int idx = 0;
    int n = 0;
    while (fileData[idx] >= '0' && fileData[idx] <= '9') {
        n = n * 10 + (fileData[idx++] - '0');
    }
    ++idx; // Skip the space or newline

    // Create the vector and fill it with values from the memory-mapped file
    std::vector<int> vec(n);
    for (int i = 0; i < n; ++i) {
        int num = 0;
        while (fileData[idx] >= '0' && fileData[idx] <= '9') {
            num = num * 10 + (fileData[idx++] - '0');
        }
        vec[i] = num;
        ++idx; // Skip the space or newline
    }

    // Output the vector
    for (const int& num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Unmap the file from memory
    munmap(fileData, fileSize);

    return 0;
}

7.2 Matrices

In C++20, matrices are typically represented as vectors of vectors (std::vector<std::vector<T>>), where each inner vector represents a row of the matrix. This approach allows for dynamic sizing and easy manipulation of multi-dimensional data, making matrices ideal for problems involving grids, tables, or any 2D structure.

Matrices in C++ offer flexibility in managing data: you can resize rows and columns independently, access elements using intuitive indexing, and leverage standard vector operations for rows. Additionally, the use of ranges and views introduced in C++20 boosts the ability to iterate and transform matrix data more expressively and efficiently.

The use of matrices is common in competitive programming for tasks such as implementing dynamic programming tables, graph adjacency matrices, or performing transformations on 2D data. With the powerful capabilities of C++20’s STL, matrices become a highly adaptable and efficient way to handle complex, multi-dimensional computations in a structured manner.

7.2.1 Creating and Filling a Matrix

The code creates a 2x2 matrix (a vector of vectors) and fills each element with the value 1:

Standard Version:

int rows = 2, cols = 2;
std::vector<std::vector<int>> matrix(rows, std::vector<int>(cols));

for (int i = 0; i < rows; ++i) {
    for (int j = 0; j < cols; ++j) {
        matrix[i][j] = 1;
    }
}

• $ \text{std::vector<std::vector> matrix(rows, std::vector(cols));} $ creates a matrix of size $2\times 2$.
• The nested for loop fills each element of the matrix with $1$.

Optimized for Minimal Typing:

std::vector<std::vector<int>> matrix(2, std::vector<int>(2, 1));

This version eliminates the need for the explicit loop by using the constructor to initialize the matrix with 1s directly.

7.2.2 Displaying the Matrix

Finally, the matrix is printed in the standard format:

Standard Version:

for (const auto& row : matrix) {
    for (const auto& element : row) {
        std::cout << element << " ";
    }
    std::cout << std::endl;
}

• The loop iterates over each row and prints all elements in the row, followed by a newline.

Optimized for Minimal Typing:

for (const auto& row : matrix) {
    for (int el : row) std::cout << el << " ";
    std::cout << "\n";
}

Here, we replaced std::endl with "\n" to improve performance by avoiding the unnecessary flushing of the output buffer.

7.2.3 Inserting Elements at a Specific Position

To insert an element at a specific position in a matrix (vector of vectors) in C++ 20, we use the insert function. This function can insert rows or columns in a specific location, modifying the structure of the matrix.

#include <iostream>
#include <vector>

int main() {
    std::vector<std::vector<int>> matrix = { {1, 2}, {3, 4} };

    // Insert a row at position 1
    matrix.insert(matrix.begin() + 1, std::vector<int>{5, 6});

    // Insert a column value at position 0 in the first row
    matrix[0].insert(matrix[0].begin(), 0);

    // Display the modified matrix
    for (const auto& row : matrix) {
        for (int el : row) std::cout << el << " ";
        std::cout << "\n";
    }

    return 0;
}

This code inserts a new row at position 1 and a new column value at position 0 in the first row. The result is a modified matrix.

7.2.4 Removing the Last Element and a Specific Element

To remove the last element of a matrix or a specific element, you can use the pop_back function for removing the last row and the erase function for removing specific rows or columns.

#include <iostream>
#include <vector>

int main() {
    std::vector<std::vector<int>> matrix = { {1, 2}, {3, 4}, {5, 6} };

    // Remove the last row
    matrix.pop_back();

    // Remove the first element of the first row
    matrix[0].erase(matrix[0].begin());

    // Display the modified matrix
    for (const auto& row : matrix) {
        for (int el : row) std::cout << el << " ";
        std::cout << "\n";
    }

    return 0;
}

This code removes the last row from the matrix and removes the first element of the first row.

7.2.5 Creating a New Vector with a Default Value

To create a new matrix filled with a default value, you can specify this value in the constructor of the vector.

#include <iostream>
#include <vector>

int main() {
    // Create a 3x3 matrix filled with the default value 7
    std::vector<std::vector<int>> matrix(3, std::vector<int>(3, 7));

    // Display the matrix
    for (const auto& row : matrix) {
        for (int el : row) std::cout << el << " ";
        std::cout << "\n";
    }

    return 0;
}

This code initializes a 3x3 matrix with all elements set to 7.

7.2.6 Resizing and Filling with Random Values

To resize a matrix and fill it with random values, you can use the resize function along with the <random> library.

#include <iostream>
#include <vector>
#include <random>

int main() {
    std::vector<std::vector<int>> matrix;
    int rows = 3, cols = 3;

    // Resize the matrix
    matrix.resize(rows, std::vector<int>(cols));

    // Fill the matrix with random values
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(1, 10);

    for (auto& row : matrix) {
        for (auto& el : row) {
            el = dis(gen);
        }
    }

    // Display the matrix
    for (const auto& row : matrix) {
        for (int el : row) std::cout << el << " ";
        std::cout << "\n";
    }

    return 0;
}

This code resizes the matrix to 3x3 and fills it with random values between 1 and 10.

7.2.7 Sorting Matrices by Rows and Columns

In C++20, we can sort matrices (represented as vectors of vectors) both by rows and by columns. Here are examples of how to do both:

7.2.7.1 Sorting by Rows

Sorting by rows is straightforward, as we can use the std::sort function directly on each row of the matrix.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
   std::vector<std::vector<int>> matrix = {
        {3, 1, 4}, {1, 5, 9}, {2, 6, 5}
    };

   // Sort each row of the matrix
   for (auto& row : matrix) {
       std::sort(row.begin(), row.end());
   }

   // Display the sorted matrix
   for (const auto& row : matrix) {
       for (int el : row) std::cout << el << " ";
       std::cout << "\n";
   }

   return 0;
}

This code sorts each row of the matrix independently. The time complexity for sorting by rows is $O(m \cdot n \log n)$, where $m$ is the number of rows and $n$ is the number of columns.

7.2.7.2 Sorting by Columns

Sorting by columns is more complex because the elements in a column are not contiguous in memory. We need to extract each column, sort it, and then put the sorted elements back into the matrix.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
   std::vector<std::vector<int>> matrix = { {3, 1, 4}, {1, 5, 9}, {2, 6, 5} };
   int rows = matrix.size();
   int cols = matrix[0].size();

   // Sort each column of the matrix
   for (int j = 0; j < cols; ++j) {
       std::vector<int> column;
       for (int i = 0; i < rows; ++i) {
           column.push_back(matrix[i][j]);
       }
       std::sort(column.begin(), column.end());
       for (int i = 0; i < rows; ++i) {
           matrix[i][j] = column[i];
       }
   }

   // Display the sorted matrix
   for (const auto& row : matrix) {
       for (int el : row) std::cout << el << " ";
       std::cout << "\n";
   }

   return 0;
}

This code sorts each column of the matrix independently. The time complexity for sorting by columns is $O(n \cdot m \log m)$, where $n$ is the number of columns and $m$ is the number of rows.

Note that this method of sorting by columns is not the most efficient for very large matrices, as it involves many data copies. For large matrices, it might be more efficient to use an approach that sorts the row indices based on the values in a specific column.

7.2.8 Optimizing Matrix Input and Output in Competitive Programming

In competitive programming, efficiently handling matrices for input and output is crucial. Let’s explore optimized techniques in C++ that minimize system calls and maximize execution speed.

Typically, the input for a matrix consists of:

1. Two integers $n$ and $m$, representing the number of rows and columns, respectively.
2. $n \times m$ elements of the matrix, separated by spaces and newlines.

For example:

3 4
1 2 3 4
5 6 7 8
9 10 11 12

7.2.8.1 Optimized Reading with fread

To optimize reading, we can use fread to load the entire input at once into a buffer, then parse the numbers from the buffer. This approach reduces the number of system calls compared to reading the input one character or one line at a time.

#include <cstdio>
#include <vector>

int main() {
    char buffer[1 << 16];
    size_t bytesRead = fread(buffer, 1, sizeof(buffer), stdin);
    size_t idx = 0;

    auto readInt = [&](int& num) {
        while (idx < bytesRead && (buffer[idx] < '0' || buffer[idx] > '9') && buffer[idx] != '-') ++idx;
        bool neg = false;
        if (buffer[idx] == '-') {
            neg = true;
            ++idx;
        }
        num = 0;
        while (idx < bytesRead && buffer[idx] >= '0' && buffer[idx] <= '9') {
            num = num * 10 + (buffer[idx++] - '0');
        }
        if (neg) num = -num;
    };

    int n, m;
    readInt(n);
    readInt(m);

    std::vector<std::vector<int>> matrix(n, std::vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            readInt(matrix[i][j]);
        }
    }

    // Matrix processing...

    return 0;
}

In this code: We define a lambda function readInt to read integers from the buffer, handling possible whitespace and negative numbers. The readInt function skips over any non-digit characters and captures negative signs. This ensures robust parsing of the input data.

7.2.8.2 Optimized Output with putchar_unlocked

For output, using putchar_unlocked offers better performance than std::cout or even putchar, as it is not thread-safe and thus faster.

#include <cstdio>
#include <vector>

void writeInt(int num) {
    if (num == 0) {
        putchar_unlocked('0');
        return;
    }
    if (num < 0) {
        putchar_unlocked('-');
        num = -num;
    }
    char digits[10];
    int idx = 0;
    while (num) {
        digits[idx++] = '0' + num % 10;
        num /= 10;
    }
    while (idx--) {
        putchar_unlocked(digits[idx]);
    }
}

int main() {
    // Assume matrix is already populated
    int n = /* number of rows */;
    int m = /* number of columns */;
    std::vector<std::vector<int>> matrix = /* your matrix */;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            writeInt(matrix[i][j]);
            putchar_unlocked(j == m - 1 ? '\n' : ' ');
        }
    }

    return 0;
}

In this code: We define a function writeInt to output integers efficiently. It handles zero and negative numbers correctly, and we use putchar_unlocked for faster character output.

putchar_unlocked is a non-thread-safe version of putchar. It writes a character to stdout without locking the output stream, eliminating the overhead associated with ensuring thread safety. This makes putchar_unlocked faster than putchar, which locks the output stream to prevent concurrent access from multiple threads.

When comparing putchar and putchar_unlocked, we find that putchar is thread-safe and locks stdout to prevent data races, but incurs overhead due to locking. On the other hand, putchar_unlocked is not thread-safe and does not lock stdout, making it faster due to the absence of locking overhead.

Here’s an example of using putchar_unlocked to output an integer efficiently:

#include <cstdio>

void writeInt(int num) {
   if (num == 0) {
       putchar_unlocked('0');
       return;
   }
   if (num < 0) {
       putchar_unlocked('-');
       num = -num;
   }
   char digits[10];
   int idx = 0;
   while (num) {
       digits[idx++] = '0' + (num % 10);
       num /= 10;
   }
   while (idx--) {
       putchar_unlocked(digits[idx]);
   }
}

int main() {
   int number = 12345;
   writeInt(number);
   putchar_unlocked('\n');
   return 0;
}

In contrast, using putchar would involve replacing putchar_unlocked with putchar:

#include <cstdio>

void writeInt(int num) {
   if (num == 0) {
       putchar('0');
       return;
   }
   if (num < 0) {
       putchar('-');
       num = -num;
   }
   char digits[10];
   int idx = 0;
   while (num) {
       digits[idx++] = '0' + (num % 10);
       num /= 10;
   }
   while (idx--) {
       putchar(digits[idx]);
   }
}

int main() {
   int number = 12345;
   writeInt(number);
   putchar('\n');
   return 0;
}

putchar_unlocked is best used in single-threaded programs where maximum output performance is required. It’s particularly >useful in competitive programming scenarios where execution time is critical and the program is guaranteed to be >single-threaded.

However, caution must be exercised when using putchar_unlocked. It is not thread-safe, and in multi-threaded applications, >using it can lead to data races and undefined behavior. Additionally, it is a POSIX function and may not be available or >behave differently on non-POSIX systems.

Both putchar and putchar_unlocked are functions from the C standard library <cstdio>, which is included in C++ for >compatibility purposes. The prototype for putchar is int putchar(int character);, which writes the character to stdout >and returns the character written, or EOF on error. It is thread-safe due to internal locking mechanisms.

The prototype for putchar_unlocked is int putchar_unlocked(int character);. It’s a faster version of putchar without >internal locking, but it’s not thread-safe and may not be part of the C++ standard in all environments.

If both performance and thread safety are needed, consider using buffered output or high-performance C++ I/O techniques. For >example:

#include <iostream>
#include <vector>

int main() {
   std::ios::sync_with_stdio(false);
   std::cin.tie(nullptr);

   std::vector<int> numbers = {1, 2, 3, 4, 5};
   for (int num : numbers) {
       std::cout << num << ' ';
   }
   std::cout << '\n';

   return 0;
}

By untethering C++ streams from C streams using std::ios::sync_with_stdio(false); and untangling cin from cout with >std::cin.tie(nullptr);, you can achieve faster I/O while maintaining thread safety and standard compliance.

7.2.8.3 Complexity Analysis

The time complexity for reading and writing is $O(nm)$, where $n$ and $m$ are the dimensions of the matrix. The space complexity is also $O(nm)$, as we store the entire matrix in memory. However, the constant factors are significantly reduced compared to standard I/O methods, leading to faster execution times in practice.

7.2.8.4 Using mmap on Unix Systems

On Unix systems, we can use mmap to map a file (or standard input) directly into memory, potentially improving I/O performance even further.

#include <sys/mman.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/stat.h>
#include <vector>
#include <cstdio>

int main() {
    struct stat sb;
    fstat(0, &sb); // File descriptor 0 is stdin
    size_t fileSize = sb.st_size;
    char* data = static_cast<char*>(mmap(nullptr, fileSize, PROT_READ, MAP_PRIVATE, 0, 0));

    size_t idx = 0;

    auto readInt = [&](int& num) {
        while (idx < fileSize && (data[idx] < '0' || data[idx] > '9') && data[idx] != '-') ++idx;
        bool neg = false;
        if (data[idx] == '-') {
            neg = true;
            ++idx;
        }
        num = 0;
        while (idx < fileSize && data[idx] >= '0' && data[idx] <= '9') {
            num = num * 10 + (data[idx++] - '0');
        }
        if (neg) num = -num;
    };

    int n, m;
    readInt(n);
    readInt(m);

    std::vector<std::vector<int>> matrix(n, std::vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            readInt(matrix[i][j]);
        }
    }

    munmap(data, fileSize);

    // Matrix processing...

    return 0;
}

Note: Using mmap can be risky, as it relies on the entire input being available and may not be portable across different systems or handle input streams properly. Use it only when you are certain of the input’s nature and when maximum performance is essential.

Remember: The efficiency of these approaches comes at the cost of increased code complexity and reduced readability. In scenarios where performance is not critical, standard I/O methods are preferable for their simplicity and maintainability.

8. Efficient Data Manipulation in C++ using Span and Ranges

In the fast-paced world of competitive programming and high-performance computing, efficient data manipulation is paramount. C++20 introduces two powerful features - std::span and std::ranges for that.

These features are particularly important because they address common performance bottlenecks in data-intensive applications. std::span provides a lightweight, non-owning view into contiguous data, reducing unnecessary copying and allowing for flexible, efficient data access. std::ranges, on the other hand, offers a unified, composable interface for working with sequences of data, enabling more intuitive and often more performant algorithm implementations. Together, they form a potent toolkit for developers seeking to push the boundaries of what’s possible in terms of code efficiency and elegance in C++.

8.1 Using std::span

The std::span is a new feature introduced in C++20 that allows you to create lightweight, non-owning views of arrays and containers, such as std::vector. This avoids unnecessary copying of data and provides a flexible and efficient way to access and manipulate large blocks of data. std::span can be particularly useful when working with large datasets, file I/O, or when optimizing memory usage in competitive programming.

Unlike containers such as std::vector, std::span doesn’t own the data it references. This means it doesn’t allocate new memory and works directly with existing data, leading to lower memory overhead. Additionally, std::span can work with both static arrays and dynamic containers (like std::vector) without requiring copies. It provides safer array handling compared to raw pointers, as it encapsulates size information. Since std::span eliminates the need for memory copies, it can speed up operations where large datasets need to be processed in-place, or only certain views of data are required.

Example of std::span for Efficient Data Access:

In this example, we create a std::span from a std::vector of integers, allowing us to iterate over the vector’s elements without copying the data:

#include <iostream>
#include <span>
#include <vector>

int main() {
    // Create a vector of integers
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // Create a span view of the vector
    std::span<int> view(numbers);

    // Iterate over the span and print the values
    for (int num : view) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

How std::span Works:

$ \text{std::span view(numbers);} $ creates a non-owning view of the `std::vector` `numbers`. This allows access to the elements of the vector without copying them. The loop $ \text{for (int num : view)} $ iterates over the elements in the `std::span`, just like it would with the original `std::vector`, but with no additional overhead from copying the data.

8.1.1 Efficient Use Cases for std::span

std::span is especially useful when you want to work with sub-ranges of arrays or vectors. For example, when working with just part of a large dataset, you can use std::span to reference a subset without slicing or creating new containers:

std::span<int> subrange = view.subspan(1, 3); // Access elements 1, 2, and 3
for (int num : subrange) {
    std::cout << num << " "; // Outputs: 2 3 4
}

When passing data to functions, std::span provides an efficient alternative to passing large vectors or arrays by reference. You can pass a span instead, ensuring that no copies are made, while maintaining full access to the original data:

void process_data(std::span<int> data) {
    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> numbers = {10, 20, 30, 40, 50};
    process_data(numbers); // Pass the vector as a span
    return 0;
}

In this example, the function process_data accepts a std::span, avoiding unnecessary copies and keeping the original data structure intact.

8.1.2 Comparing std::span to Traditional Methods

Unlike std::vector, which manages its own memory, std::span does not allocate or own memory. This is similar to raw pointers but with added safety since std::span knows its size. std::span is safer than raw pointers because it carries bounds information, helping avoid out-of-bounds errors. While raw pointers offer flexibility, they lack the safety features provided by modern C++.

8.1.3 Practical Application: Using std::span in Competitive Programming

When working with large datasets in competitive programming, using std::span avoids unnecessary memory copies, making operations faster and more efficient. You can easily pass sub-ranges of data to functions without creating temporary vectors or arrays. Additionally, it allows you to maintain full control over memory without introducing complex ownership semantics, as with std::unique_ptr or std::shared_ptr.

Example: Efficiently Passing Data in a Competitive Programming Scenario:

#include <iostream>
#include <span>
#include <vector>

void solve(std::span<int> data) {
    for (int num : data) {
        std::cout << num * 2 << " "; // Example: print double each value
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> input = {100, 200, 300, 400, 500};

    // Use std::span to pass the entire vector without copying
    solve(input);

    // Use a subspan to pass only a portion of the vector
    solve(std::span<int>(input).subspan(1, 3)); // Pass elements 200, 300, 400

    return 0;
}

8.2 Efficient Data Manipulation with std::ranges in C++20

C++20 introduced the <ranges> library, which brings a powerful and flexible way to work with sequences of data through lazy-evaluated views and composable transformations. std::ranges allows you to create views over containers or arrays without modifying them or creating unnecessary copies. This is especially beneficial in competitive programming and high-performance applications, where minimizing both memory and computational overhead is crucial.

In traditional programming with containers like std::vector, iterating over and transforming data often requires intermediate storage or manual loops to handle operations like filtering, transforming, or slicing the data. With std::ranges, these operations can be composed in a clean and expressive way while maintaining optimal performance through lazy evaluation. Lazy evaluation means that the transformations are only computed when the data is accessed, rather than immediately creating new containers or applying operations.

8.2.1 How std::ranges Works

The core idea behind std::ranges is to create “views” over data. These views allow you to manipulate and query data without modifying the underlying container. A view in std::ranges is an abstraction that can represent any sequence of elements that can be iterated over, just like a container. The key difference is that a view is not required to own its elements; instead, it provides a “window” into an existing data sequence, allowing for efficient operations.

Example Filtering and Transforming Data with std::ranges:

Suppose we have a vector of integers and we want to filter out the odd numbers and then multiply the remaining even numbers by two. Using traditional methods, we would need to loop through the vector, apply conditions, and store the results in a new container. With std::ranges, this can be done in a more expressive and efficient way:

#include <iostream>
#include <vector>
#include <ranges>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // Create a lazy-evaluated view that filters out odd numbers and doubles the even ones
    auto even_doubled = numbers
                        | std::ranges::views::filter([](int n) { return n % 2 == 0; })
                        | std::ranges::views::transform([](int n) { return n * 2; });

    // Iterate over the view and print the results
    for (int num : even_doubled) {
        std::cout << num << " ";  // **Output**: 4 8 (only even numbers doubled)
    }
    std::cout << std::endl;

    return 0;
}

In this example, we create a view even_doubled over the original vector numbers. The first operation, std::ranges::views::filter, filters out all the odd numbers from the vector. The second operation, std::ranges::views::transform, multiplies each of the remaining even numbers by two. Both of these operations are lazily evaluated, meaning that no new container is created, and the transformations are applied only when iterating over the view. This approach is not only cleaner in terms of code but also more efficient in terms of performance.

8.2.2 Composition of Operations

One of the key strengths of std::ranges is its composability. Operations like filtering, transforming, or slicing can be composed together, and the result is still a view. This means that you can chain multiple operations together without needing intermediate containers or data structures. The result is a highly efficient pipeline of operations that is applied only when the data is accessed.

Consider the following example, where we filter, transform, and take only a part of the data:

#include <iostream>
#include <vector>
#include <ranges>

int main() {
    std::vector<int> numbers = {10, 15, 20, 25, 30, 35, 40};

    // Filter out numbers less than 20, double the remaining, and take only the first three
    auto result = numbers
                  | std::ranges::views::filter([](int n) { return n >= 20; })
                  | std::ranges::views::transform([](int n) { return n * 2; })
                  | std::ranges::views::take(3);

    // Iterate over the view and print the results
    for (int num : result) {
        std::cout << num << " ";  // **Output**: 40 50 60
    }
    std::cout << std::endl;

    return 0;
}

In this example, we chain together three operations: filtering the numbers greater than or equal to 20, doubling them, and taking only the first three results. The operations are applied lazily and are only computed when iterating over the final view, result. This leads to highly efficient data processing, as no intermediate containers are created, and each transformation is performed only once for the relevant elements.

8.2.3 Memory and Performance Considerations

The key advantage of std::ranges is its use of lazy evaluation, which minimizes memory usage by avoiding the creation of temporary containers. In traditional methods, each operation (e.g., filtering or transforming) might create a new container, leading to increased memory consumption and computational overhead. With std::ranges, the operations are “stacked” and evaluated only when needed. This reduces the memory footprint and ensures that performance remains high, even when dealing with large datasets.

Another performance benefit comes from the fact that std::ranges operations are highly optimized. Since the operations are evaluated lazily and directly on the data, there’s no need for unnecessary copying or allocation. This leads to more efficient cache usage and fewer CPU cycles spent on managing intermediate data structures.

8.2.3 Practical Use Cases in Competitive Programming

Imagine a scenario where you need to process only a portion of the input data based on certain conditions. Using traditional methods, this might involve creating multiple containers or applying multiple iterations over the data. With std::ranges, you can chain these operations in a single pass, improving both performance and code readability.

Consider the following example in a competitive programming context:

#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>

int main() {
    std::vector<int> data = {50, 40, 30, 20, 10, 5};

    // Sort the data, filter values greater than 15, and transform them by subtracting 5
    auto processed = data
                     | std::ranges::views::sort
                     | std::ranges::views::filter([](int n) { return n > 15; })
                     | std::ranges::views::transform([](int n) { return n - 5; });

    // Iterate and output the results
    for (int num : processed) {
        std::cout << num << " ";  // **Output**: 15 25 35 45
    }
    std::cout << std::endl;

    return 0;
}

Here, the data is sorted, filtered, and transformed in a single efficient chain of operations. Each step is evaluated lazily, meaning that no intermediate containers or data copies are made, and each number is processed only once.

std::ranges in C++20 brings a powerful new way to work with data by providing efficient, lazy-evaluated views over containers. This minimizes memory usage, avoids unnecessary copying, and allows for highly optimized data processing pipelines. In competitive programming and high-performance applications, where every CPU cycle and byte of memory counts, using std::ranges can significantly improve both performance and code clarity. Whether you’re filtering, transforming, or composing operations, std::ranges allows you to build complex data processing pipelines that are both expressive and efficient.

9. Time and Space Complexity in Competitive Programming

In this section, we will delve deeper into understanding both time and space complexities, providing a more comprehensive look into how these affect the efficiency of algorithms, particularly in competitive programming environments. This includes examining loops, recursive algorithms, and how various complexity classes dictate algorithm performance. We’ll also consider the impact of space complexity and memory usage, which is crucial when dealing with large datasets.

9.1 Loops, Time and Space Complexity

One of the most common reasons for slow algorithms is the presence of multiple loops iterating over input data. The more nested loops an algorithm contains, the slower it becomes. If there are $k$ nested loops, the time complexity becomes $O(n^k)$.

For instance, the time complexity of the following code is $O(n)$:

for (int i = 1; i <= n; i++) {
    // code
}

And the time complexity of the following code is $O(n^2)$ due to the nested loops:

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        // code
    }
}

While the focus is often on time complexity, it’s equally important to consider space complexity, especially when handling large inputs. A loop like the one below has a time complexity of $O(n)$ but also incurs a space complexity of $O(n)$ if an array is created to store values:

std::vector<int> arr(n);
for (int i = 1; i <= n; i++) {
    arr.push_back(i);
}

In competitive programming, excessive memory use can cause the program to exceed memory limits. Therefore, always account for the space complexity of your solution, particularly when using arrays, matrices, or data structures that grow with input size.

9.2 Order of Growth

Time complexity doesn’t tell us the exact number of times the code within a loop executes but rather gives the order of growth. In the following examples, the code inside the loop executes $3n$, $n+5$, and $\lfloor n/2 \rfloor$ times, but the time complexity of each code is still $O(n)$:

for (int i = 1; i <= 3*n; i++) {
    // code
}

for (int i = 1; i <= n+5; i++) {
    // code
}

for (int i = 1; i <= n; i += 2) {
    // code
}

Another example where time complexity is $O(n^2)$:

for (int i = 1; i <= n; i++) {
    for (int j = i+1; j <= n; j++) {
        // code
    }
}

9.3 Algorithm Phases and Time Complexity

When an algorithm consists of consecutive phases, the total time complexity is the largest time complexity of any single phase. This is because the slowest phase typically becomes the bottleneck of the code.

For instance, the following code has three phases with time complexities of $O(n)$, $O(n^2)$, and $O(n)$, respectively. Thus, the total time complexity is $O(n^2)$:

for (int i = 1; i <= n; i++) {
    // phase 1 code
}
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        // phase 2 code
    }
}
for (int i = 1; i <= n; i++) {
    // phase 3 code
}

When analyzing algorithms that consist of multiple phases, consider that each phase may also introduce additional memory usage. In the example above, if phase 2 allocates a matrix of size $n \times n$, the space complexity would increase to $O(n^2)$, matching the time complexity.

Sometimes, time complexity depends on multiple factors. In this case, the formula for time complexity includes multiple variables. For example, the time complexity of the following code is $O(nm)$:

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        // code
    }
}

If the above algorithm also uses a data structure such as a matrix of size $n \times m$, the space complexity would also be $O(nm)$, increasing memory usage significantly, particularly for large input sizes.

9.4 Recursive Algorithms

The time complexity of a recursive function depends on the number of times the function is called and the time complexity of a single call. The total time complexity is the product of these values.

For example, consider the following function:

void f(int n) {
    if (n == 1) return;
    f(n-1);
}

The call f(n) makes $n$ recursive calls, and the time complexity of each call is $O(1)$. Thus, the total time complexity is $O(n)$.

9.4.1 Exponential Recursion

Consider the following function, which makes two recursive calls for every Input:

void g(int n) {
    if (n == 1) return;
    g(n-1);
    g(n-1);
}

Here, each function call generates two other calls, except when $n = 1$. The table below shows the function calls for a single initial call to $g(n)$:

Thus, the time complexity is:

Recursive functions also have space complexity considerations. Each recursive call adds to the call stack, and in the case of deep recursion (like in the exponential example above), this can lead to $O(n)$ space complexity. Be cautious with recursive algorithms, as exceeding the maximum stack size can cause a program to fail due to stack overflow.

9.4.2 Common Complexity Classes

Here is a list of common time complexities of algorithms:

• $O(1)$: A constant-time algorithm doesn’t depend on the input size. A typical example is a direct formula calculation.

• $O(\log n)$: A logarithmic algorithm often halves the input size at each step, such as binary search.

• $O(\sqrt{n})$: Slower than $O(\log n)$ but faster than $O(n)$, this complexity might appear in algorithms that involve square root reductions in input size.

• $O(n)$: A linear-time algorithm processes the input a constant number of times.

• $O(n \log n)$: Common in efficient sorting algorithms (e.g., mergesort, heapsort), or algorithms using data structures with $O(\log n)$ operations.

• $O(n^2)$: Quadratic complexity, often seen with nested loops processing all pairs of input elements.

• $O(n^3)$: Cubic complexity arises with three nested loops, such as algorithms processing all triples of input elements.

• $O(2^n)$: This complexity usually indicates exponential growth, common in recursive algorithms that explore all subsets.

• $O(n!)$: Common in algorithms that generate all permutations of the input.

9.4.3 Estimating Efficiency

When calculating an algorithm’s time complexity, you can estimate whether it will be efficient enough for the given problem before implementation. A modern computer can perform hundreds of millions of operations per second.

For example, assume that the input size is $n = 10^5$. If the time complexity is $O(n^2)$, the algorithm would perform roughly $(10^5)^2 = 10^{10}$ operations, which would take several seconds, likely exceeding the time limits of most competitive programming environments.

On the other hand, given the input size, we can estimate the required time complexity of an algorithm. The following table provides useful estimates, assuming a time limit of one second:

For example, if the input size is $n = 10^5$, it is likely that the algorithm must have a time complexity of $O(n)$ or $O(n \log n)$. This insight can help guide the design of the algorithm and eliminate approaches that would result in worse time complexity.

While time complexity is a good estimate of efficiency, it hides constant factors. For example, an $O(n)$ algorithm might perform $n/2$ or $5n$ operations, and these constants can significantly affect the actual running time.

Since loops have a significant impact on code performance, we can dive deeper into the possible loop options available.

10. Loops the Heart of All Competitive Programming

Loops are, without a doubt, the most important part of any code, whether for competitive programming, high-performance applications, or even solving academic problems. Most programming languages offer more than one way to implement loops. In this text, since Python is only our pseudocode language, we will focus on studying loops in C++.

10.1 Deep Dive into for Loops in Competitive Programming

C++ provides several ways to iterate over elements in a vector, using different types of for loops. In this section, we will explore the various for loop options available in C++20, discussing their performance and code-writing efficiency. We will also analyze which loops are best suited for competitive programming based on input size—whether dealing with small or large datasets.

10.1.1 for Loop with Iterator

The for loop using iterators is one of the most efficient ways to iterate over a vector, especially for complex operations where you need to manipulate the elements or the iterator’s position directly.

for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << " ";
}

Utilizing iterators directly avoids unnecessary function calls such as operator[] and allows fine-grained control over the iteration. Ideal when detailed control over the iterator is necessary or when iterating over containers that do not support direct index access (e.g., std::list).

Input Size Consideration:

• For Small Inputs: This is a solid option as it allows precise control over the iteration with negligible overhead.
• For Large Inputs: Highly efficient due to minimal overhead and memory usage. However, ensure that the iterator’s operations do not induce cache misses, which can slow down performance for large datasets.

10.1.2. Classic for Loop with Index

The classic for loop using an index is efficient and provides precise control over the iteration process.

for (size_t i = 0; i < vec.size(); ++i) {
    std::cout << vec[i] << " ";
}