DIGFORST - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

HARD

EXPLANATION

At first we could see this problem as “find the shortest path (smallest digits-sum) from 1 to N satisfying the constructed number is divisible by it’s digits”. Then we just use a shortest-path algorithm to solve it (eg. Dijkstra), here I use Bellman-Ford with queue. We construct a graph with vertices formatted (v, d, r) where v: vertex no., d: a 7-bit number letting you know which digits are there in the constructed number, and r: the remainder when dividing the constructed number to 420 (the LCM of 1…7). We start with the vertex (1, 0, 0), anytime you travel through a vertex you will get new vertex as (v’, d’, r’) where r’ = (r * 10+digit) % 420. And we record the answer everytime we meet any vertex ( N , d * , r * ) satisfying r * is divisible by any detected digits in d *. Finally just choose the smallest answer to output.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

1 Like