Please subscribe to the official Codeforces channel in Telegram via the link ×

321625uzki's blog

By 321625uzki, history, 7 weeks ago, In English

(When discussing, problem setter think his program have error middle result because of "Numerical instability"(may refer to floating error?), but I think this is an algorithm error, and the realization of me and Rainbow_sjy is hacked at local by myself when choosing the same seed)

Specifically, for the minimum circle coverage, we have that if $$$p_i$$$, $$$p_j$$$, and $$$p_k$$$ are the three points of $$$C_{res}$$$, then for a $$$p_{k'} \not\in C{res}$$$, there is a conclusion that $$$p_k \in C_{p_k',p_j,p_i}$$$ (Note that we have the condition $$$p_i \not \in C_{k,k',j},p_j \not \in C_{k,k',i}$$$).so the new circle can cover all the original points.But for this question, we do not have such a conclusion.

For example, when


thus,our (R2,R31,R77) circle isn't restricted by R77,though we've known it should be restricted when we ends for-loop.that may become serious problems.when we use (R10,R31,R77) to instead (R2,R31,R77),R77 is still useless and the restrict of R2 is thrown away. When R2 is a useful restrict at R[1,77] the process will returned a invalid answer in spite of R2.

If you stick to let the result circle tangent to the three circle, instead of the biggest circle contained of the circles(like std is doing), there will be other questions like some input circle don't intersect with result circle(because it's not biggest).

The std solution returned NaN first time, when using my seed mt19937(321625) to call std::shuffle.Then it returned right, because it always reshuffle when returned NaN, but now no one can prove the correct of expect time complexity.And I don't know how to make that wrong or TLE.But the problem setter acknowledges that "There is a one-out-of-thousand chance that the returned answer will return a non-NaN value which deviates far from the actual answer." when testing his solution.

The data mentioned earlier can be downloaded from .You can download it without login and have a test whether your solution is right when using seed mt19937(321625) and std::shuffle to shuffle the sequence.

Full text and comments »

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