Congruence Shortest Path

When a problem asks something like “Given $n$ integers, how many other integers can be formed from these $n$ integers (the $n$ integers may be used repeatedly)?”, “Given $n$ integers, find the smallest (largest) integer that these $n$ integers cannot form”, or “What is the minimum number of uses needed to form a number congruent to $p$ modulo $K$?”, the congruence shortest-path method can be used.

The congruence shortest-path method uses congruence to construct states, which can reduce the space complexity.

Similar to the difference constraints method, the states constructed using congruence can be regarded as vertices in a single-source shortest-path problem. The state transition in a congruence shortest-path problem is usually of the form $f(i+y) = f(i) + y$, analogous to $f(v) = f(u) +edge(u,v)$ in a single-source shortest-path problem.

Examples

Example 1

Assume without loss of generality that $x < y < z$.

Let $d_i$ be the lowest floor $p$ that can be reached using only Operation 2 and Operation 3 such that $p\bmod x = i$; in other words, it is the smallest number congruent to $i$ modulo $x$ that can be obtained after applying Operation 2 and Operation 3, and it is used to calculate the number of valid integers in this congruence class.

This gives two transitions:

• $i \xrightarrow{y} (i+y) \bmod x$

• $i \xrightarrow{z} (i+z) \bmod x$

Usually, the smallest number among a set of $a_i$ is chosen as the modulus; here that is $x$, so that the space complexity can be reduced as much as possible (by using the smallest residue system).

This is equivalent to performing the edge-construction operations in a shortest-path algorithm:

add(i, (i+y) % x, y)

add(i, (i+z) % x, z)

It remains only to find $d_0, d_1, d_2, \dots, d_{x-1}$. A single shortest-path computation yields all the corresponding $d_i$.

#include <iostream>
#include <queue>

using namespace std;
using ll = long long;
constexpr int MAXN = 100010;
constexpr ll linf = (1ull << 63) - 1;

ll h, x, y, z;
ll head[MAXN << 1], tot;
ll dis[MAXN], vis[MAXN];
queue<int> q;

struct edge {
  ll to, next, w;
} e[MAXN << 1];

void add(ll u, ll v, ll w) {
  e[++tot] = edge{v, head[u], w};
  head[u] = tot;
}

void spfa() {  // SPFA algorithm; see the shortest-path section
  dis[0] = 0;
  vis[0] = 1;
  q.push(0);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    vis[u] = 0;
    for (int i = head[u]; i; i = e[i].next) {
      int v = e[i].to, w = e[i].w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        if (!vis[v]) {
          q.push(v);
          vis[v] = 1;
        }
      }
    }
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> h;
  cin >> x >> y >> z;
  if (x == 1 || y == 1 || z == 1) {
    cout << h << '\n';
    return 0;
  }
  --h;
  for (int i = 0; i < x; i++) {
    add(i, (i + z) % x, z);
    add(i, (i + y) % x, y);
    dis[i] = linf;
  }
  spfa();
  ll ans = 0;
  for (int i = 0; i < x; i++) {
    if (h >= dis[i]) ans += (h - dis[i]) / x + 1;
  }
  cout << ans << '\n';
  return 0;
}

In fact, it is not necessary to run a standard shortest-path algorithm. Notice two special properties:

First, there are only two edge weights, and for any path, the order in which the two edge weights are traversed has no effect because addition is commutative. Therefore, we can perform two shortest-path computations, constructing edges of only one weight each time.

Second, in a graph with only one edge weight, every vertex $u$ has one incoming edge (from $(u-y) \bmod x$) and one outgoing edge (to $(u+y) \bmod x$), so the entire graph must consist of several cycles. Moreover, it can be proved that there are $\gcd(x,y)$ cycles of equal length.

Furthermore, since all edge weights are positive, after going around a cycle twice, no further relaxation is possible. A single cyclic update pass is enough. This avoids being constrained by the complexity of a general shortest-path algorithm and achieves $O(x)$.

As with difference constraints, if $\{a_1,a_2,\cdots,a_n\}$ is a solution, then $\{a_1+d,a_2+d,\cdots,a_n+d\}$ is also a solution. Therefore, in this problem, take $i=1$ as the source vertex. At this source vertex, $dis_{1}=1$ is the smallest value within the known range, so the resulting solution is also a smallest one.

The answer is:

The 1 is added because the floor containing $d_i$ is counted as well.

In the implementation, note that $h$ satisfies $h \leq 2^{63}-1$, so before solving the shortest-path problem, the initial value of $d_i$ should be at least $2^{63}$. This exceeds the maximum value of long long in C++. Therefore, one can use unsigned long long, or first set $h \gets h - 1$ and set the lowest floor to floor $0$; the rest of the code is unchanged.

#include <algorithm>
#include <climits>
#include <cstring>
#include <iostream>
#include <vector>

using ll = long long;

constexpr int maxn = 1e5 + 100;

ll d[maxn];
bool vis[maxn];
ll ans;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

void upd(int step, int M) {
  int D = gcd(step, M);
  int len = M / D;

  for (int st = 0; st < D; st++) {
    if (vis[st]) continue;
    std::vector<int> v;
    int u = st;
    for (int i = 0; i < len; i++) {
      v.push_back(u);
      vis[u] = true;
      u = (u + step) % M;
    }
    for (int r = 0; r < 2; r++) {
      for (int i = 0; i < len; i++) {
        int las = v[i];
        int now = v[(i + 1) % len];
        if (d[las] != LLONG_MAX) {
          // If d[las] = LLONG_MAX, d[las] + step would overflow, so handle it separately
          d[now] = std::min(d[now], d[las] + step);
        }
      }
    }
  }
}

int main() {
  ll h;
  std::cin >> h;
  int x[3];
  for (int i = 0; i < 3; i++) {
    std::cin >> x[i];
  }
  std::sort(x, x + 3);
  int M = x[0];

  for (int i = 0; i < M; i++) {
    d[i] = LLONG_MAX;
    // h in this problem reaches the upper bound of ll, so if ll is used, the initial value must be set to LLONG_MAX
  }
  d[0] = 0;

  upd(x[1], M);
  memset(vis, 0, sizeof(vis));
  upd(x[2], M);

  ll H = h - 1;
  ans = 0;
  for (int i = 0; i < M; i++) {
    if (d[i] <= H && d[i] != LLONG_MAX) {
      ans += (H - d[i]) / M + 1;
    }
  }
  printf("%lld\n", ans);
  return 0;
}

Example 2

This problem can be solved in $O(n\log^2 n)$ time by using cyclic convolution to optimize the complete knapsack problem, but we want a linear-time algorithm.

Observe that any positive integer can be obtained by starting from $1$ and performing multiplication by $10$ and addition of $1$ in some order; the number of additions of $1$ is exactly the digit sum of the number. This suggests using shortest paths.

For every $0\le k\le n-1$, add an edge of weight $0$ from $k$ to $10k$, and an edge of weight $1$ from $k$ to $k+1$. (All vertex numbers are interpreted modulo $n$.)

Every multiple of $n$ corresponds to a path from vertex $1$ to vertex $0$ in this graph, so it suffices to find the shortest path from $1$ to $0$. Some paths are invalid (for example, they may contain $10$ consecutive edges of weight $1$), but the answers produced by such paths can never be better, so they do not affect the answer.

The time complexity is $O(n)$.

Exercises

Luogu P3403 Jumping Machine

Luogu P2662 Cattle Farm Fence

[National Training Team] MoMo's Equation

“NOIP2018” Currency System

AGC057D - Sum Avoidance

“THUPC 2023 Preliminary Contest” Knapsack