A pattern can be seen in the solution that the result will be equal to (n/2)*m . May be I am missing any mathematical concept behind this reason. Can anyone provide me the mathematical logic behind the solution? Why is this working?
Problem: Positive Negative Sign - LightOJ 1294 - Virtual Judge
n being divisible by 2m gives us the info that there will be equal number of positive and negative groups. Now lets take numbers from successive positive and negative group. Eg. - n=12 and m=3
-1 -2 -3 +4 +5 +6 -7 -8 -9 +10 +11 +12
In successive +ve and -ve groups, the sum of corresponding elements is m. Eg. - In 1st +ve and 1st -ve group we have -
4 + (-1) =3
5 + (-2) = 3
6 + (-3) = 3
Choosing elements from successive +ve and -ve groups we get m for each pair of numbers in the sequence. Thus answer = m*(no. of pairs) = m*(n/2)
The Sum is given by, - (1+2+3+…+m) + (m+1 + m+2 + m+3 +…+ 2m) - (2m+1 + 2m+2 + 2m+3 +…+ 3m) + (3m+1 + 3m+2 + 3m+3 +…+ 4m)…
Formulating them we get, - (m*(m+1))/2 + (m*(3m+1))/2 - (m*(5m+1))/2 + (m*(7m+1))/2 …
Taking (m/2) common, we get
-> (m/2) * ((3m+1 + 7m+1 + 11m+1) … - (m+1 + 5m+1 + 9m+1 …))
All 1s get cancelled, and we get
-> (m/2) * (3m-m + 7m-5m + 11m - 9m + …)
-> (m/2) * ( 2m + 2m + 2m + …)
Given that n is divisible by 2m, the above is written as:
(m/2) * (2m) * (n/2m) (Since there are n/2m sequence-pairs as said by @soham_mittal )
Hence, the answer is (n*m)/2.
Great ! It was easy to understand from your such explanation. Thank you
Thank you very much!