CEOI 2010 - A Huge Tower

Authors: Óscar Garries, Evan Zhao

Table of Contents

ExplanationImplementation

Official Analysis

Explanation

First, let's define some variables. Let a1,a2,...,ana_1, a_2, ..., a_n be the block sizes, sorted from least to greatest. Let bib_i be the number of indicies jj such that j<ij < i and aiaj+da_i \leq a_j + d. Let ansi\texttt{ans}_i be the answer if the tower consisted of only the blocks a1,a2,...,aia_1, a_2, ..., a_i. Of course, this means that ansn\texttt{ans}_n will be the final answer.

For any tower consisting of the first i1i - 1 blocks, there will always be bi+1b_i + 1 number of ways to insert the block of size aia_i into the tower. To understand why, consider where the block of size aia_i can be inserted. The block of size aia_i can always be inserted at the bottom of the tower, because there is no block larger than aia_i in the tower. The block with size aia_i can be inserted at the top of some block xx with size axa_x if and only if aiax+da_i \leq a_x + d.

Thus, we see that ansi=ansi1(bi+1)\texttt{ans}_i = \texttt{ans}_{i-1} \cdot (b_i + 1), because there are bi+1b_i + 1 valid ways to insert block aia_i into any of the ansi1ans_{i-1} valid towers.

C++

Implementation

This solution uses 2-pointers instead of creating the arrays ans[]ans[] and b[]b[].

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 9;
int main() {
int n, d;
cin >> n >> d;
vector<int> ar(n);

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!