.friday's blog

By .friday, history, 4 weeks ago, In English,

Can someone please help me out to understand the solution of 340 C -- TOURIST PROBLEM solution given below:

LINK

THANKS IN ADVANCE :)

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why are you sending a link to the C ++ code in the Java platform?)

Secondly, there is a problem analysis and officially the correct solution: Click

Good luck!

»
4 weeks ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

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 :)