ACM14AM3-Editorial

PROBLEM LINK:

Practice
Contest

Author: Utkarsh
Tester:
Editorialist: Jingbo Shang, Anudeep

DIFFICULTY:

Easy

PREREQUISITES:

Dynamic Programming

PROBLEM:

Given a string S which has ‘0’ - ‘9’. Find number of substrings, which when represented in base 10, whose remainder under mod M equals to L.

EXPLANATION:

Let F[i][j] denote the number of substrings ended at i-th character and the value mod M equals to j.

Therefore, we can try to extend F[i][j] to F[i + 1][(j * 10 + S[i + 1]] % 10] by simply add the next character. Or, one can also take the single character i+1-th into account.

So, we can formally have the algorithm as following:

  1. Initially, F[i][S[i] % M] is 1. Because we can only choose the single character.
  2. Then, F[i + 1][(j * 10 + S[i + 1]] % 10] += F[i][j], by extending substrings.
  3. The final answer should be the sum of F[1…|S|][L].

This algorithm’s time complexity is O(|S|L), which is efficient enough for this problem.

AUTHOR’S AND TESTER’S SOLUTIONS:

The links will be fixed soon.

Author’s solution can be found here.
Tester’s solution can be found here.

2 Likes

Instead of mod 10 it should be mod M.

Thank you for this. Was looking for it few days ago, couldn’t find. Why is there no editorial link in problem page?