harrypotter0's blog

Problem in Subtask 2 of this problem .
By harrypotter0, history, 8 years ago, In English

Hi guys , recently I tried to accept this question but was partially successful in my approach (30 points only). I have tried all my efforts but could not reduce the complexity of my code .Any help or suggestion will be highly appreciated .Thanks in advanvce .

Problem link ::

My submission ::

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hint : Sort the teams according to the strength values. Now for each value in this sorted array, think about how many times this value will be added in the final sum and how many times it will be subtracted in the final sum depending on its position in the sorted array.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    friend could you explain it a bit more .

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      I will try and explain with an example. Consider that there are 4 teams with strengths 10,30,20,40.

      We sort the strength array. So, the sorted array looks like {10,20,30,40}.

      Consider the team at i'th position in this array. Clearly, it will have a higher strength than the teams at position 1 to i-1. Hence in all those pairs, When we add the absolute value of the difference of strengths to the answer, we would be adding the strength of i'th team. Also, it will have a lower strength than the teams at position i+1 to n. Hence in all those pairs, When we add the absolute value of the difference of strengths to the answer, we would be subtracting the strength of i'th team.

      We would be adding 10 0 times and subtracting 10 3 times.
      We would be adding 20 1 time and subtracting 20 2 times.
      We would be adding 30 2 times and subtracting 30 1 time.
      We would be adding 40 3 times and subtracting 40 0 times.

      Thus ans= 20+60+120-30-40-30 = 100.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it +6 Vote: I do not like it

        Thanks for such a good explanation . Now the concept is absolutely clear :) Thanks a lot the code is fully accepted now.

        → Reply