xiii. Ad Hoc Problem Set

Practice problems where the whole solution is an observation. Each row names the observation, so solve first and read the hint only when stuck. The list grows over time; add a row whenever an upsolved problem had a reusable idea.

Problem	Key observation	Note
CSES 1083 Missing Number	sum of $\mathrm{1..}n$ minus the given sum (or xor)	Toolkit
CSES 1069 Repetitions	one scan over runs	Arrays and Strings
CSES 1094 Increasing Array	cost is $\sum (\text{prefix max}-a_i)$	Ordering
CSES 1070 Permutations	evens then odds works for $n\ge 4$; $n=2,3$ impossible	Permutation Constructions
CSES 1071 Number Spiral	the layer is $\max (y,x)$; its parity fixes the direction	Toolkit
CSES 1072 Two Knights	all pairs minus attacking pairs $4(k-1)(k-2)$	Complementary Counting
CSES 1092 Two Sets	possible iff $n(n+1)/2$ is even; fill greedily from $n$ down	Small Answers
CSES 1754 Coin Piles	$a+b\equiv 0(\mathrm{mod}3)$ and $2\min (a,b)\ge \max (a,b)$	Invariants
CSES 1755 Palindrome Reorder	at most one odd count; build half and mirror	Arrays and Strings
CSES 1618 Trailing Zeros	count factors of 5: $\sum \lfloor n/5^i\rfloor$	Factorials
CSES 2205 Gray Code	$i\oplus (i\gg 1)$	Gray Code
CSES 2165 Tower of Hanoi	recursive structure, $2^n-1$ moves	Tower of Hanoi
POJ 1852 Ants	collisions = passing through	Ordering
Codeforces 1525B Permutation Sort	answer in $\{0,1,2,3\}$ by the ends	Small Answers
Codeforces 1696B NIT Destroys the Universe	answer in $\{0,1,2\}$ by the nonzero block	Small Answers
Codeforces 1437B Reverse Binary Strings	$\max (\#00,\#11)$	Arrays and Strings
15-puzzle solvability (classic)	inversion parity plus the blank’s row	Invariants
Mutilated chessboard (classic)	colouring	Invariants

Proof: Two Sets and Coin Piles conditions

Two Sets. Equal halves need an even total $n(n+1)/2$. Conversely, let the target be $T=n(n+1)/4$ and take numbers greedily from $n$ downward while they fit: each taken number is at most the remaining target, and once the remaining target is smaller than the next number $k$, it is at most $k-1$, so it is itself one of the untaken numbers $\mathrm{1..}k-1$. Take it and stop. Coin Piles. Each move removes 3 coins in total, so $3\mid a+b$, and each move takes at most 2 coins from any pile, so $\max (a,b)\le 2\cdot \frac{a+b}{3}$, which is equivalent to $2\min \ge \max$. Conversely, with $x$ moves of type $(2,1)$ and $y$ of type $(1,2)$, solve $2x+y=a$, $x+2y=b$: $x=(2a-b)/3$, $y=(2b-a)/3$, which are non-negative integers exactly under the two conditions.

Related: How to Practice.