Challenge: To Heap or Not to Heap
Subdomeniu: Combinatorics (combinatorics)
Scor cont: 100.0 / 100
Submission status: Accepted
Submission score: 1.0
Submission ID: 464819261
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/to-heap-or-not-to-heap/problem
Cerinta
Consider a rooted binary tree with $n$ vertices containing numbers. Each vertex of the tree either has two sons (left son and right son), or no sons. We will call such a tree _heap_, if and only if for all vertices (except the root), the number assigned the vertex is smaller or equal to the parent's number.
Consider a heap and the following function:
dfs(vertex){
print number in the vertex
if (vertex is not a leaf) {
dfs(left son of the vertex)
dfs(right son of the vertex)
}
}
You are given a sequence $a[1..n]$ of $n$ numbers. Your task is to calculate how many heaps will produce this sequence after calling `dfs(root)`. It is guaranteed that the sequence is generated by `generate()` function listed in the input format section below. Since the number of heaps can be very large, output its value modulo $1000000007~(10^9 + 7)$.
**Constraints**
$1 \le n < 2 \times 10^5$
$1 \le a_i \le n$Input Format
The first line contains a single odd integer $n$. The second line contains $n$ space-separated integers $a_1, a_2, \dots, a_n$ $-$ the result of `dfs(root)` call.
The sequence is generated by this algorithm:
int n, k, ptr
array of integers a[1 .. n]
generate(){
read odd n
create array val[1 .. n]
for each i from 1 to n
val[i] = random(1, n) //random(l, r) returns uniform integer from [l, r]
ptr = 1
sort array val by non-increasing
gen_heap(val)
}
gen_heap(array values){
k = size of values
a[ptr] = values[1]
ptr = ptr + 1
if(k == 1)
return
create two empty arrays left, right
for each i from 2 to k - 1
if(random(1, 2) == 1){
add values[i] to the end of left
}else{
add values[i] to the end of right
}
if(left has even size)
add values[k] to the end of left
else
add values[k] to the end of right
gen_heap(left);
gen_heap(right);
}Output Format
Output the number of heaps that will produce the given sequence modulo $1000000007~(10^9 + 7)$.Cod sursa
#include <bits/stdc++.h>
using namespace std;
static const int MOD = 1000000007;
struct Frame {
int l, r;
int phase; // 0=init, 1=iterate splits
int curL;
int endL;
int maxL;
long long ans;
};
static inline long long keyOf(int l, int r) {
return ( (long long)l << 21 ) ^ (long long)r; // n < 2e5, 21 bits is safe
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
if (n == 1) {
cout << 1 << '\n';
return 0;
}
int maxK = (n - 1) / 2;
vector<int> inv(maxK + 2, 0), catalan(maxK + 1, 0);
inv[1] = 1;
for (int i = 2; i <= maxK + 1; ++i) {
inv[i] = MOD - (long long)(MOD / i) * inv[MOD % i] % MOD;
}
catalan[0] = 1;
for (int k = 1; k <= maxK; ++k) {
catalan[k] = (long long)catalan[k - 1] * (4LL * k - 2) % MOD * inv[k + 1] % MOD;
}
// next strictly greater element index
vector<int> bigger(n, n);
vector<int> st;
st.reserve(n);
for (int i = 0; i < n; ++i) {
while (!st.empty() && a[st.back()] < a[i]) {
bigger[st.back()] = i;
st.pop_back();
}
st.push_back(i);
}
// prefix count of strict increases
vector<int> inc(n, 0);
for (int i = 1; i < n; ++i) {
inc[i] = inc[i - 1] + (a[i - 1] < a[i] ? 1 : 0);
}
unordered_map<long long, int> memo;
memo.reserve((size_t)n * 8);
memo.max_load_factor(0.7f);
vector<Frame> stackFrames;
stackFrames.reserve((size_t)n * 4);
stackFrames.push_back({0, n - 1, 0, 0, 0, 0, 0});
while (!stackFrames.empty()) {
Frame &f = stackFrames.back();
long long key = keyOf(f.l, f.r);
auto itMemo = memo.find(key);
if (itMemo != memo.end()) {
stackFrames.pop_back();
continue;
}
if (f.phase == 0) {
int len = f.r - f.l + 1;
if (f.l >= f.r) {
memo[key] = 1;
stackFrames.pop_back();
continue;
}
if ((len & 1) == 0) {
memo[key] = 0;
stackFrames.pop_back();
continue;
}
// root must be maximum of interval (no strictly greater inside)
if (bigger[f.l] <= f.r) {
memo[key] = 0;
stackFrames.pop_back();
continue;
}
// fully non-increasing segment -> Catalan shortcut
if (inc[f.r] - inc[f.l] == 0) {
memo[key] = catalan[(len - 1) / 2];
stackFrames.pop_back();
continue;
}
f.phase = 1;
f.curL = 1;
f.maxL = bigger[f.l + 1] - (f.l + 1);
f.endL = min(len - 1, f.maxL + 1); // iterate L in [1, endL) by +2
f.ans = 0;
}
bool pushed = false;
while (f.curL < f.endL) {
int L = f.curL;
int l1 = f.l + 1;
int r1 = f.l + L;
int l2 = f.l + L + 1;
int r2 = f.r;
// right subtree root must be maximum on [l2..r2]
if (bigger[l2] <= r2) {
f.curL += 2;
continue;
}
long long k1 = keyOf(l1, r1);
auto it1 = memo.find(k1);
if (it1 == memo.end()) {
stackFrames.push_back({l1, r1, 0, 0, 0, 0, 0});
pushed = true;
break;
}
long long k2 = keyOf(l2, r2);
auto it2 = memo.find(k2);
if (it2 == memo.end()) {
stackFrames.push_back({l2, r2, 0, 0, 0, 0, 0});
pushed = true;
break;
}
f.ans = (f.ans + 1LL * it1->second * it2->second) % MOD;
f.curL += 2;
}
if (pushed) continue;
memo[key] = (int)f.ans;
stackFrames.pop_back();
}
cout << memo[keyOf(0, n - 1)] << '\n';
return 0;
}
HackerRank Combinatorics – To Heap or Not to Heap