WolfBlue's blog

By WolfBlue, history, 6 months 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

Read more »

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

By WolfBlue, history, 4 years ago, In English

After a long time of trying to solve this problem, I was excited to finally have a solution that seemed to work.

I quickly submitted the solution, but to my great surprise, I obtained a TLE. I quickly searched through the code for anything suspicious, but I could not find anything — it seems to be very clearly O(n^2), with n at most 5000... but it still takes far too long: running it on my computer it seemed to take more than 1 second for the loop where I simply initialize all the values to Infinity!

Does anybody know why it would take so long to do such a simple task as this? What am I missing here?

Read more »

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