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).