Soluție HackerRank pentru Introduction to Algebra, subdomeniul Algebra, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Introduction to Algebra
- Domeniu: Algebra
- Limbaj: C++14
Challenge: Introduction to Algebra
Subdomeniu: Algebra (algebra)
Scor cont: 100.0 / 100
Submission status: Accepted
Submission score: 1.0
Submission ID: 464814960
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/introduction-to-algebra/problem
Cerință
Welcome to Sevenkplus' perfect math class! In this class we will study an algebraic structure called magma.
A magma is a nonempty set M equipped with a binary operation bigodot : M× Mto M. We write xbigodot y for the application of the operator on the two elements x,yin M.
Note that there are no restrictions on the binary operation. For example, we cannot assume that (xbigodot y)bigodot z=xbigodot (ybigodot z) always holds.
There are many different types of magmas. Some are interesting, others are even more interesting. Studying specific types of magmas is an important part of mathematics.
Below we introduce the following types of magmas.
A quasigroup is a magma such that for all x,yin M, there exists a unique zin M such that xbigodot z=y and a unique win M such that wbigodot x=y.
A loop is a quasigroup such that there is a unique element ein M such that for all xin M, ebigodot x=xbigodot e=x.
A semigroup is a magma such that for all x,y,zin M, we have (xbigodot y)bigodot z=xbigodot(ybigodot z).
A monoid is a semigroup such that there is a uniqe element ein M such that for all xin M, ebigodot x=xbigodot e=x.
A group is a monoid such that for all xin M, there exists yin M such that xbigodot y=ybigodot x=e.
An abelian group is a group such that for all x,yin M, we have xbigodot y=ybigodot x.
A rack is a magma such that (1) for all x,y,zin M, we have xbigodot (ybigodot z)=(xbigodot y)bigodot(xbigodot z) and (2) for all x,yin M, there exists a unique zin M such that xbigodot z=y.
A quandle is a rack such that for all xin M, we have xbigodot x=x.
In this problem, you are given several magmas. You have to tell us what types they are.
Input Format
The first line is a integer T, the number of magmas given to you.
Following are T magmas.
For each magma, the first line is an integer n, the size of the set M. (Yes, you only need to consider finite algebraic structures here, which greatly simplifies the problem.)
Without loss of generality, we assume that M={0,1,…,n-1}.
Following are n lines. Each line contains n space-separated integers. The j-th number on the i-th line is (i-1)bigodot (j-1) where bigodot is the binary operation of the magma.
Constraints
1 ≤ T≤ 60
1≤ n≤ 110.
Output Format
For each magma, output one line, which is the magic number of the magma (denoted by S henceforth).
The magic number S of a magma is defined as:
* Initially, let S=0.
* If the magma is a quasigroup, add 1 to S.
* If the magma is a loop, add 2 to S.
* If the magma is a semigroup, add 4 to S.
* If the magma is a monoid, add 8 to S.
* If the magma is a group, add 16 to S.
* If the magma is an abelian group, add 32 to S.
* If the magma is a rack, add 64 to S.
* If the magma is a quandle, add 128 to S.
* Then S is the magic number of the magma.
Cod sursă
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<vector<int>> op(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> op[i][j];
}
}
auto inRange = [&](int v) { return 0 <= v && v < n; };
bool rowBij = true, colBij = true;
{
vector<int> seen(n);
for (int i = 0; i < n && rowBij; ++i) {
fill(seen.begin(), seen.end(), 0);
for (int j = 0; j < n; ++j) {
int v = op[i][j];
if (!inRange(v) || ++seen[v] != 1) {
rowBij = false;
break;
}
}
}
for (int j = 0; j < n && colBij; ++j) {
fill(seen.begin(), seen.end(), 0);
for (int i = 0; i < n; ++i) {
int v = op[i][j];
if (!inRange(v) || ++seen[v] != 1) {
colBij = false;
break;
}
}
}
}
bool quasigroup = rowBij && colBij;
int identity = -1;
int cntId = 0;
for (int e = 0; e < n; ++e) {
bool ok = true;
for (int x = 0; x < n; ++x) {
if (op[e][x] != x || op[x][e] != x) {
ok = false;
break;
}
}
if (ok) {
identity = e;
++cntId;
}
}
bool hasUniqueId = (cntId == 1);
bool loop = quasigroup && hasUniqueId;
bool semigroup = true;
for (int x = 0; x < n && semigroup; ++x) {
for (int y = 0; y < n && semigroup; ++y) {
int xy = op[x][y];
if (!inRange(xy)) {
semigroup = false;
break;
}
for (int z = 0; z < n; ++z) {
int yz = op[y][z];
if (!inRange(yz)) {
semigroup = false;
break;
}
int lhs = op[xy][z];
int rhs = op[x][yz];
if (!inRange(lhs) || !inRange(rhs) || lhs != rhs) {
semigroup = false;
break;
}
}
}
}
bool monoid = semigroup && hasUniqueId;
bool group = false;
if (monoid) {
group = true;
int e = identity;
for (int x = 0; x < n && group; ++x) {
bool found = false;
for (int y = 0; y < n; ++y) {
if (op[x][y] == e && op[y][x] == e) {
found = true;
break;
}
}
if (!found) group = false;
}
}
bool abelian = false;
if (group) {
abelian = true;
for (int x = 0; x < n && abelian; ++x) {
for (int y = 0; y < n; ++y) {
if (op[x][y] != op[y][x]) {
abelian = false;
break;
}
}
}
}
bool rack = false;
{
bool leftDistributive = true;
for (int x = 0; x < n && leftDistributive; ++x) {
for (int y = 0; y < n && leftDistributive; ++y) {
int xy = op[x][y];
if (!inRange(xy)) {
leftDistributive = false;
break;
}
for (int z = 0; z < n; ++z) {
int yz = op[y][z];
int xz = op[x][z];
if (!inRange(yz) || !inRange(xz)) {
leftDistributive = false;
break;
}
int lhs = op[x][yz];
int rhs = op[xy][xz];
if (!inRange(lhs) || !inRange(rhs) || lhs != rhs) {
leftDistributive = false;
break;
}
}
}
}
// condition (2): for all x,y exists unique z with x*z=y <=> each row is a permutation
rack = leftDistributive && rowBij;
}
bool quandle = false;
if (rack) {
quandle = true;
for (int x = 0; x < n; ++x) {
if (op[x][x] != x) {
quandle = false;
break;
}
}
}
int S = 0;
if (quasigroup) S += 1;
if (loop) S += 2;
if (semigroup) S += 4;
if (monoid) S += 8;
if (group) S += 16;
if (abelian) S += 32;
if (rack) S += 64;
if (quandle) S += 128;
cout << S << '\n';
}
return 0;
}