Sorry

Правка en1, от 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(n^2)$$$ pass;
  • make $$$O(nd)$$$ fail;
  • make $$$d$$$ small enough (i.e., $$$\leq 10^6$$$), 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 $$$d \leq 10^9$$$ 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).

Теги sorry

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский TheScrasse 2023-12-24 20:35:14 1076 Initial revision (published)