link to the problem : https://www.hackerearth.com/practice/math/combinatorics/inclusion-exclusion/practice-problems/algorithm/gadget-fan/description/
I am only able to get 68 points when i submitted an O(n) solution. I am not able to optimize it further. I read the editorial as well but i wasn't able to understand it. So, if anyone could explain me the editorial or provide an alternate efficient approach to this problem.
The intended solution is O(1)./
Case I:for k>=2*n answer is n*(n+1)/2 as it may take may possible value.
Case II:for k<=n for i , possible values are i..k-i This forms an Arithmetic Progression. if k is even this sums to k^2/4. if k is odd (k-1)(k+1)/4.
CASE III: k>n for i any value from i to n is possible subjected i <=min(k-n,n) let y=min(k-n,n) , This also forms an AP which sums to y*(2n-y+1)/2
for n>=i>y values are i...k-i , let x=n-k/2 , which sums to (2n-k-x)*x , so overall answer is addition of these both.