PROBLEM LINKS
DIFFICULTY
MEDIUM
PREREQUISITES
Breadth-First Search with Many Queues, Dijkstra’s Algorithm
PROBLEM
We are given an integer M and 10 integers W[0], W[1], …, W[9]. Calculate the value of
F(N_min(0)) F(N_min(1)) + … + F(N_min(M-1))
where
- S(i) = weighted digit sum of i (each digit d has weight W[d])
- S_min(i) = minimum weighted digit sum of all non-negative integers having residue R modulo M
- N_min(i) = minimum integer X having X mod M = i and S(X) = S_min(i)
- F(i) = i interpreted in base 3141, modulo 2^32.
EXPLANATION
We can separate the problem into two phases. First, calculating S_min(i) for 0 ≤ i < M. Second, calculating N_min(i) for 0 ≤ i < M.
Calculating S_min(i)
Recall that S_min(i) is the minimum weighted digit sum for residue i modulo M. Since M can be quite large, it seems that we cannot iterate over 0 ≤ i < M and calculate S_min(i) independently. We need a faster way.
Suppose we have an integer X1 that has residue M1 modulo M. What happen when we append another digit D at the end of X1? We will have another integer X2 that has residue M2 modulo M, such that:
X2 = X1 × 10 + D M2 = (M1 × 10 + D) mod M S(X2) = S(X1) + W[D]
Hence by appending a digit to an integer, we increase the weighted digit sum and change the residue to another. In fact, we can consider an integer X as appending the digits of X sequentially to integer 0. We can model this a graph! Let’s have M nodes for each integer 0, 1, …, M-1. For each pair of nodes M1 and M2, we have a directed edge M1 -> M2 with weight W[D] if M2 = (M1 × 10 + D) mod M.
After building the graph, then S(X) is simply the shortest path from node 0 to node (X mod M).
We can calculate the weighted shortest path from node 0 to all other nodes using some shortest path algorithm like Dijkstra’s. However, Dijkstra’s runs in O((V + E) log V) and is too slow for the given constraints. In this problem, S(i) will not be too large for all i, so we can use BFS (breadth-first search) with many queues as follows.
Usually, Dijsktra’s runs in the following way:
while PQ is not empty:
pop node u from PQ
skip u if it was seen before
for each edge (u, v) with weight w:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
push node v to PQ
Then, we can exploit the small S(i) to modify the above algorithm using BFS with many queues:
for i := 0; i < MAX_S_I; i++:
while Q[i] is not empty:
pop node u from Q[i]
skip u if it was seen before
// dist[u] should equal to i now
for each edge (u, v) with weight w:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
push node v to Q[dist[v]]
Essentially, we have many queues that represents the distances from the source (node 0). Initially we push node 0 to Q[0] and then we iterate the queues in increasing order of distances, guaranteeing it to work exactly the same way as Dijkstra’s. The difference is that we cut the log V factor, so we have an O(V + E) algorithm that fits to the given constraints.
The number of queues is equal to the maximum distance a node can have. In this problem, it is equal to the maximum possible value of S_min(i). An upper bound of S_min(i) is max{W[d]} × (number of digits in i), since i itself has residue i modulo M 
Therefore, the number of queues is at most 314 × 7, plus 1 (we have additional Q[0] as well).
Calculating N_min(i)
Now that we have S_min(i), how to construct a minimum integer having S(i) = S_min(i)? We construct this digit-by-digit from the most significant digit to the least significant digit, each picking the smallest possible digit. Therefore the resulting number will be minimum. We can use BFS to do this as follows. Note that we will store directly the value of F(N_min(i)), which can be interpreted as a number in base 3141, modulo 2^32.
for i := 0; i < M; i++:
seen[i] := false
N_min[i] := 0
seen[0] := true
Q.push(0)
while Q is not empty:
pop node u from Q
for each edge (u, v) with weight w:
if dist[v] == dist[u] + w and not seen[v]:
seen[v] := true
N_min[v] := (N_min[u] * 3141 + w) mod 2^32
push node v to Q
The answer will be N_min[0] + N_min[1] + … + N_min[M-1].
SETTER’S SOLUTION
Can be found here.
A faster solution can be found here.
TESTER’S SOLUTION
Can be found here.