Editorial for Bad Maths

Use this editorial only when stuck, and do not copy-paste code from it.

Please be respectful to the problem author and editorialist. Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Track each variable's value relative to a representative using a weighted DSU.

Store for every node $v$ a multiplier $r_v$ meaning "the value of $v$ equals $r_v$ times the value of its parent". Path compression multiplies these weights along the way. When adding $a \times b = c$ :

If $a$ and $b$ are already in the same component, check whether the implied product matches $c$ .
Otherwise link the two roots and set the new edge weight so the equation holds.

Inconsistent equations are rejected (No) and ignored afterwards. The whole pass is nearly linear in $n$ .

Solution (Python)

Code 1

class DisjointSet():

    def __init__(self) -> None:
        self.parent = dict[str,str]()
        self.relative_to_par = dict[str,int]()
        self.size = dict[str,int]()
        
    
    def make_set(self, v : str) -> None:
        if v not in self.parent:
            self.parent[v] = v
            self.size[v] = 1
            self.relative_to_par[v] = 1

    def find_set(self,v : str) -> tuple[str,int]:
        """
        Returns: (highest parent, value relative to that parent)
        """

        if (self.parent[v] == v): return (v,1)

        parent,value = self.find_set(self.parent[v])

        self.parent[v] = parent
        self.relative_to_par[v] = value * self.relative_to_par[v]

        return (self.parent[v], self.relative_to_par[v])
    
    def new_eq(self,v : str, u : str, val : int) -> bool:
        a, uval = self.find_set(v)
        b, vval = self.find_set(u)

        if a == b:
            # Checks if current values are consistent
            return uval * vval == val
        
        val *= uval * vval

        if (self.size[a] > self.size[b]):
            a,b = b,a

        self.parent[a] = b
        self.relative_to_par[a] = val
        self.size[b] += self.size[a]

        return True

n = int(input())

dsu = DisjointSet()

for _ in range(n):
    a,b,v = (x for x in input().split())
    v = int(v)

    dsu.make_set(a)
    dsu.make_set(b)

    print("Yes" if dsu.new_eq(a,b,v) else "No")

Comments0

No comments yet

Be the first to comment.

Editorial for Bad Maths

Approach

Solution (Python)

Comments0

New comment