Recognizing a Lattice of Symbols¶
Estimated time limit: 2 seconds. Memory limit: 128 MB.
The actual time limit is twice the slowest-case median runtime of the reference solution on the target judge, rounded up to a multiple of \(0.5\) seconds. See the benchmark environment.
Story¶
A directory allows several symbols to name one object and uses a relation table to describe an order among objects. Determine whether the table can represent a lattice exactly.
(This story was rewritten by GPT-6.)
Formal Problem Statement¶
A partial order \(\le\) is reflexive, antisymmetric, and transitive: \(x\le x\) ; if \(x\le y\) and \(y\le x\) , then \(x=y\) ; if \(x\le y\) and \(y\le z\) , then \(x\le z\) .
An upper bound \(u\) of \(x,y\) satisfies \(x\le u\) and \(y\le u\) . An upper bound that is at most every other upper bound is their least upper bound, or join. Lower bounds and the greatest lower bound, or meet, reverse these comparisons. A nonempty partially ordered set is a lattice if every pair has both a join and a meet.
Symbols are different from elements: several symbols may represent the same element. Let \(f\) map each symbol to one element, with every element represented by at least one symbol. A symbol relation represents the partial order when a relation between symbols \(i,j\) exists exactly when \(f(i)\le f(j)\) . The element set and the mapping \(f\) may be chosen; they are not supplied as input.
You are given \(n\) symbols and an \(n\times n\) matrix \(A\) . Entry \(A_{i,j}=1\) means relation \((i,j)\) exists; zero means it does not. Decide whether there are an element set, a surjection \(f\) , and a lattice on that set such that
The matrix cannot be changed and no symbol can be omitted. Several symbols may represent one element, so relations in both directions between distinct symbols are not necessarily invalid.
Input Format¶
The first line contains the test-case count \(T\) . Each case begins with \(n\) , followed by \(n\) rows of \(n\) integers describing matrix \(A\) .
Output Format¶
Print Y for each matrix that can represent a lattice, or N otherwise, one character per line.
Samples¶
Sample 1¶
Input¶
5
6
1 1 1 1 1 1
0 1 0 1 1 1
0 0 1 1 1 1
0 0 0 1 0 1
0 0 0 0 1 1
0 0 0 0 0 1
5
1 1 1 1 1
0 1 0 0 1
0 0 1 0 1
0 0 0 1 1
0 0 0 0 1
5
0 1 1 1 1
0 1 0 0 1
0 0 1 0 1
0 0 0 1 1
0 0 0 0 1
5
1 1 0 1 1
0 1 0 0 1
0 0 1 1 1
0 0 0 1 1
0 0 0 0 1
5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
Output¶
N
Y
N
N
Y
Sample 2¶
Input¶
3
1
0
1
1
2
1 1
1 1
Output¶
N
Y
Y
Sample Explanation¶
The second case of the first sample has a minimum, three incomparable middle elements, and a maximum, forming a lattice. Its third case lacks a reflexive relation and is invalid. Its fifth case has every relation present; all symbols can represent one element, making it valid.
This separate diagram gives an invalid partial order: a lower element is below a higher one when an upward path connects them. The minimal upper bounds \(u,v\) of \(a,b\) are incomparable, so neither is below every upper bound.
Constraints and Guarantees¶
Each case satisfies \(1\le n\le50\) and \(A_{i,j}\in\{0,1\}\) . The sum of \(n\) over the input file is at most \(50000\) .
| Score share | Additional conditions |
|---|---|
| 100% | None |