Can somebody help with this problem

This is the problem link… https://www.codechef.com/CODO2021/problems/COG2103

There is a mathematical equation given, and we need to find the summation over it:
The answer to which is:
n*(n-1)/2
Can , somebody please explain this, how did we reach to this conclusion…
Thanks…

1 Like

Let us first reduce F(x) to something that is more comprehensible for the sake of the problem,
Math1
As a result, we can now define F (i/n) as
Math2
In this form, let us focus particularly on the exponent of n.
There may be two cases:

  • Case I : n is odd.
    In this case, the value of n - 2i ranges from n-2, n-4, n-6, n-8, … when i = 1, 2, 3, 4, … to …5, 3, 1, -1, 3, 5, … when i = …(n-3)/2, (n-1)/2, (n+1)/2, (n+3)/2, … to finally …8-n, 6-n, 4-n, 2-n when i = …n-4, n-3, n-2, n-1. Thus, we can observe that the exponents in the first half (first (n-1)/2 terms) are the negative of those in the second half (second (n-1)/2 terms) and vice versa. Thus, a series (as was to be calculated in the question) of the following form is formed

  • Case II : n is even
    In this case except for the middle term F(1/2) (when i = n/2) the rest of the series works in a similar fashion as for the odd number n-1. Thus the series results to
    F(1/2) + ((n-1)-1)/2
    F(1/2) + (n-2)/2
    Since F(1/2) = 1/2, we may say that the result is
    1/2 + (n-2)/2
    (n-1)/2
    Thus, we get the value of sigma (summation of F(x)) as (n-1)/2 which when multiplied by the n give us the result as
    (n * (n-1))/2
    for each test case.

Hope this helps. :slightly_smiling_face: