TournamentsAmbiguityNumber
SRM 365 · 2007-09-12 · by Xixas
SRM 365 · 2007-09-12 · by Xixas · Brute Force, String Parsing
Problem Statement
Problem Statement
In a chess tournament, each pair of distinct players played a single match against each other. Each match resulted in one of three outcomes: the first player won, the second player won, or there was a draw. The ambiguity number of the tournament is defined as the number of distinct triples of players (a, b, c) such that player a defeated b, player b defeated player c, and player c defeated player a.
You are given the results of all the matches as aString[] table. The j-th character of the i-th element of table is '1' (one) if player i defeated player j, '0' (zero) if player j defeated player i, or '-' if the match between players i and j resulted in a draw. Return the ambiguity number of the given tournament.
Constraints
- table will contain between 1 and 50 elements, inclusive.
- Each element of table will contain exactly n characters, where n is the number of elements in table.
- Each character in each element of table will be '1' (one), '0' (zero), or '-'.
- The i-th character of the j-th element of table will be '1' if and only if the j-th character of the i-th element of table is '0'.
- The i-th character of the j-th element of table will be '-' if and only if the j-th character of the i-th element of table is '-'.
- The i-th character of the i-th element of table will be '-'.
Examples
0)
{"-10",
"0-1",
"10-"}
Returns: 3
Player 0 defeated player 1, player 1 defeated player 2, and player 2 defeated player 0.
1)
{"----",
"----",
"----",
"----"}
Returns: 0
All matches ended in a draw.
2)
{"-1",
"0-"}
Returns: 0
Too few players to form a triple.
3)
{"--1-10-1---1--1-00",
"--0110000--0---10-",
"01--00000100-00011",
"-0---0010-11110100",
"001--01-00-0001-1-",
"11111--100--1-1-01",
"-1110--00110-11-01",
"0110-01--100110-10",
"-111111---01--0-01",
"--0-1100----10011-",
"--10--011--1--101-",
"01101-110-0--1-0-1",
"---010-0-0---00-11",
"--101-00-1-01-0-0-",
"0-110001110-11-110",
"-010-----011--0--0",
"11010110100-010--0",
"1-01-0010--00-111-"}
Returns: 198
4)
{"-1-", "0-0", "-1-"}
Returns: 0
Submissions are judged against all 52 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TournamentsAmbiguityNumber with a public method int scrutinizeTable(vector<string> table) · 52 test cases · 2 s / 256 MB per case