WolfBlue's blog

By WolfBlue, history, 2 years ago, In English

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:

Spoiler

Source: https://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

Source: https://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

Source: https://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

Key observation:

Spoiler

Source: A class in complexity theory

  • Vote: I like it
  • +218
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Auto comment: topic has been updated by WolfBlue (previous revision, new revision, compare).

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good post, thought div2 tasks are hardly called hard.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +107 Vote: I do not like it

    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.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      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?

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, thanks for the feedback. I've updated the title to be more reflective of the content by prepending the word Seemingly.

»
2 years ago, # |
Rev. 2   Vote: I like it +50 Vote: I do not like it

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$$$.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

The first problem is just WOW !!!

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This is really awesome! Thanks

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :))

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by WolfBlue (previous revision, new revision, compare).

»
2 years ago, # |
Rev. 4   Vote: I like it +9 Vote: I do not like it

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. ProblemSubmission

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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In the 4th problem there is no need for the matrix to be binary:)

  • »
    »
    2 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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!

»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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$$$.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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! :/