Here I've enumerated some of my favorite problems. The 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:
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:
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:
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:
Key observation:
Source: A class in complexity theory
Auto comment: topic has been updated by WolfBlue (previous revision, new revision, compare).
Good post, thought div2 tasks are hardly called hard.
They are hard for the auditory they are aiming for, which is div. 2. It's like chess grandmaster shouting at newbies for not playing moves that are obvious to him. But does he realize that it's obvious, not because it's actually pretty easy to spot, but because he's got experience? In the past, he could overlook these moves too, in the past, you could find problems listed above hard. If you find something easy, it doesn't necessarily mean that it's easy by definition, it means that you are strong enough to find it easy.
I think her point is that this is exactly the type of problem that comes up as Div2 A, B and C. Problems that look hard at first sight but are trivialized by simple observations. You could open almost any Div2 round and find problem like these (well, except problem 4 which is unlike the others and has nothing to do with the title). What's so interesting about a blog post with random unspecial problems?
I thought these were particularly nice problems and over the course of lots of competitions my personal favorites. So readers of a similar mindset to me would think that it would be very interesting. Of course, someone with a lot of experience or someone who likes a different kind of problem might think they are just random problems.
Hi, thanks for the feedback. I've updated the title to be more reflective of the content by prepending the word Seemingly.
Dude, it's possible to multiply binary matrices REALLY fast.
My implementation of bit matrix multiplication fits in $$$0.9s$$$ on CF with $$$N=5000$$$.
Nice comment, although the algorithm can be further made 10~20x faster using method of four russians.
code (my template is for and/or boolean matrix multiplication, but ideas are similar)
Also, this type of implementation will outperform the ones that compute one C[i][j] at a time (no matter whether using avx2 or not), which uses a different ordering of computation. Things are even better if one of the matrices is sparse.
The first problem is just WOW !!!
This is really awesome! Thanks
For the last problem, I thought the same thing.
The v vector set we want to check with should ideally span Rn.
I am not sure till what point are you going to check to be confident that AB is equal to C with high probability? Can you relate the number of times we are going to check with probability of success?
Also it goes without saying that all the v vectors we check with ahould be linearly independent :))
Freivalds' algorithm
Thanks nymph of delphi.
Respectfully, Prince of Transylvania
Auto comment: topic has been updated by WolfBlue (previous revision, new revision, compare).
The solution of problem $$$4$$$ doesn't require $$$A$$$, $$$B$$$ and $$$C$$$ to be binary, they can have any integer values.
Actually since the proof of Freivalds' algorithm doesn't depend on how the resulting matrix $$$d$$$ was obtained, the application of this technique can be increased a fair bit.
For example we can check for the equality arbitrary matrix polynomials of $$$A_{n \times n}$$$ having largest term $$$A^k$$$ with a probability $$$1 - \frac{1}{p}$$$ in $$$O(n ^ 2 \cdot k \cdot \log{p})$$$ using this idea. Problem — Submission
Obvious disclaimer — learning such ideas is rarely ever useful in competitive coding. I discovered Freivalds' algorithm while trying to figure out how to solve the above problem during a Codechef long contest. I have never seen this idea used anywhere in an actual non-educational competitive coding round.
The idea of Freivalds' algorithm appeared in China's NOI 2013 D1P1.
In the 4th problem there is no need for the matrix to be binary:)
That's true, the constraint to take the matrices mod 2 is just there to avoid having huge numbers. I also thought the binary version is a bit easier to think about and write strong test cases for/harder to cheese. But as Wielomian and wery0 point out, it leads to another solution that would pass the time limit!
Thanks to all people linking to Freivalds' algorithm. In problem 4, I initially thought that the solution is to "pack" matrices into unsigned long long numbers (matrix $$$A$$$ — row-wise, matrix $$$B$$$ — column-wise). Then the naive algorithm can be implemented in $$$O(n^3 / 64)$$$ since the sum in the multiplication definition can be expressed as sum of popcounts of bitwise and operations, ie. $$$\sum_{i < 3000 / 64} popcount(A[j][i] \, \& \, B[i][k]) \, mod\, 2$$$.
Popcount may be applied only once to the whole sum, if the summation means bitwise xor, ie. $$$popcount(\oplus_{i < 3000 / 64} (A[j][i] \, \& \, B[i][k])) \, mod \, 2$$$.
Well except the last problem rest are pretty routine problems in div2.And the last one won't we have to check A(Bv)-Cv=0 for all unit vectors in R^3000?That will anyway be an O(3000^3) task.I still wonder if there is some way to exploit the binary nature of the metrices! :/