SHAMPINION's blog

By SHAMPINION, history, 5 years ago, translation, In English

Tests for problem D are too ill-conceived: kiimak's told his submission fails on a simple case with n = 5 and here is my dumb solution.

As it was mentioned, we need to check if there is a pair of indices $$$(i, j)$$$ such that $$$a_i$$$ and $$$a_j$$$ intersect but not $$$b_i$$$ and $$$b_j$$$(or vice versa). That is what we do to find those indices:

Perform the following operation 5000 times. Take a randomly generated pivot index not chosen before. This index might be $$$i$$$ in our assumption. Then iterate through $$$[1\dots n]$$$ looking for $$$j$$$. If there is one suitable for us then the answer is NO, we can stop our algorithm. Else try taking another $$$i$$$. This runs in $$$\mathcal{O}(5000 \times n)$$$. Now I'm going to tell why it's a terrible solution and why it mustn't pass the tests(thanks to lemelisk, it's already hacked).

Imagine a test where $$$n = 100000$$$ and there are only two segments intersecting in $$$a$$$ (let their indices be $$$i$$$ and $$$j$$$) and no segments intersecting at all in $$$b$$$. Obviously, the answer is NO, the only suitable pair is $$$(i, j)$$$. What is the probability of picking it? It equals to the probability of picking $$$i$$$ or $$$j$$$ as the pivot index. We pick only $$$\frac{5000}{10^5} = \frac{1}{20} = 0.05$$$ of numbers. So the probability of neither picking $$$i$$$ nor $$$j$$$ is $$$0.95 \times 0.95 = 0.9025$$$. So adding this testcase or the similar one would let my solution fail with a huge probability.

nong, try harder next time!

Full text and comments »

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