E - バランスチェック / Balance Check Editorial by admin
gemini-3.5-flash-thinkingOverview
This problem asks us to count the integers from \(1\) to \(N\) where the absolute difference between the “sum of digits at odd positions” and the “sum of digits at even positions” (counted from the most significant digit) is at most \(D\).
Since \(N\) can be as large as \(10^{15}\), checking each number one by one (brute force) is far too slow. For problems of the form “count integers up to \(N\) satisfying a certain condition,” the technique of Digit DP (Digit Dynamic Programming) is extremely effective.
Analysis
1. Basic Idea of Digit DP
We consider determining the digits one by one from the most significant (top) digit. For example, when \(N = 314\), we determine the hundreds digit, tens digit, and ones digit in order. During this process, we maintain the following information as states while performing transitions (determining the next digit).
is_less(less-than-\(N\) flag): A flag indicating whether the portion determined so far is already confirmed to be less than \(N\).- For example, with \(N = 314\), if we choose
2for the hundreds digit, no matter what we choose for the tens and ones digits, the number is guaranteed to be less than \(N\) (is_less = 1). - If we choose
3for the hundreds digit, it’s not yet determined whether the number is less than \(N\), so for the tens digit we can only choose digits up to1(is_less = 0).
- For example, with \(N = 314\), if we choose
2. Problem-Specific Challenges and Solutions
① Handling Leading Zeros
When \(N\) has at most 15 digits, processing a 3-digit number (e.g., 123) means we determine digits as 0, 0, 0, …, 1, 2, 3 from the top.
However, the “odd-positioned” and “even-positioned” digits in the problem statement must be counted from the actual most significant digit, excluding leading zeros.
- For 00123, the first non-zero digit 1 becomes the “1st digit (odd-positioned).”
- To handle this correctly, we include a flag is_leading_zero representing “whether all digits determined so far are \(0\)” in our state.
② Determining Odd and Even Positions
The moment the first non-zero digit appears (when is_leading_zero changes from \(1\) to \(0\)) is the “1st position (odd).” After that, odd and even positions alternate with each subsequent digit.
To manage this, we include a flag parity in our state indicating whether the next digit to be determined is at an odd or even position.
③ Difference Between Odd-Position Sum and Even-Position Sum
Let \(S_{\mathrm{odd}}\) be the sum of odd-positioned digits and \(S_{\mathrm{even}}\) be the sum of even-positioned digits. What we need is their difference \(S_{\mathrm{odd}} - S_{\mathrm{even}}\). We maintain this difference in the DP state. - When placing digit \(d\) at an odd position: add \(+d\) to the difference - When placing digit \(d\) at an even position: add \(-d\) to the difference
Since the difference can be negative, we add a sufficiently large offset value (offset = 150) to ensure that array indices are never negative.
Algorithm
DP Table Definition
We define the DP table as follows:
dp[i][is_less][is_leading_zero][parity][diff]
- i: number of digits determined so far (from \(0\) to \(L\), where \(L\) is the number of digits in \(N\))
- is_less: whether it is already confirmed to be less than \(N\) (\(0\): not confirmed, \(1\): confirmed)
- is_leading_zero: whether all digits determined so far are \(0\) (\(0\): a non-zero digit has already appeared, \(1\): all zeros)
- parity: whether the next digit to determine is at an odd or even position counting from the first non-zero digit (\(0\): odd position, \(1\): even position)
- diff: \((S_{\mathrm{odd}} - S_{\mathrm{even}}) + \text{offset}\)
Transition Rules
When determining the next digit \(d\) (\(0 \leq d \leq 9\)) from the current position, we transition as follows:
When no non-zero digit has appeared yet (
is_leading_zero == 1)- When \(d = 0\):
is_leading_zeroremains \(1\). Parity and difference do not change. - When \(d \geq 1\):
This \(d\) becomes the first non-zero digit (odd-positioned).
next_is_leading_zerobecomes \(0\), \(d\) is added to the difference, and the next parity becomes even (1).
- When \(d = 0\):
When a non-zero digit has already appeared (
is_leading_zero == 0)- If the current parity is odd (
0): add \(+d\) to the difference, and set the next parity to1. - If the current parity is even (
1): add \(-d\) to the difference, and set the next parity to0.
- If the current parity is odd (
Computing the Answer
After all digits are determined (i = L), we sum up all states where is_leading_zero == 0 (positive integer) and the absolute value of the actual difference is at most \(D\) (\(|S_{\mathrm{odd}} - S_{\mathrm{even}}| \leq D\)). This sum is the answer.
Complexity
Time Complexity
- \(O(\log_{10} N \times \text{offset})\)
- The number of digits \(L\) of \(N\) is at most \(15\).
- The number of DP states is \(15 \times 2 \times 2 \times 2 \times 300 = 36,000\).
- Each state has \(10\) transitions (digits \(0\) through \(9\)).
- The total number of loop iterations is approximately \(360,000\), which completes almost instantly (a few milliseconds) within the time limit.
Space Complexity
- \(O(\log_{10} N \times \text{offset})\)
- The DP table size is an array of
long longwith dimensions \(18 \times 2 \times 2 \times 2 \times 300\), which is approximately \(345 \text{ KB}\) — very memory-efficient.
- The DP table size is an array of
Implementation Notes
Handling Negative Indices (Offset): The difference \(S_{\mathrm{odd}} - S_{\mathrm{even}}\) can be negative. Since the maximum number of digits is \(15\), the range of the difference is at most \(-135\) to \(135\). Therefore, by adding
offset = 150, we ensure it always stays in a positive range (\(0\) to \(300\)).Counting Only Positive Integers: The problem asks for positive integers from \(1\) to \(N\). The state where all digits are \(0\) (the state with
is_leading_zero == 1) represents \(0\), so by only summing states withis_leading_zero == 0in the final computation, we correctly count only positive integers.Source Code
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
// dp[i][is_less][is_leading_zero][parity][diff]
// i: 決定した桁数 (0 to L)
// is_less: 1 if already less than N, 0 otherwise
// is_leading_zero: 1 if all digits so far are 0, 0 otherwise
// parity: 0 if next digit is odd-positioned, 1 if even-positioned (only valid if is_leading_zero is 0)
// diff: S_odd - S_even + offset
long long dp[18][2][2][2][300];
int main() {
// 高速入出力
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string S;
if (!(cin >> S)) return 0;
long long D;
if (!(cin >> D)) return 0;
int L = S.length();
int offset = 150;
dp[0][0][1][0][offset] = 1;
for (int i = 0; i < L; ++i) {
int limit_digit = S[i] - '0';
for (int is_less = 0; is_less < 2; ++is_less) {
for (int is_leading_zero = 0; is_leading_zero < 2; ++is_leading_zero) {
for (int parity = 0; parity < 2; ++parity) {
for (int diff = 0; diff < 300; ++diff) {
long long val = dp[i][is_less][is_leading_zero][parity][diff];
if (val == 0) continue;
int max_d = is_less ? 9 : limit_digit;
for (int d = 0; d <= max_d; ++d) {
int next_is_less = is_less || (d < limit_digit);
int next_is_leading_zero = is_leading_zero && (d == 0);
if (next_is_leading_zero) {
dp[i + 1][next_is_less][1][0][offset] += val;
} else {
int next_parity;
int next_diff;
if (is_leading_zero) {
// 最初の非ゼロ桁 (奇数番目の第1桁)
next_diff = diff + d;
next_parity = 1; // 次は偶数番目
} else {
if (parity == 0) {
next_diff = diff + d;
next_parity = 1;
} else {
next_diff = diff - d;
next_parity = 0;
}
}
if (next_diff >= 0 && next_diff < 300) {
dp[i + 1][next_is_less][0][next_parity][next_diff] += val;
}
}
}
}
}
}
}
}
long long ans = 0;
for (int is_less = 0; is_less < 2; ++is_less) {
for (int parity = 0; parity < 2; ++parity) {
for (int diff = 0; diff < 300; ++diff) {
long long val = dp[L][is_less][0][parity][diff];
if (val > 0) {
long long actual_diff = abs(diff - offset);
if (actual_diff <= D) {
ans += val;
}
}
}
}
}
cout << ans << "\n";
return 0;
}
This editorial was generated by gemini-3.5-flash-thinking.
posted:
last update: