Winner Strength Editorial

Problem -
A_CODENITE24

Author -
sathvik36

Observations -
In a match between two players, no matter which player wins, the winner’s strength will be the sum of the two players.

Explanation -
Imagine you have a series of players, each with an initial strength represented in an array S, where S[i] is the strength of the ith player. Each match involves two players competing, and the winner’s strength becomes the sum of both players’ strengths.

Here’s how the process unfolds:

  1. Initial Match (First and Second Players): The first match involves the players with strengths S[0] and S[1]. The winner’s new strength is the sum of these two strengths, so the winner has strength S[0] + S[1].
  2. Subsequent Matches: In the next match, the player with strength S[0] + S[1] faces the third player with strength S[2]. The winner’s new strength is now S[0] + S[1] + S[2].
  3. Continuing the Pattern: This process repeats, with each match involving the current winner and the next player in line. After each match, the winner’s strength becomes the cumulative sum of all players who have participated so far.
  4. Final Match Outcome: By the time the last match concludes, the final winner will have a strength equal to the sum of all players’ initial strengths in the array S. This is because every player contributes their strength once during the series of matches.

In summary, since each player contributes their strength in every match they participate in, the ultimate winner at the end will carry the cumulative strength of all players who participated. Thus, the final strength is simply the sum of all values in S.

Time Complexity -

Time complexity is O(n) per test case.

Code -

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        int tot_strength=0;
        for(int i=0;i<n;i++){
            int strength_i;
            cin >> strength_i;
            tot_strength+=strength_i;
        }
        cout << tot_strength << '\n';
    }

    return 0;
}