E. A Recurring Problem
47th Annual hosted by ICPC World Championship AASTMT Problem E A Recurring Problem Time...
Problem Statement
Formatted from the contest statement text, with sample tests broken out into copyable blocks.
47th Annual hosted by
ICPC World
Championship AASTMT Problem E
A Recurring Problem
Time limit: 20 seconds
You have a very big problem! You love recurrence relations, perhaps a bit too much. In particular,
you are a fan of positive linear recurrence relations (PLRR), which can be defined as follows. First, you
choose the order k of the relation. Then you choose coefficients c1 , c2 , . . . , ck , and the first k elements of
a sequence a1 , a2 , . . . , ak . The relation is called “positive” if all of these numbers are positive integers.
The rest of the sequence can then be generated indefinitely using the formulaai+k = c1 · ai + c2 · ai+1 + · · · + ck · ai+k−1 for i ≥ 1.The Fibonacci sequence is the most famous recurrence of this form, but there are many others. In fact, yesterday, in a fit of mad mathematical inspiration, you wrote down all possible ways of choosing a positive linear recurrence relation, and each associated infinite sequence, on some index cards, one per card. (You have a lot of index cards; you buy in bulk.) It has all been a bit of a blur. But when you woke up today, you realized that you do not have a good way to order or count the PLRRs. You tried just sorting the sequences lexicographically, but there are too many that start with “1” — you will never make it to the later ones. Fortunately, inspiration struck again! You realized that you can instead order the PLRRs lexicographi- cally by the generated part of the sequence only (that is, the part of the sequence starting after the initial k values). Ties are broken by lexicographic order of the coefficients. For example k = 1, c1 = 2, a1 = 2 comes before k = 2, (c1 , c2 ) = (2, 1), (a1 , a2 ) = (1, 2), even though the continuation of the sequence is the same for both. This allows you to properly index your cards, starting from 1, with every card being assigned a number. Given the number on a card, describe the sequence on it!
Input
The input consists of a single line with an integer n (1 ≤ n ≤ 109 ), the index of the desired PLRR.
Output
Output four lines detailing the desired recurrence relation. The first line contains its order k. The second line contains the k coefficients c1 , . . . , ck . The third line contains the k starting values a1 , . . . , ak . The fourth line contains the first 10 of the generated values.
Sample Tests
3
World Finals | ICPC 2023 Lu
47th Annual
ICPC World
Championship2
1 1
1 1
2 3 5 8 13 21 34 55 89 144
xor
hosted by
AASTMT12354
1 1 3 1
3 2 1 1
9 15 44 99 255 611 1519 3706 9129 22377Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Key Observations
The generated sequence is strictly increasing, because \[ a_{i+k}\ge c_ka_{i+k-1}\ge a_{i+k-1} \] and all terms are positive.
The central task is to count how many PLRRs start with a given prefix of generated values.
Suppose the current generated prefix is $x=(x_1,\dots,x_\ell)$ and we also remember the previous $\ell-1$ generated values $a=(a_1,\dots,a_{\ell-1})$. If the last coefficient of the recurrence is $c$ and the previous hidden value is $a_0$, then this coefficient contributes \[ c\cdot(a_0,a_1,\dots,a_{\ell-1}) \] to the prefix $x$. Removing that contribution produces a smaller subproblem of the same kind.
Once these prefix counts are known, the desired card is found by lexicographic block skipping: decide the first generated value, then the second, and so on.
Algorithm
For a length-$\ell$ vector $x=(x_1,\dots,x_\ell)$ and a length-$(\ell-1)$ vector $a=(a_1,\dots,a_{\ell-1})$, let $f(x,a)$ be the number of ways to choose a positive recurrence suffix consistent with that data. Initially, for a generated prefix $x$, we use $a=(x_1,\dots,x_{\ell-1})$.
The recursion is \[ f(x,a)=
\] where we only sum over pairs $(a_0,c)$ that keep all coordinates nonnegative.
The implementation is:
Memoize $f(x,a)$ for prefixes of length at most $5$.
Find the first generated value by scanning $1,2,3,\dots$ and subtracting whole blocks $f((x_1),())$ until the correct block is reached.
Extend the current prefix one value at a time. For each possible next value, count how many PLRRs realize that extension, and skip whole blocks until the target one is found.
Stop when the current prefix identifies exactly one PLRR, or when five generated values are fixed.
If only one PLRR remains, reconstruct its coefficients and initial values by following any valid recursive decomposition.
Otherwise enumerate all candidates consistent with the chosen 5-term prefix, compare them by generated sequence and then by coefficient vector, and select the remaining rank inside that block.
Correctness Proof
We prove that the algorithm returns the correct answer.
Lemma 1.
The recursion for $f(x,a)$ counts exactly the PLRRs consistent with the state $(x,a)$.
Proof.
Take any valid PLRR consistent with $(x,a)$. Let $c$ be its last coefficient and let $a_0$ be the value immediately preceding the remembered vector $a$. Then the contribution of this last coefficient to the generated prefix is exactly $c(a_0,a_1,\dots,a_{\ell-1})$. After subtracting it, the remaining earlier coefficients form a valid smaller PLRR counted by the recursive call.
Conversely, every choice of $(a_0,c)$ together with every recursively counted smaller PLRR uniquely extends to a valid larger PLRR by restoring that last coefficient. Hence the recursion is a bijective decomposition of the counted objects. □
Lemma 2.
At every reconstruction step, the block sizes computed by the algorithm are exactly the sizes of the lexicographic groups of PLRRs sharing the current generated prefix.
Proof.
By Lemma 1, $f$ counts exactly how many PLRRs start with any proposed prefix. Since the generated sequence is strictly increasing, trying the next generated value in increasing order lists the lexicographic blocks in the correct order. Subtracting these block sizes therefore moves to the unique block containing the desired card. Repeating the same argument extends the prefix correctly one position at a time. □
Lemma 3.
If two distinct recurrences have orders at most $K$, then their generated parts differ within the first $2K$ generated values.
Proof.
Let the two generated sequences be $u$ and $v$, of orders $p,q \le K$. Their difference satisfies a linear recurrence of order at most $p+q \le 2K$ (for example, using the product of the two characteristic polynomials). If its first $2K$ values were all zero, then every later value would also be forced to zero. So two distinct generated sequences of orders at most $K$ must differ within the first $2K$ terms. □
Theorem.
The algorithm outputs the PLRR on the $n$th card.
Proof.
By Lemma 2, the prefix-building phase always chooses the unique lexicographic block containing the desired card, so after that phase the target card is among the remaining candidates.
If only one candidate remains, reconstruction is correct by Lemma 1. Otherwise the algorithm enumerates all candidates consistent with the fixed 5-term prefix. By Lemma 3, comparing the first $2K$ generated terms, where $K$ is the maximum candidate order, is enough to determine the lexicographic order of the generated parts exactly. Ties are then broken by the coefficient vectors, exactly as required by the statement. Therefore the selected candidate is precisely the $n$th card. □
Complexity Analysis
Let $S$ be the number of memoized states $f(x,a)$ reached by the search and let $T$ be the total number of recursive transitions tried across those states. The counting phase takes $O(T)$ time and $O(S)$ memory. If explicit enumeration is needed at the end, let $C$ be the number of remaining candidates for the chosen 5-term prefix; the extra work is $O(C \log C)$ for sorting plus linear time to generate the comparison prefixes.
Implementation Notes
Counts are capped at a large constant, because only comparisons with the remaining rank matter.
A useful pruning rule is: if deleting the last coordinate already yields an impossible prefix, then the current state is impossible as well.
The implementation fixes at most five generated values before explicit enumeration; this keeps the memoized state representation small and is sufficient for the official data.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
namespace {
using int64 = long long;
constexpr int64 CAP = (1LL << 60);
struct Key {
int len = 0;
array<int64, 5> x{};
array<int64, 5> a{};
bool operator==(const Key& other) const {
return len == other.len && x == other.x && a == other.a;
}
};
struct KeyHash {
size_t operator()(const Key& key) const {
uint64_t hash = key.len;
auto mix = [&](uint64_t value) {
hash ^= value + 0x9e3779b97f4a7c15ULL + (hash << 6) + (hash >> 2);
};
for (int i = 0; i < 5; ++i) {
mix(static_cast<uint64_t>(key.x[i]));
}
for (int i = 0; i < 5; ++i) {
mix(static_cast<uint64_t>(key.a[i]));
}
return static_cast<size_t>(hash);
}
};
unordered_map<Key, int64, KeyHash> memo_count;
int64 count_state(int len, const array<int64, 5>& x, const array<int64, 5>& a) {
for (int i = 0; i < len; ++i) {
if (x[i] < 0) {
return 0;
}
}
bool all_zero = true;
for (int i = 0; i < len; ++i) {
if (x[i] != 0) {
all_zero = false;
break;
}
}
if (all_zero) {
return 1;
}
if (len > 1 && count_state(len - 1, x, a) == 0) {
return 0;
}
Key key;
key.len = len;
key.x = x;
key.a = a;
unordered_map<Key, int64, KeyHash>::const_iterator it = memo_count.find(key);
if (it != memo_count.end()) {
return it->second;
}
int64 total = 0;
for (int64 a0 = 1; a0 <= x[0]; ++a0) {
int64 max_coeff = x[0] / a0;
for (int i = 1; i < len; ++i) {
max_coeff = min(max_coeff, x[i] / a[i - 1]);
}
array<int64, 5> next_a{};
if (len > 1) {
next_a[0] = a0;
for (int i = 1; i < len - 1; ++i) {
next_a[i] = a[i - 1];
}
}
for (int64 coeff = 1; coeff <= max_coeff; ++coeff) {
array<int64, 5> next_x = x;
next_x[0] -= coeff * a0;
for (int i = 1; i < len; ++i) {
next_x[i] -= coeff * a[i - 1];
}
total += count_state(len, next_x, next_a);
if (total > CAP) {
total = CAP;
break;
}
}
if (total == CAP) {
break;
}
}
memo_count[key] = total;
return total;
}
int64 count_prefix(const vector<int64>& x, const vector<int64>& a) {
array<int64, 5> xx{};
array<int64, 5> aa{};
int len = static_cast<int>(x.size());
for (int i = 0; i < len; ++i) {
xx[i] = x[i];
}
for (int i = 0; i + 1 < len; ++i) {
aa[i] = a[i];
}
return count_state(len, xx, aa);
}
bool reconstruct_unique(int len, const array<int64, 5>& x, const array<int64, 5>& a,
vector<int64>& coeff_rev, vector<int64>& init_rev) {
bool all_zero = true;
for (int i = 0; i < len; ++i) {
if (x[i] != 0) {
all_zero = false;
break;
}
}
if (all_zero) {
return true;
}
for (int64 a0 = 1; a0 <= x[0]; ++a0) {
int64 max_coeff = x[0] / a0;
for (int i = 1; i < len; ++i) {
max_coeff = min(max_coeff, x[i] / a[i - 1]);
}
array<int64, 5> next_a{};
if (len > 1) {
next_a[0] = a0;
for (int i = 1; i < len - 1; ++i) {
next_a[i] = a[i - 1];
}
}
for (int64 coeff = 1; coeff <= max_coeff; ++coeff) {
array<int64, 5> next_x = x;
next_x[0] -= coeff * a0;
for (int i = 1; i < len; ++i) {
next_x[i] -= coeff * a[i - 1];
}
if (count_state(len, next_x, next_a) > 0) {
coeff_rev.push_back(coeff);
init_rev.push_back(a0);
return reconstruct_unique(len, next_x, next_a, coeff_rev, init_rev);
}
}
}
return false;
}
void enumerate_all(int len, const array<int64, 5>& x, const array<int64, 5>& a,
vector<int64>& coeff_rev, vector<int64>& init_rev,
vector<pair<vector<int64>, vector<int64>>>& out) {
bool all_zero = true;
for (int i = 0; i < len; ++i) {
if (x[i] != 0) {
all_zero = false;
break;
}
}
if (all_zero) {
vector<int64> coeffs(coeff_rev.rbegin(), coeff_rev.rend());
vector<int64> initials(init_rev.rbegin(), init_rev.rend());
out.push_back(make_pair(coeffs, initials));
return;
}
for (int64 a0 = 1; a0 <= x[0]; ++a0) {
int64 max_coeff = x[0] / a0;
for (int i = 1; i < len; ++i) {
max_coeff = min(max_coeff, x[i] / a[i - 1]);
}
array<int64, 5> next_a{};
if (len > 1) {
next_a[0] = a0;
for (int i = 1; i < len - 1; ++i) {
next_a[i] = a[i - 1];
}
}
for (int64 coeff = 1; coeff <= max_coeff; ++coeff) {
array<int64, 5> next_x = x;
next_x[0] -= coeff * a0;
for (int i = 1; i < len; ++i) {
next_x[i] -= coeff * a[i - 1];
}
if (count_state(len, next_x, next_a) == 0) {
continue;
}
coeff_rev.push_back(coeff);
init_rev.push_back(a0);
enumerate_all(len, next_x, next_a, coeff_rev, init_rev, out);
coeff_rev.pop_back();
init_rev.pop_back();
}
}
}
int64 exact_count(const vector<int64>& generated_prefix) {
vector<int64> prev_terms;
if (!generated_prefix.empty()) {
prev_terms.assign(generated_prefix.begin(), generated_prefix.end() - 1);
}
return count_prefix(generated_prefix, prev_terms);
}
vector<pair<int64, int64>> next_value_counts(const vector<int64>& prefix) {
vector<pair<int64, int64>> result;
int64 total = exact_count(prefix);
int64 seen = 0;
vector<int64> prev_terms = prefix;
for (int64 value = prefix.back(); seen < total; ++value) {
vector<int64> extended = prefix;
extended.push_back(value);
int64 ways = count_prefix(extended, prev_terms);
if (ways > 0) {
result.push_back(make_pair(value, ways));
seen += ways;
}
}
return result;
}
vector<int64> generated_terms(const vector<int64>& coeffs, const vector<int64>& initials, int count) {
vector<int64> seq = initials;
while (static_cast<int>(seq.size()) < static_cast<int>(coeffs.size()) + count) {
int64 next = 0;
for (int i = 0; i < static_cast<int>(coeffs.size()); ++i) {
next += coeffs[i] * seq[seq.size() - coeffs.size() + i];
}
seq.push_back(next);
}
return vector<int64>(seq.begin() + coeffs.size(), seq.begin() + coeffs.size() + count);
}
void solve() {
int64 n;
cin >> n;
memo_count.clear();
memo_count.reserve(1 << 20);
vector<int64> prefix;
int64 skipped = 0;
for (int64 first = 1;; ++first) {
vector<int64> current(1, first);
int64 ways = exact_count(current);
if (skipped + ways >= n) {
prefix = current;
n -= skipped;
break;
}
skipped += ways;
}
int64 branch_count = exact_count(prefix);
while (branch_count > 1 && prefix.size() < 5) {
vector<pair<int64, int64>> choices = next_value_counts(prefix);
skipped = 0;
for (int i = 0; i < static_cast<int>(choices.size()); ++i) {
if (skipped + choices[i].second >= n) {
prefix.push_back(choices[i].first);
n -= skipped;
branch_count = choices[i].second;
break;
}
skipped += choices[i].second;
}
}
vector<pair<vector<int64>, vector<int64>>> candidates;
vector<int64> coeff_rev;
vector<int64> init_rev;
if (branch_count == 1) {
array<int64, 5> x{};
array<int64, 5> a{};
for (int i = 0; i < static_cast<int>(prefix.size()); ++i) {
x[i] = prefix[i];
}
for (int i = 0; i + 1 < static_cast<int>(prefix.size()); ++i) {
a[i] = prefix[i];
}
reconstruct_unique(static_cast<int>(prefix.size()), x, a, coeff_rev, init_rev);
candidates.push_back(make_pair(vector<int64>(coeff_rev.rbegin(), coeff_rev.rend()),
vector<int64>(init_rev.rbegin(), init_rev.rend())));
} else {
array<int64, 5> x{};
array<int64, 5> a{};
for (int i = 0; i < static_cast<int>(prefix.size()); ++i) {
x[i] = prefix[i];
}
for (int i = 0; i + 1 < static_cast<int>(prefix.size()); ++i) {
a[i] = prefix[i];
}
enumerate_all(static_cast<int>(prefix.size()), x, a, coeff_rev, init_rev, candidates);
int max_order = 0;
for (int i = 0; i < static_cast<int>(candidates.size()); ++i) {
max_order = max(max_order, static_cast<int>(candidates[i].first.size()));
}
int compare_terms = max(10, 2 * max_order);
vector<pair<vector<int64>, vector<int64>>> ranked;
ranked.reserve(candidates.size());
for (int i = 0; i < static_cast<int>(candidates.size()); ++i) {
ranked.push_back(make_pair(candidates[i].first,
generated_terms(candidates[i].first, candidates[i].second, compare_terms)));
}
sort(ranked.begin(), ranked.end(),
[](const pair<vector<int64>, vector<int64>>& lhs,
const pair<vector<int64>, vector<int64>>& rhs) {
if (lhs.second != rhs.second) {
return lhs.second < rhs.second;
}
return lhs.first < rhs.first;
});
pair<vector<int64>, vector<int64>> picked = candidates[0];
picked.first = ranked[n - 1].first;
for (int i = 0; i < static_cast<int>(candidates.size()); ++i) {
if (candidates[i].first == picked.first) {
picked.second = candidates[i].second;
break;
}
}
candidates.clear();
candidates.push_back(picked);
}
const vector<int64>& coeffs = candidates[0].first;
const vector<int64>& initials = candidates[0].second;
cout << coeffs.size() << '\n';
for (int i = 0; i < static_cast<int>(coeffs.size()); ++i) {
if (i) {
cout << ' ';
}
cout << coeffs[i];
}
cout << '\n';
for (int i = 0; i < static_cast<int>(initials.size()); ++i) {
if (i) {
cout << ' ';
}
cout << initials[i];
}
cout << '\n';
vector<int64> first_ten = generated_terms(coeffs, initials, 10);
for (int i = 0; i < 10; ++i) {
if (i) {
cout << ' ';
}
cout << first_ten[i];
}
cout << '\n';
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.
Show raw files
competitive_programming/icpc/2023/E-a-recurring-problem/solution.texC++ implementationcompetitive_programming/icpc/2023/E-a-recurring-problem/solution.cppStatement textcompetitive_programming/icpc/2023/E-a-recurring-problem/statement.txtStatement PDFcompetitive_programming/icpc/2023/E-a-recurring-problem/statement.pdfMetadatacompetitive_programming/icpc/2023/E-a-recurring-problem/meta.jsonYear packetcompetitive_programming/icpc/2023/contest_problems.pdf