↵
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://mirror.codeforces.com/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://mirror.codeforces.com/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://mirror.codeforces.com/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↵
↵
↵
