Question here: https://www.codechef.com/practice/course/4-star-difficulty-problems/DIFF1900/problems/SEGDIV?tab=statement
I'm intrigued about this submission over here: https://www.codechef.com/viewsolution/82916450
I have no idea why it works. The poster also just left out the proof part and simply wrote, "It's difficult to prove it". Is there any proof of this or is just conveniently satisfies for the given question's constraints? (n <= 500)
no
holy based
Elements of the sequence in this submission will satisfy $$$a_i = a_{i-j} + j + 2\big\lceil\frac{j}{2}\big\rceil$$$.
For a subarray of length $$$k$$$ ending at position $$$i$$$, the sum of elements is then $$$\sum_{j=0}^{k-1} \big( a_i - j - 2\big\lceil\frac{j}{2}\big\rceil\big) = (ka_i) - \big(\frac{1}{2}k(k-1)\big) - \big(\frac{1}{2}k(k-1) + \big\lceil\frac{k-1}{2}\big\rceil\big) = ka_i - \big\lceil\frac{k-1}{2}\big\rceil$$$.
$$$ka_i$$$ will be divisible by $$$k$$$, but $$$0 < \big\lceil\frac{k-1}{2}\big\rceil < k$$$ for all $$$k \geq 2$$$ and so the sum will never be divisible by the length.