CEOI 2010 - A Huge Tower

Official Analysis

Explanation

First, let's define some variables. Let $a_1, a_2, ..., a_n$ be the block sizes, sorted from least to greatest. Let $b_i$ be the number of indices $j$ such that $j < i$ and $a_i \leq a_j + d$. Let $\texttt{ans}_i$ be the answer if the tower consisted of only the blocks $a_1, a_2, ..., a_i$. Of course, this means that $\texttt{ans}_n$ will be the final answer.

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

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

Implementation

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

Time Complexity: $\mathcal{O}(N \log N)$

Copy
#include <algorithm>
#include <iostream>
#include <vector>

const int MOD = 1e9 + 9;

int main() {
	int n, d;
	std::cin >> n >> d;
	std::vector<int> blocks(n);

Copy
import java.io.*;
import java.util.*;

public class tower {
	static final int MOD = 1000000009;
	public static void main(String[] args) {
		Kattio io = new Kattio();

		int n = io.nextInt();
		int d = io.nextInt();

Copy
MOD = 10**9 + 9

n, d = map(int, input().split())
blocks = list(map(int, input().split()))

blocks.sort()  # sort the blocks

right = 0
res = 1
for left in range(n):