C - Perfect Standings Editorial by en_translator
This problem can be divided into the following two steps:
- Obtain the names and scores of all participants.
- Rearrange them by their ranks.
Both steps have several different approaches.
1. Obtain the names and scores of all participants
The easiest way for the former part is simply writing the scores and names of the \(31\) people explicitly:
Sample code (C++)
vector<pair<int, string>> standings{
{a, "A"},
{b, "B"},
{c, "C"},
{d, "D"},
{e, "E"},
{a + b, "AB"},
{a + c, "AC"},
{a + d, "AD"},
{a + e, "AE"},
{b + c, "BC"},
{b + d, "BD"},
{b + e, "BE"},
{c + d, "CD"},
{c + e, "CE"},
{d + e, "DE"},
{a + b + c, "ABC"},
{a + b + d, "ABD"},
{a + b + e, "ABE"},
{a + c + d, "ACD"},
{a + c + e, "ACE"},
{a + d + e, "ADE"},
{b + c + d, "BCD"},
{b + c + e, "BCE"},
{b + d + e, "BDE"},
{c + d + e, "CDE"},
{a + b + c + d, "ABCD"},
{a + b + c + e, "ABCE"},
{a + b + d + e, "ABDE"},
{a + c + d + e, "ACDE"},
{b + c + d + e, "BCDE"},
{a + b + c + d + e, "ABCDE"}
};
Sample code (Python)
standings = [
(a, "A"),
(b, "B"),
(c, "C"),
(d, "D"),
(e, "E"),
(a + b, "AB"),
(a + c, "AC"),
(b + c, "BC"),
(a + d, "AD"),
(b + d, "BD"),
(c + d, "CD"),
(a + e, "AE"),
(b + e, "BE"),
(c + e, "CE"),
(d + e, "DE"),
(a + b + c, "ABC"),
(a + b + d, "ABD"),
(a + c + d, "ACD"),
(b + c + d, "BCD"),
(a + b + e, "ABE"),
(a + c + e, "ACE"),
(b + c + e, "BCE"),
(a + d + e, "ADE"),
(b + d + e, "BDE"),
(c + d + e, "CDE"),
(a + b + c + d, "ABCD"),
(a + b + c + e, "ABCE"),
(a + b + d + e, "ABDE"),
(a + c + d + e, "ACDE"),
(b + c + d + e, "BCDE"),
(a + b + c + d + e, "ABCDE"),
]
This approach is prone to bugs, such as finding a wrong score for only one person, and requires a long code two.
The code length can be reduced by the technique of corresponding subsets to integers.
A size-\(N\) set \(S=\lbrace s _ 0,s _ 1,\dotsc,s _ {N-1}\rbrace\) has \(2 ^ N\) subsets, which can be corresponded to integers between \(0\) and \(2 ^ N-1\) as follows:
- For each integer \(i\) between \(0\) and \(N-1\), the subset \(X\) of \(S\) corresponding to an integer \(x\) contains an element \(s _ i\) if and only if the \(2 ^ i\)s place of the binary representation of \(x\) is \(1\).
For example in our problem, the binary representation of \(1\) is 00001, so it corresponds to \(\lbrace A\rbrace\); the binary representation of \(10\) is 01010, so it corresponds to \(\lbrace B,D\rbrace\).
This way, each participant can be corresponded to an integer between \(1\) and \(31\), and the necessary values can be obtained based on this correspondence.
If you use this method, it would be convenient to get the score of problem \(i\) \((1\leq i\leq5)\) for a given integer \(i\), so it is recommended to use a length-\(5\) array instead of using \(5\) variables.
Sample code (C++)
vector<pair<int, string>> standings;
for (int bit = 1; bit < 32; ++bit) {
int solved_point = 0;
string name = "";
for (int digit = 0; digit < 5; ++digit)
// Those with standing bit at the digit-th least significant bit solved the digit-th problem.
if (bit & 1 << digit) {
// Add the problem to the name and the score.
solved_point += point[digit];
name += "ABCDE"[digit];
}
// Insert the information of scores and names
standings.emplace_back(solved_point, name);
}
Sample code (Python)
standings = []
for bit in range(1, 32):
solved_point = 0
name = ""
for digit in range(5):
# Those with standing bit at the digit-th least significant bit solved the digit-th problem.
if bit & 1 << digit:
# Add the problem to the name and the score.
solved_point += point[digit]
name += "ABCDE"[digit]
# Insert the information of scores and names
standings.append((solved_point, name))
Rearrange by their ranks
You can use a function that rearranges (sorts) a sequence in a particular order equipped in many languages. However, this time we need to sort them in descending order of their scores (higher to lower), with ties broken in ascending order of their names (smaller to larger). There are several ways to achieve this.
If your language supports lexicographical comparison of tuples (a few values put together) as a standard feature, one can multiply all the scores by \(-1\) so that we can just sort them in ascending order.
Sample code (C++)
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <ranges>
using namespace std;
int main() {
array<int, 5> point{};
for (auto&& p : point)
cin >> p;
// Multiply the scores by -1 for sorting
for (auto&& p : point)
p *= -1;
// Information of all participants' scores and names
vector<pair<int, string>> standings;
for (int bit = 1; bit < 32; ++bit) {
int solved_point = 0;
string name = "";
for (int digit = 0; digit < 5; ++digit)
// Those with standing bit at the digit-th least significant bit solved the digit-th problem.
if (bit & 1 << digit) {
solved_point += point[digit];
name += "ABCDE"[digit];
}
// Insert the information of scores and names
standings.emplace_back(solved_point, name);
}
// Sort in ascending order
ranges::sort(standings);
// Print their names in order
for (const auto& name : standings | views::values)
cout << name << endl;
return 0;
}
Sample code (Python)
point = list(map(int, input().split()))
# Multiply the scores by -1 for sorting
point = [-p for p in point]
standings = []
for bit in range(1, 32):
solved_point = 0
name = ""
for digit in range(5):
# Those with standing bit at the digit-th least significant bit solved the digit-th problem.
if bit & 1 << digit:
# Add the problem to the name and the score.
solved_point += point[digit]
name += "ABCDE"[digit]
# Insert the information of scores and names
standings.append((solved_point, name))
# sort their names and print their names in ascending order
for _, name in sorted(standings):
print(name)
If the standard library of your language supports stable sort, and is capable of specifying which element of a tuple should be used as the criteria of sorting, you can sort them in your desired order as follows:
- Perform a sort them in ascending order of their names.
- Perform a stable sort them in descending order of their scores.
If your language only supports sorting in ascending order (or is difficult to sort in descending order), you may also write as follows.
- Perform a sort them in ascending order of their names.
- Reverse the sequence.
- Perform a stable sort them in ascending order of their scores.
- Reverse the sequence.
Sample code (C++)
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <ranges>
using namespace std;
int main() {
array<int, 5> point{};
for (auto&& p : point)
cin >> p;
// Information of all participant's scores nad names
vector<pair<int, string>> standings;
for (int bit = 1; bit < 32; ++bit) {
int solved_point = 0;
string name = "";
for (int digit = 0; digit < 5; ++digit)
// Those with standing bit at the digit-th least significant bit solved the digit-th problem.
if (bit & 1 << digit) {
// Add the problem to the name and the score.
solved_point += point[digit];
name += "ABCDE"[digit];
}
// Insert the information of scores and names
standings.emplace_back(solved_point, name);
}
// Sort in ascending order of their names
ranges::sort(standings, less{}, &pair<int, string>::second);
// Sort in descending order of their scores
ranges::stable_sort(standings, greater{}, &pair<int, string>::first);
// Print their names in order
for (const auto& name : standings | views::values)
cout << name << endl;
return 0;
}
Sample code (Python)
from operator import itemgetter
point = list(map(int, input().split()))
standings = []
for bit in range(1, 32):
solved_point = 0
name = ""
for digit in range(5):
# Those with standing bit at the digit-th least significant bit solved the digit-th problem.
if bit & 1 << digit:
# Add the problem to the name and the score.
solved_point += point[digit]
name += "ABCDE"[digit]
# Insert the information of scores and names
standings.append((solved_point, name))
# Sort them in ascending order of their names
standings.sort(key=itemgetter(1))
# Reverse the list
standings.reverse()
# Sort them in ascending order of their scores
standings.sort(key=itemgetter(0))
# Reverse the list
standings.reverse()
# Print their names in order
for _, name in standings:
print(name)
If your language accepts a comparison function (specifying what order to sort), you may use that too. (We omit sample code.)
posted:
last update: