1

Given r blocks of one color and g blocks of another color, a tower is formed such that:

  • Each level of the tower has width(number of blocks) = width of previous(lower) level - 1 .
  • Each level of the tower has blocks of only 1 type of color.
  • Some blocks may remain unused.

My doubt is how to

Show that the max height of the tower that can be made only depends on the total number of blocks and is independent of the number of blocks of each color.

Original question : https://codeforces.com/problemset/problem/478/D (I just have doubt in proof part.)

Pritish Nayak
  • 13

1 Answers1

0

The maximum will be equal to $k$ such that $$k = \max_{i \in \mathbb N} \{ \dfrac{i(i + 1)}{2} \leq r + g\}$$

This will give a unique $k$, and tower widths $\{1, 2, \dots, k\}$ top to bottom. Number levels from top to bottom as $\{ 1, 2, \dots , k \}$

Now consider $r$ (say red) of one colour and $g$ of another colour (say green).

Let's say I increase one colour and decrease another to keep sum the same, i.e. $r - 1$ and $g + 1$.

If the topmost block of width $1$ was red, you can make the original tower again by replacing that with the other colour(green).

Else, if it was green, then since there must exist levels $i$ and $i -1$ ($i \geq 2$) such that $i$ is made of red and $i - 1$ by green, you can swap the colours of those two levels (of widths $w$ and $w + 1$ where $w \geq 1$) so that from the original tower now you have the same height but colours $r - 1$ and $g + 1$.

Without loss of generality, this also works for $r + 1 $ and $g - 1$. So you can keep increasing one colour and decreasing the other till you get any required combination of colours. This also proves that it is, in fact, possible to make such a tower in the first place.

I may have missed some boundary case, which you can easily provide proof for.

ab123
  • 2,521