Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

Sorry

Revision en1, by TheScrasse, 2023-12-24 20:35:14

Sorry for weak tests in 1917C - Watering an Array.

Initially, the statement had the array b in input, and we had to do these three things simultaneously:

  • make O(n2) pass;
  • make O(nd) fail;
  • make d small enough (i.e., 106), so that the input could be read fast in any language.

But O(nd) was too fast, so (on Dec 22) we decided to use d109 and compress the array. But testers had already tested the old version of the problem, and I can't expect testers to reset their memory and retry the problem, so no one found the wrong O(nk) solution.

I'm sorry for making at least two mistakes:

  • Modifications 2 days before the contest may be ok, but they must be checked very carefully because fewer testers will see them.
  • I should have checked the existence of a pretest with all small cases. Maybe in this problem such test is not so comfortable to make, but you can achieve a similar effect by using a pretest with many random cases where every value in the input is small.

Please downvote this blog (instead of the announcement).

Tags sorry

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English TheScrasse 2023-12-24 20:35:14 1076 Initial revision (published)