DmitryGrigorev's blog

By DmitryGrigorev, history, 3 weeks ago,

Actually, the solution to the Grakn Forces F problem seems pretty easy, but somehow I didn't come up with the intended one. I wrote some solution making $O(n \cdot log^2(n))$ queries in the worst case, which I actually didn't even seriously suppose to pass.

After the contest, I run the stress and it turned out that the solution fails in plenty of tests (around $1000$ numbers specifically).

It would definitely be caught if the number of tests was greater. It seems that there are not more than $10$ tests that pretend to be random (except very small numbers and very large numbers that I tested by myself). So my question is — what is the reason for this number to be so small?

I believe that tests must distinguish proper solutions and some shit like this that works very sometimes if it's possible. I understand the point that sometimes it's hard to generate tests, but here we just needed to have only a sufficient number of random tests to hack my solution, but definitely more than $10$. Here I had ~$50$ % chance to pass these $10$ tests, that's what actually happened.

 » 3 weeks ago, # |   +72 Well, organizers apparently didn't predict any random-ish solution with 50% of passing a test. What I would for sure include in tests are tests of form $n = 2^k$ or $n = 2^k - 1$. If these are missing then yeah, tests are weak.