Common Mistakes

This page mainly lists some mistakes that many people often make in contests.

Mistakes Caused by Different Environments

  • Using scanf or printf with %I64d as the format specifier may cause input/output format errors under Linux.

Mistakes That Cause CE

These mistakes are mostly lexical, syntactic, or semantic errors. Their causes are relatively simple, and they are not difficult to fix.

Examples:

  • Spelling errors such as writing int main() as int mian().

  • Forgetting the semicolon after writing a struct or class.

  • Declaring an array that is too large, using an illegal function (such as multithreading) on an OJ, or declaring a function without defining it can cause a linker error.

  • Mismatched function parameter types.

    • Example: when using the <algorithm> header's max function, passing one parameter of type int and another of type long long.

      // query is a custom function that returns a long long
printf("%lld\n", max(0, query(1, 1, n, l, r));

// Error    no matching overloaded function instance for the parameter list "std::max"

  • Skipping the initialization of some local variables when using goto and switch-case.

Mistakes That Do Not Cause CE but Cause Warnings

Although programs containing these mistakes can be compiled, they will most likely produce incorrect results at runtime. The compiler points out these mistakes when compiling with the -W{warningtype} option.

  • Confusing the assignment operator = with the comparison operator ==.

    • Example:

      std::srand(std::time(nullptr));
int n = std::rand();
if (n = 1)
  printf("Yes");
else
  printf("No");

// No matter what random value n obtains, the output is certainly Yes
// Warning    incorrect operator: constant assignment in a Boolean context. Consider using the == operator instead.

    • If you really intend to use = in a statement where == would normally be used (for example, while (foo = bar)) and do not want to receive a warning, you can use double parentheses: while ((foo = bar)).

  • Mistakes caused by operator precedence.

    • Example:

      // Incorrect
// std::cout << (1 << 1 + 1);
// Correct
std::cout << ((1 << 1) + 1);

// Warning    <<: check whether the operator precedence may be incorrect; use parentheses to clarify precedence

  • Using the static qualifier incorrectly.

  • When using scanf for input, omitting the address-of operator &.

  • Using parameter types that do not match the format specifiers with scanf or printf.

  • Using bitwise operations and the logical operator == at the same time without parentheses.

    • Example: (x >> j) & 3 == 2

  • Overflow of an int literal.

    • Example: long long x = 0x7f7f7f7f7f7f7f7f, 1<<62.

  • Uninitialized local variables.

    ???+ note "What Happens to an Uninitialized Variable" Original text: https://loj.ac/d/3679 by @hly1204

    For example, when we declare an `int a;` in C++ without initializing it, we may sometimes think that `a` has a "random" value (although it may not actually be random), or may regard it as a fixed value, but in fact neither is true.

In a simple test program

<https://wandbox.org/permlink/T2uiVe4n9Hg4EyWT>

the code is:

```cpp
#include <iostream>

int main() {
  int a;
  std::cout << std::boolalpha << (a < 0 || a == 0 || a > 0);
  return 0;
}
```

With optimizations enabled on some compilers and environments, its output is false.

If interested, see <https://www.ralfj.de/blog/2019/07/14/uninit.html>. Although the experiment uses Rust, its essence is the same.

  • A local variable and a global variable having the same name, causing the global variable to be accidentally overwritten. (This type of error can be checked by enabling -Wshadow.)

  • Output errors caused by operator overloading.

    • Example:

      // The first << was intended to be the overloaded operator for output; the second << was intended to be the shift operator, shifting 1
// left by 1 bit. However, because parentheses were omitted, the compiler treats the second <<
// as an output operator as well, causing the output to differ from the expected result. Incorrect: std::cout << 1 << 1; Correct:
std::cout << (1 << 1);

Mistakes That Cause Neither CE nor Warnings

The compiler cannot detect these mistakes; they can only be found by examining the program yourself.

Mistakes That Cause WA

  • Failing to clear an array before reading the next test case after finishing processing the previous one.

  • Failing to account for negative numbers in fast input.

  • The bit width of the data type used is insufficient, causing overflow.

    • For example, the situation described by the saying "Three years of OI come to nothing; if you do not use long long, you will regret it." Contestants fail to use long long in the right places (defining integers as long long types), obtain an incorrect answer, and lose points.

  • When storing a graph, using node indices starting from 0 while the endpoints in the problem's edges are numbered starting from 1, and forgetting to subtract 1 during input.

  • Mistyping or reversing the greater-than/less-than signs.

  • After executing ios::sync_with_stdio(false);, mixing scanf/printf with std::cin/std::cout, causing input/output disorder.

    • Example:

      // This example illustrates the consequences of mixing two I/O methods after disabling synchronization with stdio
// It is recommended to run it step by step to observe the effect
#include <cstdio>
#include <iostream>

int main() {
  // After synchronization is disabled, cin/cout use an independent buffer instead of synchronizing output to scanf/printf
  // buffers, reducing I/O time
  std::ios::sync_with_stdio(false);
  // With cout, using '\n' for a newline buffers the content instead of outputting it immediately
  std::cout << "a\n";
  // printf's '\n' flushes printf's buffer, causing the output to be out of order
  printf("b\n");
  std::cout << "c\n";
  // The cout buffer is not output until the program terminates
  return 0;
}

  • Mistakes caused by macro expansion and the omission of parentheses.

    • Example: the value returned by this macro is not 42=164^2 = 16, but 2+2×2+2=82+2\times 2+2 = 8.

      #define square(x) x* x
printf("%d", square(2 + 2));

  • Arithmetic errors caused by not using unsigned when hashing.

    • Right-shifting a negative number fills the highest bit with 1. See Bitwise Operators.

  • Failing to delete or comment out debugging output statements.

  • Accidentally adding a ;.

    • Example:

      /* clang-format off */
while (1);
    printf("OI Wiki!\n");

  • Setting an incorrect sentinel value. For example, the 0 node of a balanced tree.

  • When using : to initialize variables in a class or struct constructor, having a declaration order that does not match the dependencies during initialization.

    • The initialization order of member variables is related to the order in which they are declared in the class, not their order in the initializer list. See the section "Initialization order" in Constructors and Member Initializer Lists.

    • Example:

      #include <iostream>

class Foo {
 public:
  int a, b;

  // a is initialized before b, so its value is indeterminate
  Foo(int x) : b(x), a(b + 1) {}
};

int main() {
  Foo bar(1, 2);
  std::cout << bar.a << ' ' << bar.b;
}

// Possible output: -858993459 1

  • Failing to merge the ancestors of the two elements when merging two sets in a disjoint-set union.

    • Example:

      f[a] = b;              // Incorrect
f[find(a)] = find(b);  // Correct

  • Using freopen with a for append writing.

    • The CCF judging environment does not clear the output file. Using a causes the previous contestant's output to also be read by the judge, resulting in WA.

Different Newline Characters

Warning

In official contests, every effort is made to ensure that the environment in which contestants solve problems is the same as the environment used for final testing.

This section only applies to mock contests and similar situations. We also recommend that problem setters make the data conform to the data format as much as possible.

Different operating systems use different symbols to mark line breaks. The following are newline characters used by several common systems:

  • LF (represented by \n): Unix or Unix-compatible systems

  • CR+LF (represented by \r\n): Windows

  • CR (represented by \r): Mac OS version 9 and earlier

C/C++ uses the escape sequence \n for a newline. This may lead us to assume that the newline character in the input is also necessarily represented by \n and to read only one character as the newline, which means that we fail to read the input file completely.

The solutions are as follows:

  • Call getchar() multiple times until the desired character is read.

  • Use cin; this may increase the constant factor of the code.

  • Use scanf("%s",str) to read a string, and then take str[0] as the input character.

  • Use scanf(" %c",&c) to filter out all whitespace characters.

Results That May Be Unknown

Undefined behavior leads to unknown results, possibly WA, RE, and so on. Compilers usually assume that your program does not exhibit undefined behavior, which is why code may behave differently with O2 enabled and disabled.

  • Division by 0 (finding the inverse of 0)

    ???+ warning "Example" cpp cout << x / 0 << endl;

  • Array (subscript) out of bounds

    For example:

    • Failing to set the initial value of a loop correctly, causing access to the element at subscript -1.

    • Failing to allocate twice the space for an undirected graph's edge table.

    • Failing to allocate four times the space for a segment tree.

    • Misreading the data range and omitting a zero.

    • Incorrectly estimating the algorithm's space complexity.

    • Calling pushup or pushdown on a leaf node when writing a segment tree.

      The correct approach is: do not go out of bounds. Remember to check your code and ensure that every subscript access x is within the defined subscript range.

  • A non-main function with a return value reaches the end without executing any return statement.

    Even if one branch has a return value, the result is still undefined if other branches do not.

    You can append -Wall to the compilation options to check whether the compiler issues a warning about a function not returning.

  • Attempting to modify a string literal

    ???+ warning "Example" cpp char *p = "OI-wiki"; p[0] = 'o'; p[1] = 'i';

    Attempting to modify a string literal in this way causes undefined behavior. Instead, use another appropriate data type, such as std::string or char[].

  • Repeatedly freeing or illegally dereferencing a region of memory

    For example:

    • Dereferencing a pointer before it has been initialized.

    • The memory region pointed to by a pointer has already been freed.

      When using erase, delete, or free, be careful not to apply the same operation multiple times to the same address/object.

  • Attempting to free part of the block of memory allocated by new []

    For example:

    object *pool = new object[POOL_SIZE];

object *pointer = pool + 10;

// Error!
delete pointer;

    This is common when a whole block is preallocated using a memory pool and an attempt is then made to use delete or free() to free an individual object obtained from the pool.

  • Dereferencing a null pointer or wild pointer

    For a null pointer: first check the null pointer, using p == nullptr or !p.

    For a wild pointer: set the pointer to nullptr when freeing it to avoid the problem.

  • Signed integer overflow

    For example, consider the expression x+1 > x.

    The normal output should be true, but when INT_MAX is used as x, the output is false. This is called signed integer overflow.

    You can use a larger data type (such as long long or __int128), or check for overflow. If nonnegative values are guaranteed, an unsigned integer type can also be used.

    Signed integer overflow may affect compiler optimizations. For example:

    int foo(int x) {
  if (x > x + 1) return 1;
  return 0;
}

    may be directly optimized by the compiler into:

    int foo(int x) { return 0; }

    This is because the compiler can assume that signed integers never overflow, so x > x + 1 can never hold.

  • Using an uninitialized variable

    ???+ warning "Example" cpp int foo(int a) { int t; /* Not initialized */ if (/* Use */ t > 3) return a; return 0; }

Mistakes That Cause RE

  • Not removing file operations (on some OJs).

  • An incorrect comparison function when sorting. std::sort requires the comparison function to define a strict weak ordering: `a b.r); else return block[a.l] < block[b.l]; }

  • Insufficient stack space under Windows, causing a stack overflow. Windows sends a SIGSEGV signal to the program, which terminates and returns 3221225725 (that is, 0xC00000FD, the NTSTATUS value STATUS_STACK_OVERFLOW). If using the gcc compiler, you can add -Wl,--stack=SIZE during compilation to specify the stack-size limit, where SIZE is the stack size in bytes.

    Insufficient stack space under Linux causes a stack overflow. Linux will write head_info chaotically in the stack heap; this usually causes the program to terminate immediately in the vast majority of cases, displaying messages such as 段错误（核心已转储）/segmentation fault (core dumped). You can use ulimit -s SIZE in the terminal to modify the stack-space limit of the current terminal, where SIZE is the stack-space size in kilobytes (KB). Note that if you set the stack-space limit too large, infinite recursion may cause the recursion stack to become too large and subsequently crash the system.

Mistakes That Cause TLE

  • Failing to check the boundary in divide and conquer, resulting in infinite recursion.

  • Infinite loops.

    • Duplicate loop-variable names.

    • Reversed loop direction.

  • Failing to mark whether a state has been visited during BFS.

  • Writing min/max using macro expansion

    This mistake greatly increases program runtime and may even directly affect the code's time complexity. It is especially common among beginners writing segment trees.

    A common incorrect implementation is:

    #define Min(x, y) ((x) < (y) ? (x) : (y))
#define Max(x, y) ((x) > (y) ? (x) : (y))

    Although this is correct in terms of correctness, if a function's return value is directly passed to max, such as a = Max(func1(), func2()), and the function takes a long time to execute, program performance is greatly affected. After macro expansion, this becomes a = func1() > func2() ? func1() : func2(), which calls the function three times, one more time than a normal max function. Note that if func1() returns a different answer each time, this form of max can also produce an incorrect result. For example, func1() could be return ++a; with a as a global variable.

    Example: the following code can be forced to take Θ(n)\Theta(n) time per query, resulting in TLE.

    #define max(x, y) ((x) > (y) ? (x) : (y))

int query(int t, int l, int r, int ql, int qr) {
  if (ql <= l && qr >= r) {
    ++ti[t];  // Record the number of node visits for convenient debugging
    return vi[t];
  }

  int mid = (l + r) >> 1;
  if (mid >= qr) return query(lt(t), l, mid, ql, qr);
  if (mid < ql) return query(rt(t), mid + 1, r, ql, qr);
  return max(query(lt(t), l, mid, ql, qr), query(rt(t), mid + 1, r, ql, qr));
}

  • Appending characters to a std::string using the + operator

    This creates a temporary string object, modifies it, and then assigns it to the original variable. The compiler cannot optimize away this mistake. When the data size is large, it may cause the time complexity to deteriorate.

    A common incorrect implementation is:

    std::string a;
char b = 'c';
a = a + b;

    When this code executes, the program first creates a temporary string variable, then stores this value of a in the temporary variable, appends this value of b at the end, and finally stores the result back to a.

    It can be seen from the assembly result that a = a + b calls three functions in std::__cxx11::basic_string, namely operator+, operator=, and variable creation.

    The correct implementation should be:

    std::string a;
char b = 'c';
a += b;

    This implementation directly appends character b to string a and calls operator+= only once. For a more detailed performance comparison, see Benchmark.

  • Not removing file operations (on some OJs).

  • Repeatedly executing a function whose complexity is not O(1)O(1) in a for/while loop. Strictly speaking, this may change the time complexity.

  • Using an incorrect midpoint formula or termination condition when performing binary search.

Mistakes That Cause MLE

  • An array that is too large.

    ??? note "Detailed Explanation of Memory Usage Metrics under Linux" > Too long; didn't read: when declaring a particularly large global static array in an examination in the CCF series, be especially careful. Because all arrays declared by the program are counted toward memory usage (unlike most online judging platforms, which only count the portions actually used), in some cases this may even cause the entire problem to receive MLE.

    -   RSS and VSZ[^ref1][^ref2]

    1.  VSZ (Virtual Memory Size)[^ref3]

        VSZ represents the **virtual memory size** of a process, that is, the total size of the virtual address space that the process can access. It is usually displayed in KB.

        Virtual memory is a logical concept and is usually much larger than actual memory usage.

        Under Linux, you can use the `top` command to view the components of a process's memory usage. The `VIRT` column represents its virtual memory usage.

        Virtual memory generally includes address space allocated by the process but not actually used. In short, the amount requested is approximately the amount of virtual memory.

        It is especially important to note that common online judging platforms usually count only physical memory usage. However, the CCF judging environment counts virtual memory. This means that even if only a small part of a large global static array is used, declaring it may consume a large amount of space.
    2.  RSS (Resident Set Size)[^ref4]

        RSS represents the **physical memory size** actually occupied by a process, that is, the size of page frames resident in RAM. It is usually displayed in KB.

        Similarly, you can use `top` to view physical memory in the `RES` column.

        RSS generally includes only the parts actually loaded into physical memory. In other words, it reflects how much is actually used.
-   Analysis of memory-usage behavior

    Suppose the following array is declared:

    ```cpp
    const int SIZE = 1e8;
    int arr[SIZE];  // Space occupied: 4 bytes * 100 million = 400 MB
    ```

    This is a static array allocated in the global data segment. If the array is not explicitly initialized, it is usually allocated in the BSS segment (if explicitly initialized, such as all zeros or other values, it is allocated in the DATA segment).

    -   When the array is not used at all (assuming the compiler does not optimize it away)

        -   Physical memory: if the array is not accessed, demand paging means that the memory pages have not yet been loaded into physical memory. Physical memory does not increase, or increases only slightly (some metadata pages may be loaded).
        -   Virtual memory: the size of the array is counted toward virtual memory (an increase of `400MB`), because the array's entire virtual address space has been allocated.
    -   When the array is partially used

        Suppose only a small number of elements of the array are used, for example:

        ```cpp
        arr[0] = 1;
        arr[999999] = 2;
        ```

        -   Virtual memory: virtual memory does not change and remains `400MB`.
        -   Physical memory: each access to an element of the array loads this virtual page into physical memory. Assuming a system page size of `4KB`, each page contains $4 \text{KB} ÷ 4 \text{B} = 1024$ `int` elements. Two accesses to the array may load two pages, increasing physical memory by approximately $2 \times 4 \text{KB} = 8 \text{KB}$.
    -   When most of the array is used

        Suppose values are assigned to the first $50,000,000$ elements of the array:

        ```cpp
        for (int i = 0; i < 50000000; ++i) {
          arr[i] = i;
        }
        ```

        -   Virtual memory (VSZ): VSZ remains `400MB` and does not change.
        -   Physical memory (RSS): accesses are sequential (the $50,000,000$ elements accessed are adjacent in memory), so the number of pages that need to be loaded is $\left\lceil \dfrac{50,000,000}{1024} \right\rceil = 48,828$ pages.

            Assuming a page size of `4KB`, the total is therefore $48,828 \times 4 \text{KB} \approx 190 \text{MB}$, and physical memory increases to approximately `190MB`.

            Note: if the array is assigned using random subscripts, the physical memory usage will differ substantially from the prediction (because pages are loaded according to addresses, so random assignments cause a large number of memory pages to be loaded).

        In brief: as the proportion of the array that is accessed increases, physical memory approaches virtual memory (assuming no page reclamation occurs).

  • Inserting too many elements into an STL container.

    • This often happens because an infinite loop occurs in a loop that inserts elements into an STL container.

    • It may also be caused by being hacked.

Excessive Constant Factors

  • Failing to define the modulus as a constant when defining it.

    • Example:

      // int mod = 998244353;      // Incorrect
const int mod = 998244353;  // Correct; makes it convenient for the compiler to treat it as a constant

  • Using unnecessary recursion (tail recursion is excluded).

  • Introducing a large amount of extra computation when converting recursion into iteration.

Mistakes That Only Affect Local Program Execution

  • Possible mistakes in file operations:

    • During differential testing, failing to close the file pointer with fclose(fp) before assigning fp = fopen() again. This causes the process to have a large number of wild file pointers.

    • Omitting .in/.out from the filename in freopen().

  • Forgetting to delete or free heap space after using it.

References and Notes

Previous section
010 Blockwise Precomputation
Next section
012 Common Tricks

This content comes from OI Wiki: Common Mistakes. See the original for authors and revision history. AIOJ has adapted the formatting, in-site links, and resource paths.

Content is shared under CC BY-SA 4.0 and SATA license; additional terms are governed by the original notice. Thanks to the OI Wiki authors and contributors; per the SATA terms, please visit the OI Wiki repository and star it to show your support.