Блог пользователя harrypotter0

Problem in Subtask 2 of this problem .
Автор harrypotter0, история, 8 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    friend could you explain it a bit more .

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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

        → Ответить