PoorComparisons

We have a group of N athletes. They can play one-on-one games. Each game ends either with a win for one of the players or with a draw.

In some situations the results of these matches happen to be transitive. E.g., if A defeats B and B defeats C (or draws with C), we would expect that also A defeats C in a head-to-head game.

Sadly, it is not always the case. In real-life tournaments one can often encounter match results that are not compatible with each other.

Formally:

• We will use the character '=' to represent a draw, the character '>' to represent a win (with the player on the left defeating the player on the right), and '<' for a loss.
• If we assign integers a and b to players A and B, we say that their match result is compatible with these integers if those integers satisfy the corresponding relation.
• Given three players A, B, and C, we say that the results between A, B, and C are compatible if we can assign integers a, b, c to these players in such a way that for each pair of players their two integers are compatible with the outcome of their match.
• The weirdness of a tournament is the number of triples of distinct players that are not compatible.

We are interested in tournaments in which N players play each other exactly once. Such a tournament contains exactly T(N) = N * (N-1) * (N-2) / 6 unordered triples of distinct players.

Determine whether such a tournament can have weirdness strictly greater than 0.81 * T(N).

If yes, construct a String[] with N elements, each containing N characters. In element A, character B should be the result of the match between players A and B (from the point of view of player A), or the character '=' if A equals B.

If no, construct an empty String[].

In either case, as we want to keep the output size small, return compress(your answer), where compress is the routine given below.

/* Java */
    String compress(String[] tournament) {
        String answer=""; int cur = 0, c = 0, N = tournament.length;
        for (int i=0; i<N; ++i) for (int j=0; j<i; ++j, ++c) {
            cur = 3*cur + tournament[i].charAt(j) - 60;
            if (c % 4 == 3) { answer += (char)(cur+33); cur = 0; }
        }
        if (c % 4 != 0) { while (c % 4 != 0) { cur = 3*cur; ++c; } answer += (char)(cur+33); }
        return answer;
    }

/* C++ */
    string compress(vector<string> tournament) {
        string answer=""; char cur = 0; int c = 0, N = tournament.size();
        for (int i=0; i<N; ++i) for (int j=0; j<i; ++j, ++c) {
            cur = 3*cur + tournament[i][j] - 60;
            if (c % 4 == 3) { answer += cur+33; cur = 0; }
        }
        if (c % 4) { while (c % 4) { cur = 3*cur; ++c; } answer += cur+33; }
        return answer;
    }

/* High-level pseudocode */
    - concatenate the rows of the lower triangular half of the tournament matrix
    - interpret <, =, > as ternary digits 0, 1, 2
    - append 0 until you have a number of characters divisible by four
    - encode each group of four as a character from [33, 33+3^4).