NUMBGAME - Ediorial

PROBLEM LINK:

Practice

Contest

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.

Can you give a case where the ans is neither 0 nor it is the length of a.

At least we couldn’t find any counter test case for this during the test data generation. This is really a nice observation you made :slight_smile: We were neither able to prove this up. So if someone has a proof of it. Please share it!!

can any body please check why i am getting tle .thanks
[https://www.codechef.com/viewsolution/17912290][1]

Can you explain test case 5 of the example, feel like it’s solution should be 1 instead of 6. and that 1 is: bot removes 1 from 100000, so X=00000 and I also appended 00000 to X, then X=0000000000 and X mod 27 will be 0. can you tell me other 5 cases?

Hi vivek2806,
Its because you have infinite no. moves left too make it divisible by 27.
100001000010000 mod 27 = 0 using your 3 moves.
As per question only 1st move is made by computer and then you can make N no. of moves.