Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

Find odd length path between two nodes in undirected graph (multiple queries)
Difference between en4 and en5, changed 407 character(s)
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 have no clu'm not sure about how to do it. I'm guessing that probably it's not it shouldn't be necessary to find a specific path, because as long as the path has an odd length the final result does not depend of the exact path taken.will not depend on the exact path taken. Maybe precomputing partial sums and combining them using LCA somehow or something like that could work, I cannot see how to exactly do the combination.↵

Any help will be deeply appreciated :)↵

Thanks in advance

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English pabloskimg 2017-10-23 06:40:22 66
en5 English pabloskimg 2017-10-23 06:35:31 407
en4 English pabloskimg 2017-10-23 02:25:23 69
en3 English pabloskimg 2017-10-21 19:12:04 4 Tiny change: 'pagate to whole con' -> 'pagate to the whole con'
en2 English pabloskimg 2017-10-21 19:07:20 1
en1 English pabloskimg 2017-10-21 19:05:43 2279 Initial revision (published)