Solution

Most mainstream programming languages provide lexicographical comparison of strings as a function in the standard library or a language feature. With this feature, implementation will be simple. For example in C++, the < operator compares std::string variables in lexicographical order.

The total rating \(T\) of the users can be found using for statement. Then one can find \(T \bmod N\) to find the index of the winner.

Also, one has to find the number assigned to each user. This can be done by sorting the user’s name in lexicographical order. Most languages provide a sorting function, which enables us concise implementation. For example in C++, it can be implemented as follows:

#include <bits/stdc++.h>

using namespace std;

int main() {
    // Input
    int n;
    cin >> n;
    vector<string> s(n);
    vector<int> c(n);
    for (int i = 0; i < n; ++i) {
        cin >> s[i] >> c[i];
    }

    // Lexicographical sorting of strings
    sort(s.begin(), s.end());

    // Determine the winner's index
    int sum_rating = 0;
    for (const int e : c) {
        sum_rating += e;
    }
    const int winner = sum_rating % n;

    // Output
    cout << s[winner] << endl;
}

The complexity of sorting strings

Let \(\displaystyle M = \sum_{i=1}^{N} |S_i| \).

With merge sort, the complexity is \(O(M \log N)\). This is due to the fact that lexicographical comparison of two strings \(a\) and \(b\) can be done in \(O(\min(|a|, |b|))\) time.

std::stable_sort in C++ is almost surely implemented with merge sort, which is not actually guaranteed by the specification. This can be used.

std::sort in GCC libstdc++ typically runs fast for string comparison. The community consensus is probably that it is unclear whether the implemented algorithm is \(O(M \log N)\) at worst. At least, it is \(\displaystyle O((\max_{1 \leq i \leq N} |S_i|) N \log N)\), which is fast enough for this problem.

It can also be solved in \(O(M)\) time using SA-IS for example.