PROBLEM LINK:
Author: Balajiganapathi S
Tester: Jingbo Shang
Editorialist: Utkarsh Saxena
PROBLEM
Given 2 integers A and M. Construct a set S of all integers that can be obtained by
deleting exactly one digit of A.
Find number of integers in S such that
concatenating zero or more integers from S to the right of it will give a multiple of M.
Constraints: 1 \le A \le 10^{10^6}, 1\leq M\leq 10^3
EXPLANATION
Let the number of digits in A be D.
The number of elements in the set S will be D (repetitions are allowed).
Since the final aim is to make a number X such that X\equiv0\space mod\space M,
it is better to calculate each operation mod\space M.
\therefore Total number of distinct integers mod\space M in S can be atmost M.
We can find the integer mod\space M made by deleting i^{th} digit of A as
P_{i-1}*10^{N-i}*S_{i+1} mod\space M.
Here P_i = integer mod\space M represented by A[1..i],
S_i = integer mod\space M represented by A[i..N]
Denote S^\prime = The set of distinct integers mod\space M in S.
Assume we have concatenated some elements of S to form an integer \equiv X\space mod\space M.
Adding one more integer Y \in S to the right of X.
The new integer thus formed Z = X * 10^{N-1} + Y \space mod\space M.
Thus for a given remainder X we can convert it to another integer with remainder Z by the above formula.
We can make a graph of M vertices for these transitions.
The i^{th} node denotes that there exists a set of integers in S when concatenated together given i\space mod\space M.
There is a directed edge form node X to node Z if there exists a Y in S^\prime
such that Z = X * 10^{N-1} + Y \space mod\space M.
To answer the problem we need to find those nodes from which there is a path to node 0
and also are present in S^\prime.
This is equivalent to finding all those nodes that are reachable from 0 in the reverse
graph (direction of edges reversed).
Time Complexity
Array P_i, Array S_i and Set S^\prime can be calculated in O(N)
Graph can be developed in O(M^2) time and space.
Finding all reachable nodes from 0 will take another O(M^2) time for bfs.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
We were neither able to prove this up. So if someone has a proof of it. Please share it!!