Skip to content

Common Techniques

This page lists some small tricks in competitive programming.

Utilizing Locality

Locality refers to the tendency of a program to reference data items that are near other recently referenced data items, or the recently referenced data items themselves. Locality is divided into temporal locality and spatial locality.

For details, see Loop Unroll, Code Layout Optimizations, etc.

Loop Macro Definitions

The following code can be simplified using macro definitions:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
for (int i = 0; i < N; i++) {
  // Loop content omitted
}

// Simplified using macro
#define f(x, y, z) for (int x = (y), __ = (z); x < __; ++x)

// When writing loop code, it can be simplified to `f(i, 0, N)`. For example:
// a is an STL container
f(i, 0, a.size()) { ... }

Another useful macro definition is recommended:

1
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)

Making Good Use of namespace

Using namespace can improve program readability and facilitate debugging.

Example: NOI 2018 Dragon Slayer 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// NOI 2018 Dragon Slayer 40-point partial score code
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
long long n, m, a[100005], p[100005], aw[100005], atk[100005];

namespace one_game {
// Variables can also be declared inside namespace
void solve() {
  for (int y = 0;; y++)
    if ((a[1] + p[1] * y) % atk[1] == 0) {
      cout << (a[1] + p[1] * y) / atk[1] << endl;
      return;
    }
}
}  // namespace one_game

namespace p_1 {
void solve() {
  if (atk[1] == 1) {  // solve 1-2
    sort(a + 1, a + n + 1);
    cout << a[n] << endl;
    return;
  } else if (m == 1) {  // solve 3-4
    long long k = atk[1], kt = ceil(a[1] * 1.0 / k);
    for (int i = 2; i <= n; i++)
      k = aw[i - 1], kt = max(kt, (long long)ceil(a[i] * 1.0 / k));
    cout << k << endl;
  }
}
}  // namespace p_1

int main() {
  int T;
  cin >> T;
  while (T--) {
    memset(a, 0, sizeof(a));
    memset(p, 0, sizeof(p));
    memset(aw, 0, sizeof(aw));
    memset(atk, 0, sizeof(atk));
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> p[i];
    for (int i = 1; i <= n; i++) cin >> aw[i];
    for (int i = 1; i <= m; i++) cin >> atk[i];
    if (n == 1 && m == 1)
      one_game::solve();  // solve 8-13
    else if (p[1] == 1)
      p_1::solve();  // solve 1-4 or 14-15
    else
      cout << -1 << endl;
  }
  return 0;
}

Using Macros for Debugging

When testing locally, programmers often need to add some debugging statements. When submitting to an OJ, to prevent the output of debugging statements from affecting the system's judgment of the program's output, they must be removed, which is time-consuming. In such cases, defining macros can save time. The general program framework is as follows:

1
2
3
4
5
6
7
8
#define DEBUG
#ifdef DEBUG
// do something when DEBUG is defined
#endif
// or
#ifndef DEBUG
// do something when DEBUG isn't defined
#endif

#ifdef checks whether the corresponding identifier defined by #define exists in the program. If defined, it executes the following statements. #ifndef executes the following statements when the corresponding identifier is not defined.

Thus, you can write debugging code inside #ifdef DEBUG and the actual submission code inside #ifndef DEBUG, making local testing convenient. When submitting, simply comment out the #define DEBUG line. Alternatively, you can define the DEBUG identifier during compilation using the -DDEBUG compilation option instead of defining it in the program. This way, you don't need to modify the program when submitting.

Many OJs enable the -DONLINE_JUDGE compilation option. Making good use of this feature can save a lot of time.

Stress Testing

Stress testing is a method for verification or debugging by comparing the outputs of two programs to check correctness. You can compare your program's output with another program's output to determine if your program is correct.

Since stress testing needs to be performed multiple times, it should be automated through batch processing.

Specifically, stress testing requires a data generator and two programs whose outputs are to be compared.

Each run of the data generator writes generated data to an input file. Using redirection, both programs read the data and write their outputs to specified files. Finally, use the fc command on Windows (or diff on Linux) to compare the files and verify program correctness. If an error is found, you can directly use the generated data for debugging.

The general framework for a stress testing program is as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
#include <cstdlib>

int main() {
  // For Windows
  // Do not use file input/output during stress testing
  // Of course, this program can also be rewritten as a batch script
  while (true) {
    system("gen > test.in");  // Data generator writes data to input file
    system("test1.exe < test.in > a.out");  // Get program1 output
    system("test2.exe < test.in > b.out");  // Get program2 output
    if (system("fc a.out b.out")) {
      // This line compares input and output
      // fc returns 0 when outputs are identical, otherwise indicates differences
      system("pause");  // Pause to view differences
      return 0;
      // The input data is already stored in test.in and can be used directly for debugging
    }
  }
}

Memory Pool

When dynamically allocating memory, frequent use of new/malloc can consume significant time and space, and even generate many memory fragments, degrading program performance and potentially causing a correct program to TLE/MLE.

In such cases, the "memory pool" technique is useful: before actually using memory, pre-allocate a certain amount of memory as a reserve. When dynamic allocation is needed, simply allocate a block from the reserve memory.

In most OI problems, the maximum memory required can be pre-calculated and allocated in one go.

Example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
// Dynamically allocate a 32-bit signed integer array:
int* newarr(int sz) {
  static int pool[MAXN], *allocp = pool;
  return allocp += sz, allocp - sz;
}

// Code for dynamic node allocation in segment tree:
Node* newnode() {
  static Node pool[MAXN << 1], *allocp = pool - 1;
  return ++allocp;
}

References

Luogu Daily #86

Introduction to Algorithmic Competition: Exercises and Solutions

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用