ACM14AM3-Editorial

acm-icpc
acmamr14
dynamic-programming
easy
editorial

#1

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*[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*[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*[S* % M] is 1. Because we can only choose the single character.
  2. Then, F[i + 1][(j * 10 + S[i + 1]] % 10] += F*[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

Instead of mod 10 it should be mod M.


#3

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