DmitryGrigorev's blog

By DmitryGrigorev, history, 3 weeks ago, In English

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.

300iq, what is your opinion?

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

»
3 weeks ago, # |
  Vote: I like it +72 Vote: I do not like it

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.