I'm trying to solve the following problem (Electrical Pollution): https://www.urionlinejudge.com.br/judge/en/problems/view/1334 (please read the problem statement). So basically we are given many 2 variable (x + y = c) and 1 variable (x = c) linear equations, i.e measurements, and then we are given multiple 2 variable (w + z = ?) and 1 variable (w = ?) queries and we have to either give the exact result if the answer can be inferred from the previous measurements, or * otherwise.
My idea is to build a graph where the nodes are the variables and the edges are the 2-variable equations connecting them.
1) As a first step, we already know the values of the variables in the 1-variable measurements, and starting from them we can propagate and infer the values of all the other variables connected with BFS over the graph.
2) As a second step, we can solve equation systems with an odd number of equations where there are the same number of equations and variables. Basically we can run DFS, find loops (backward edges), if the loop has an odd length then we can easily solve the equation system of the edges in that loop (say, we solve for the first variable in the loop) and then we propagate to the whole connected component with BFS (as in 1).
3) It turns out that 1) and 2) are not enough, because it's not necessary to know the exact values of both variables to be able to know the value of their sum. In fact, given a 2-variable query (x + y = ?), if we can find a path (not necessarily a loop) of odd length, and if we enumerate the measurements along that path with 1, 2, 3, ..., n, then we can solve the equation (x + y = ?) by adding the measurements with odd index and subtracting the measurements with even index along that path. Moreover, any odd-length path would do the trick, because the final result will be the sum of the variables at both ends of the path, and variables in between just cancel each other (like a sort of telescoping sum http://mathworld.wolfram.com/TelescopingSum.html).
My question is basically about how to implement point 3). Right know I'm not sure about how to do it. I guess it shouldn't be necessary to find a specific path, because the final result will not depend on the exact path taken, just on the end points. Maybe precomputing partial sums and combining them using LCA somehow or something like that could work, but I cannot see how to exactly do the combination.
Any help will be deeply appreciated :)
Thanks in advance
Auto comment: topic has been updated by pabloskimg (previous revision, new revision, compare).
up
Auto comment: topic has been updated by pabloskimg (previous revision, new revision, compare).
Auto comment: topic has been updated by pabloskimg (previous revision, new revision, compare).
Hi. Yes, you can use LCA to solve it, so try to think that the graph is a tree (if there exist a cycle (even cycle), you can change it to a tree (running a dfs), since all the measurements are consistent, then you can find the answer). You can convince yourself that if with a cycle you can find the answer, in any tree of that cycle you can too.
Now we have a tree, so basically you need to find the sum from u to v, but not exactly the sum. if you have a path of odd length, you can find the value by subtracting the first and second equation and then sum the new equation with the third, and so on.. So you will have something like -+-+-+- So you need the sum of the path, but in that way, adding and subtracting. So you need the sum but starting with -. But how you guarantee that the sum that you have always started with — or with + ?. Well, you can decompose the path from u to v, in u->LCA(u, v) and v->LCA(u, v). So if you write down some examples you can notice that depending on if the sum from u, started with + or with -, you only need to negate the sum. And you will only have to negate one, or sum from u->LCA(a, b) or sum from v->LCA(a, b).
So you can use sparse tables to get LCA and sums. Also, you can have for each node if the sum started with + or with -.
Here is the implementation I did with a friend