Can someone please help me out to understand the solution of 340 C -- TOURIST PROBLEM solution given below:
THANKS IN ADVANCE :)
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
Название |
---|
Hey!
To solve this problem you can read the EDITORIAL HERE, you can also see the writer's solution HERE.
Now after you're done understanding the solution, let's answer your question, as in the writer's solution, you can find that the numerator (sumtot) is the next: (please notice that the indices in the writer's solution start from 1, while in the next few lines I will start them from 0 as in the solution you are asking about)
sumtot = sum1 + 2 * sum2
->
sum1 = x[0] + x[1] + ... + x[n-1]
->
sum2 = (x[0]*0-0)+(x[1]*1-x[0])+(x[2]*2-x[1]-x[0]) +...+ (x[n-1]*(n-1)-x[n-2]-x[n-3]-...-x[0])
Now you can find the next for every
x[i] ; {0 <= i <= n-1}
:**sumtot[i]** = x[i] + 2 * { i - ( n - 1 - i ) } * x[i]
->
sumtot[i] = x[i] + 2 ( 2 * i + 1 - n ) * x[i]
->
sumtot[i] = x[i] * ( 3 + 4 * i - 2 * n )
And finally,
sumtot = SUM of all sumtot[i]
hope every thing is clear now :)