Plenty of hard problems require a hard observation or several simple ones, but usually as the difficulty scales, you need more observations or need to use less obvious observations. Here I've enumerated some of my favorite problems whose solutions appear trivial in retrospect — but the 1 line observation is quite hard to come up with. You have to think really outside of the box for these! I think such problems are quite cool and hard to come by, so please add a comment if you have any other problems of this type that you've seen! ↵
↵
They are arranged from easiest to hardest (in my opinion).↵
↵
1) For $N<10^6$, what's the Nth palindromic number in base 10 with an even number of digits? (The first is 11, then 22, 33, 44, 55, 66, 77, 88, 99, 1001).↵
↵
Key observation: ↵
↵
<spoiler summary="Spoiler">↵
Just concatenate N with itself backwards.↵
</spoiler>↵
↵
Source: https://codeforces.net/contest/688/problem/B↵
↵
2) A classic: $N < 10^6$ Ants are on a line of length $10^{15}$ at some positions $p_i$. Each has a starting position and direction left or right. They walk at a rate of 1 unit per second, and if 2 collide, both immediately turn around and walk the other way. How long will it be until no ants are on the line?↵
↵
Key observation: ↵
↵
<spoiler summary="Spoiler">↵
Since we don't care about which ant is which, we can ignore all collisions and pretend the ants pass through each other.↵
</spoiler>↵
↵
Source: https://codeforces.net/gym/102966/problem/G and other places↵
↵
3) $N<10^5$ Rectangles with ODD side lengths are on a $10^9\times 10^9$ grid. The corners of each are at integer lattice points $(x, y)$. Color each of the rectangles one of 4 colors so that no adjacent two rectangles are the same color.↵
↵
The four-color theorem shows that this is always possible, but provides no further insight for this problem.↵
↵
Key observation: ↵
↵
<spoiler summary="Spoiler">↵
If two rectangles both have their left corner at even x and even y coordinates, then they will never intersect, so we can make them the same color.↵
</spoiler>↵
↵
Source: https://codeforces.net/contest/764/problem/D↵
↵
4) You've got three $3000\times3000$ matrices $A, B,$ and $C$ containing only the elements 0 and 1. You need to output a boolean: if $AB=C$ with all elements of $AB$ taken mod 2. Note: Your method must work with high probability on ALL possible inputs. Maybe a lot of people want to hack your code.↵
↵
Solutions that won't work: ↵
↵
<spoiler summary="Spoiler">↵
The naive method involves checking if, for all $j,k<3000,$ $\sum_{i} A_{ji}B_{ik} = C_{jk}$. This is cubic and will be too slow. We could try to just check if it holds for few random integers $j$, $k$, but this will probably be wrong on inputs where only one entry of $C_{jk}$ is wrong. A different approach is needed. Note, the mod 2 constraint isn't important at all for the solution so don't get confused by it.↵
</spoiler>↵
↵
Key observation: ↵
↵
<spoiler summary="Spoiler">↵
If the matrices are equal, then for any random binary vector $v$, $ABv = Cv$.↵
</spoiler>↵
↵
Source: A class in complexity theory↵
↵
↵
↵
They are arranged from easiest to hardest (in my opinion).↵
↵
1) For $N<10^6$, what's the Nth palindromic number in base 10 with an even number of digits? (The first is 11, then 22, 33, 44, 55, 66, 77, 88, 99, 1001).↵
↵
Key observation: ↵
↵
<spoiler summary="Spoiler">↵
Just concatenate N with itself backwards.↵
</spoiler>↵
↵
Source: https://codeforces.net/contest/688/problem/B↵
↵
2) A classic: $N < 10^6$ Ants are on a line of length $10^{15}$ at some positions $p_i$. Each has a starting position and direction left or right. They walk at a rate of 1 unit per second, and if 2 collide, both immediately turn around and walk the other way. How long will it be until no ants are on the line?↵
↵
Key observation: ↵
↵
<spoiler summary="Spoiler">↵
Since we don't care about which ant is which, we can ignore all collisions and pretend the ants pass through each other.↵
</spoiler>↵
↵
Source: https://codeforces.net/gym/102966/problem/G and other places↵
↵
3) $N<10^5$ Rectangles with ODD side lengths are on a $10^9\times 10^9$ grid. The corners of each are at integer lattice points $(x, y)$. Color each of the rectangles one of 4 colors so that no adjacent two rectangles are the same color.↵
↵
The four-color theorem shows that this is always possible, but provides no further insight for this problem.↵
↵
Key observation: ↵
↵
<spoiler summary="Spoiler">↵
If two rectangles both have their left corner at even x and even y coordinates, then they will never intersect, so we can make them the same color.↵
</spoiler>↵
↵
Source: https://codeforces.net/contest/764/problem/D↵
↵
4) You've got three $3000\times3000$ matrices $A, B,$ and $C$ containing only the elements 0 and 1. You need to output a boolean: if $AB=C$ with all elements of $AB$ taken mod 2. Note: Your method must work with high probability on ALL possible inputs. Maybe a lot of people want to hack your code.↵
↵
Solutions that won't work: ↵
↵
<spoiler summary="Spoiler">↵
The naive method involves checking if, for all $j,k<3000,$ $\sum_{i} A_{ji}B_{ik} = C_{jk}$. This is cubic and will be too slow. We could try to just check if it holds for few random integers $j$, $k$, but this will probably be wrong on inputs where only one entry of $C_{jk}$ is wrong. A different approach is needed. Note, the mod 2 constraint isn't important at all for the solution so don't get confused by it.↵
</spoiler>↵
↵
Key observation: ↵
↵
<spoiler summary="Spoiler">↵
If the matrices are equal, then for any random binary vector $v$, $ABv = Cv$.↵
</spoiler>↵
↵
Source: A class in complexity theory↵
↵
↵
