GitHub 源文件 Markdown 中文

Recognizing a Lattice of Symbols: Alternative Solution

All joins and a minimum

This criterion comes from the problem setter. Codex (GPT-6) organized the C++17 program and supplied the finite-lattice proof. See alternative.cpp; the main solution explains symbol classes and the join scan.

Check reflexivity, transitivity, and a join for every pair of symbols. Then find an all-one row, representing an element at most every other element. Print Y exactly when these conditions hold; no pairwise meet scan is needed.

In a nonempty finite lattice, successively taking the meet of all elements gives a global minimum. Binary joins also exist, so the conditions are necessary.

Conversely, work in the finite partial order of symbol classes and consider any \(x,y\) . Their common lower bounds form a nonempty set because it contains the minimum. Successively join all these lower bounds. Each intermediate result remains at most both \(x\) and \(y\) : they are common upper bounds of the elements being joined, and a join is below every common upper bound. The final result is a common lower bound above every common lower bound, hence the meet. Thus every meet exists and the order is a lattice. Finiteness and the nonempty lower-bound set are both essential here.

Join checking takes \(O(n^3)\) and finding an all-one row takes \(O(n^2)\) . Total time is \(O(n^3)\) with \(O(n^2)\) space. Removing the dual pairwise scan reduces the work and was faster in the measurements, without changing the asymptotic bound.