Frenetic Array

A canvas for logic and imagination.

House of Cards (Kattis Problem)

It’s not so often I come across a problem that works out so beautifully yet requires so many different aspects in competitive programming. One particular problem, courtesy of Kattis, really did impress me.

The problem was House of Cards, and the problem was this (skip for TL;DR at bottom):

Brian and Susan are old friends, and they always dare each other to do reckless things. Recently Brian had the audacity to take the bottom right exit out of their annual maze race, instead of the usual top left one. In order to trump this, Susan needs to think big. She will build a house of cards so big that, should it topple over, the entire country would be buried by cards. It’s going to be huge! The house will have a triangular shape. The illustration to the right shows a house of height $6$ and Figure 1 shows a schematic figure of a house of height $5$.

Figure 1

For aesthetic reasons, the cards used to build the tower should feature each of the four suits (clubs, diamonds, hearts, spades) equally often. Depending on the height of the tower, this may or may not be possible. Given a lower bound $h_0$ on the height of the tower, what is the smallest possible height $h \geq h_0$ such that it is possible to build the tower?

TL;DR: Using Figure 1 as a reference, you are given a lower bound on a height for a tower of cards. However, there must be an equal distribution of all four suites; clubs, diamonds, hearts, and spades.

This implies that the number of cards have to be divisible by $4$. Seeing as the input was huge $1 \leq h_0 \leq 10^{1000}$, there was no brute forcing this. So, first thought: turn this into a closed-form series, and solve the series.

Getting the values for the first five heights, I got the following set:

$${2, 7, 15, 25, 40, \ldots}$$

I was able to turn this set into a series quite easily:

$$\sum_{n = 1} ^{h_0} \left(3n - 1\right)$$

This turned into the following equation:

$$\frac{1}{2} h_0(3h_0 + 1)$$

So, all I had to do was plug $h_0$ in the equation, and increment while the number was not divisible by $4$. Then, I realized how large the input really was. The input size ($1 \cdot 10^{1000}$) was orders of magnitudes larger than typical, large data types would allow ($1.84 \cdot 10^{19}$).

I realized this couldn’t be tested against a intensive data set, because there is only one number to calculate. I thought, since the series always subtracts one, the minimum times I must increment should roughly be four. Keeping this in mind, I decided to use Python. Python can work with arbitrarily large numbers, making it ideal in this situation.

I sat down, hoped for the best, and wrote the following code.

def getNumberOfCards(x):  
    return (3*pow(x, 2) + x) // 2


height = int(input())  
while (getNumberOfCards(height) % 4 != 0):  
    height += 1

print(height)  

With a run time of 0.02 seconds, it worked.

Painting Gabriel's Horn

There are many things in the world of mathematics and physics that are really quite unintuitive — however, I am not sure there will be anything more unintuitive to me than Gabriel's Horn.

Gabriel's Horn is thus: suppose you have the function $y = \frac{1}{x}$ where $x \in \mathbb{R}^+, 1 \leq x \leq \infty$, rotated around the $x$ axis; not too difficult to conceptualize, it looks like a horn of sorts. But here's the paradox.

Suppose we want to calculate the volume. Simple enough, using solids of revolution, we can show the volume to be:

$$V = \pi \lim_{t \rightarrow \infty} \int _1 ^t \frac{1}{x^2} dx = \pi \lim _{t \rightarrow \infty} ( 1 - \frac{1}{t} ) = \pi $$

A simple, elegant solution; we can expect the volume to be exactly $\pi$. So, let's see about the surface area.

We know the general definition of the arc length to be $\int _a ^b \sqrt{1 + f'(x)^2}$, so combining this with our solids of revolution, we should get

$$A = 2\pi \lim _{t \rightarrow \infty} \int _1 ^t \frac{1}{x} \sqrt{1 + \left( -\frac{1}{x^2} \right)^2 } dx $$

However, this is not a trivial integral; however, there is a trick we can do. Suppose we take the integral $$2\pi \lim _{t \rightarrow \infty} \int _1 ^t \frac{dx}{x}$$ instead, and we can prove this integral will always be equal to or smaller than the former integral (because of the disappearance of $\sqrt{1 + (-\frac{1}{x^2})}$). So, taking this rather trivial integral, we can see that

$$ A \geq 2\pi \lim _{t \rightarrow \infty} \int _1 ^t \frac{dx}{x} \implies A \geq \lim _{t \rightarrow \infty} 2\pi \ln(t) $$

Wait a minute; it's divergent! So we know the volume $V = \pi$, but the surface area $A \geq \infty$. This is no mistake, the math is valid. And that is one of the most counter-intuitive things I have ever ran into.

A horn you can fill with paint, but you can't paint the surface.

Calculus II & III Notes

I have decided to post my Calculus II and Calculus III notes.

Note that these notes are heavily based on Calculus for Scientists and Engineers by Briggs, Cochran, Gillett, and Schulz. I do not own the material and no copyright infringement is intended.

They can be found in projects, under notes.