Editorial for DMOPC '19 Contest 1 P3 - Simple Math
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
For subtask 1, it suffices to check every possible combination of values for the against the
given equations.
Time complexity:
For subtasks 2 and 3, we will represent our set of equations as a graph, where each node represents one of the variables, and each equation is represented by an edge with a "weight" of
, connecting nodes
, and
. Now, each connected component in our new graph represents a set of variables that are independent of each other. Thus the total number of solutions is the product of the number of solutions for each connected component. For each component, we can also see that if one variable was given a value, it forces a value on all the other variables in the component. We can thus pick an arbitrary variable,
, and solve for the variables in the component in terms of
. We can do this with either BFS or DFS. Each variable can thus have a solution in the form of
or
. For each of these, we have
which places a new restriction on the possible value for
. If a variable has two different representations, we can try to solve for
which either limits the value of
to only
or
values depending on whether or not there was a contradiction. The number of solutions for this component is thus the number of values of
that satisfy all the restrictions given by the component. The answer is simply the product of the number of values for each component.
Time complexity:
Comments