CEOI 2011 - Balloons

Official Analysis

Explanation

The problem can be solved by simulation. In particular, we want to inflate the balloons from left to right. The difficult part is to find out when the new balloon $b$ touches one of the inflated balloon $a$ on its left, and how to check this for all previous inflated balloons efficiently. For notation, $a_r$ is the radius and $a_x$ the x-coordinate of balloon $a$.

First, let's determine when two balloons "touch" each other by calculating the maximum radius of the second balloon $b_r$. As the x-coordinate of the previous inflated balloon $a_x$ and its radius $a_r$ are fixed, we can construct a rectangular triangle with the center of both balloons so that both adjacent and opposite sides are parallel to the axes. Using the Pythagorean theorem, we get $(b_x - a_x)^2 + (b_r - a_r)^2 = (b_r + a_r)^2$. With some math, we can get an expression for the maximum radius of the second balloon $b_r = \frac{(b_x - a_x)^2}{4a_r}$. This tells us that the balloon $b$ can never have a larger radius than $b_r$.

With this information, we could just check every previous inflated balloon and determine what the maximum radius of our current balloon is. This, however, has the time complexity of $\mathcal{O}(n^2)$, which is too slow. Instead, we make use of our observation that any balloon $i$ with $i_r \leq b_r$ and $i_x < b_x$ will never be touched by balloons after $b$. Therefore, we store inflated balloons in a stack. Each time when we want to inflate a new balloon $b$, we check how long the radius of $b$ can be under the constraint of the first element $a$ from the stack. (Certainly, $b_r$ should still be less than the given maximum $r$. ) If $b_r \geq a_r$, we pop $a$ out from the stack and check the next element. $a$ will never be checked again. Otherwise, if $b_r < a_r$, we can stop the check and store our newly inflated balloon $b$ into this stack.

Since we remove the element from the stack once we want to check further back, we have a time complexity of $\mathcal{O}(n)$.

Copy
#include <bits/stdc++.h>
using namespace std;

const int PRECISION = 3;

/*
 * how long can the radius of the new balloon at position bx be
 * so that it touches the ballon a, which is described by
 * its x position a.first and its radius a.second
 */

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

// class Balloons causes compilation error on ojuz, and therefore bal
public class bal {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());

		// the radius of each balloon after inflating