iamcheater   1년 전

This code is wrong under its own approach, and that failure exposes a misconfiguration in the problem. The solver doubles all values (w = 2z), builds a twin-node graph (each variable v has v and v'), encodes every equality x+y=z as difference constraints so that along any edge u → v (w) we enforce P[v] = P[u] − w, and runs BFS to assign a potential P[·] per connected component, defined only up to an additive constant in that component. For a query x+y, it outputs an answer only when x and y' lie in the same component, using the invariant 2(x+y) = P[x] − P[y']. If they are in different components, it never answers.

That policy is exactly where the solution becomes incorrect with respect to many test datasets. Distinct components can be independently anchored (their additive constants become fixed) by internal constraints, e.g., a+a=2 forces a=1; more generally, odd cycles or self-links fix a component’s absolute offset. Once two components are both anchored, a cross-component sum like a+c is logically determined. The code still withholds it because it refuses to combine components. Minimal example: with a+a=2 and c+c=4, we have a=1 and c=2, so a+c=3 is determined, yet the code prints nothing since a and c' are in different components. Hence it produces false negatives.

Everything else in the implementation is reasonable: doubling correctly handles half-integers, BFS propagation is linear time, and no contradiction check is required under the statement’s consistency promise. The failure is not a low-level bug but a specification-interpretation choice: the solver adopts a purely local notion of “checkable,” while the judge data appears to expect global reasoning that allows cross-component sums once each component is anchored.

This leads to the conclusion that the problem itself is misconfigured. The statement never formalizes “checkable” (must an answer hold in all satisfying assignments?), nor does it say whether cross-component sums are allowed when components are independently fixed. The official tags (“Graph Theory / Graph Traversal / BFS”) guide solvers toward exactly the local BFS model implemented here, yet the tests seem to require cross-component aggregation, which is a different solving regime. Without a precise definition of “checkable,” explicit guidance on cross-component sums, and an acknowledgement that variables may be half-integers even though reported sums are integers, a BFS-only, component-local solution like this one is judged wrong for omissions the statement does not forbid.

댓글을 작성하려면 로그인해야 합니다.