Editorial for DMOPC '19 Contest 1 P3 - Simple Math


Remember to use this editorial only when stuck, and not to 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.

Author: KevinWan

For subtask 1, it suffices to check every possible combination of values for the x_i against the M given equations.

Time complexity: \mathcal{O}(K^NM)

For subtasks 2 and 3, we will represent our set of equations as a graph, where each node represents one of the N variables, and each equation is represented by an edge with a "weight" of c_i, connecting nodes a_i, and b_i. 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, v, and solve for the variables in the component in terms of v. We can do this with either BFS or DFS. Each variable can thus have a solution in the form of a+v or a-v. For each of these, we have 1\leq x_i\leq K which places a new restriction on the possible value for v. If a variable has two different representations, we can try to solve for v which either limits the value of v to only 0 or 1 values depending on whether or not there was a contradiction. The number of solutions for this component is thus the number of values of v 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: \mathcal{O}(N+M)


Comments

There are no comments at the moment.