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
Cerinta
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\times M\to M$. We write $x\bigodot y$ for the application of the operator on the two elements $x,y\in M$.
Note that there are no restrictions on the binary operation. For example, we cannot assume that $(x\bigodot y)\bigodot z=x\bigodot (y\bigodot 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,y\in M$, there exists a unique $z\in M$ such that $x\bigodot z=y$ and a unique $w\in M$ such that $w\bigodot x=y$.
A **loop** is a quasigroup such that there is a unique element $e\in M$ such that for all $x\in M$, $e\bigodot x=x\bigodot e=x$.
A **semigroup** is a magma such that for all $x,y,z\in M$, we have $(x\bigodot y)\bigodot z=x\bigodot(y\bigodot z)$.
A **monoid** is a semigroup such that there is a uniqe element $e\in M$ such that for all $x\in M$, $e\bigodot x=x\bigodot e=x$.
A **group** is a monoid such that for all $x\in M$, there exists $y\in M$ such that $x\bigodot y=y\bigodot x=e$.
An **abelian group** is a group such that for all $x,y\in M$, we have $x\bigodot y=y\bigodot x$.
A **rack** is a magma such that (1) for all $x,y,z\in M$, we have $x\bigodot (y\bigodot z)=(x\bigodot y)\bigodot(x\bigodot z)$ and (2) for all $x,y\in M$, there exists a unique $z\in M$ such that $x\bigodot z=y$.
A **quandle** is a rack such that for all $x\in M$, we have $x\bigodot 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,\ldots,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 \le T\le 60$
$1\le n\le 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 sursa
#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;
}
HackerRank Algebra – Introduction to Algebra