MINWDSUM - Editorial

PROBLEM LINKS

Practice

Contest

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 + w:
            dist[v] = dist + 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 should equal to i now
        for each edge (u, v) with weight w:
            if dist[v] > dist + w:
                dist[v] = dist + 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 :slight_smile: 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 + w and not seen[v]:
            seen[v] := true
            N_min[v] := (N_min * 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.

6 Likes

“push node v to Q[dist[i]]” shoud be “push node v to Q[dist[v]]”
and also
In that same pseudocode there is a missing loop “while Q[i] is not empty”

1 Like

This “BFS with many queues” is sometimes called Dial’s algorithm.

1 Like

I tried to use the Bellman-Ford-Moore shortest path algorithm during the contest (it uses a simple queue into which the nodes of the graph are inserted whenever the minimum distance to them is updated) - although the theoretical time complexity of this algorithm is worse than Dijkstra’s algorithm, in most cases it works much faster than Dijkstra. Moreover, the nodes were inserted in the queue in increasing order of the associated N_min value so the second pass (to compute the F values) was not necessary in this case. However, the tests were strong enough and it got TLE. I spent a lot of time trying to optimize the algorithm, because on my test cases the running time was close to the time limit so I thought that it was exceeding the time limit by just a small amount. After more than 1 hour of optimization attempts I found a case where the running time was clearly above the time limit (the solution ended up making around O(M * log(M)) distance updates), so I gave up and tried to solve whatever other problems I still had time for. For me this was quite a tricky problem (in the sense that it tricked me into believing that I could solve it one way, when in fact that wasn’t possible).

2 Likes

Thanks for pointing this out. I’ve fixed this.
But actually you could do this by your own as editorial marked as “community wiki”.

how to edit ?

There is a link to edit the post:
http://discuss.codechef.com/questions/6652/edit/
However I’ve remembered that to do this you need to have some minimum amount of karma.
Probably you currently don’t have access to it.

Link to tester’s solution is broken. pls fix

The link is fixed. The correct one is MINWDSUM.cpp not MINWDSUM.c :slight_smile:

It seems like it has tricked all the contestants who tried it :slight_smile:
And this appears to be the only my problem from Cook-Offs that remains unsolved.
However, both me and Hiroto considered it as easier than usual 5th problem.