[Problem proposal] Unionfind with Potential

[Misuki743]

Problem name: Unionfind with Potential

Problem

Given a graph with $N$ vertices and $0$ edges, each vertex have some weight $w_v$ on it. Process the following $Q$ queries in order:

• $t_i = 0 \text{ } u_i \text{ } v_i \text{ } d_i$: Add an edge $(u_i, v_i)$ with constraint $w_{v_i} - w_{u_i} = d_i$
• $t_i = 1 \text{ } u_i \text{ } v_i$: Print $w_{v_i} - w_{u_i}$

Solution

Maintain difference of $w_v$ and $w_{p_v}$ in Unionfind.

Constraint

• $2 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• The graph is a forest at any time
• $u_i, v_i$ in query of type 2 would belong to same connect component at that time

Note / Disucussion

• Do we need to consider something more general instead of $w_{v_i} - w_{u_i}$?
• Do we need to consider the case where edges may form cycles and report when contradiction happen?

[maspypy]

Thank you!
Since this data structure can handle groups (not limited to commutative groups), I want to deal with non-commutative groups.
Here are some examples of the types of problems we can consider:

Each vertex has values $(x[0], \ldots, x[N-1])$. These values are unknown.

[Query 1]
Given $(u, v, a, b)$, where $a \neq 0$.
This means the information $x[v] = a x[u] + b \pmod{998244353}$.
This information is valid if it does not contradict any previously valid information.
Output whether this information is valid or invalid.

[Query 2]
Given (u, v, x). Based on the previously valid information and assuming x[u] = x, determine x[v] or print -1 if it can't be determined.

[Misuki743]

Seems nice, but to compute the inverse of affine would require computation of modulo inverse, which would make the time complexity increase from $O(q \alpha(n))$ to $O(q (\alpha(n) + \lg \text{mod}))$, maybe it's better to find a way to avoid extra cost not from the data structure itself? For example, change to another non-commutative group whose inverse won't be that costly, or just gives affine and its inverse in the input?

[lrvideckis]

this problem already exists here https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B if you want to test your library on it

[maspypy]

The problem I proposed was flawed. The fact that a cycle was formed where the composition is not the identity map only determines the values at the vertices of the cycle and does not necessarily indicate a contradiction.
It might be better to associate the group elements directly with the vertices. A (2,2) matrix might be easier for the general user to understand than an affine transformation.

[maspypy]

I would like to propose assigning invertible (2,2) matrices to vertices and edges.

Finding the inverse of all matrices can be done in $O(\log mod + N)$ time, and since the computational complexity can also be measured by the unionfind problem, I think we don't need to worry about the execution time for finding inverses.

On the other hand, in competitive programming problems, I think groups are often commutative groups or sets of affine transformations in the form of $\pm x + a$, so it may be appropriate to include conventional addition problems as originally proposed.

Furthermore, even if there are problems similar to those on AOJ, it would be fine to place useful problems all in the Library Checker.

[Misuki743]

So if I understand correctly, entry of matrix on vertices would be some variable while entry of matrix on edges would be some constant?

[maspypy]

Yes

[maspypy]

Problem 1

未知の整数列 $(a_0, \ldots, a_{n-1})$ がある．$Q$ クエリを処理せよ.

0 u v x：列 $a$ に関して $a[u]=a[v]+x$ であるという情報が与えられる.
この情報が valid であるとは，これまでの valid な情報に矛盾しないことを意味する.
この情報が valid であるか否かを出力せよ.

1 u v：これまでの valid な情報をもとに $a[u]-a[v]$ が定まるならばその値，定まらないならば -1 を出力せよ．

Problem 2

$2\times 2$ 可逆行列からなる未知の列 $(a_0, \ldots, a_{n-1})$ がある．$Q$ クエリを処理せよ.

0 u v x_{00} x_{01} x_{10} x_{11}：列 $a$ に関して $a[u]=a[v]x$ であるという情報が与えられる.
この情報が valid であるとは，これまでの valid な情報に矛盾しないことを意味する.
この情報が valid であるか否かを出力せよ.

1 u v：これまでの valid な情報をもとに $a[x]^{-1}a[u]$ が定まるならばその値，定まらないならば -1 を出力せよ．

---

Problem 1

There is an unknown sequence of integers $(a_0, \ldots, a_{n-1})$, process $Q$ queries.

0 u v x: You are provided with information that $a[u]=a[v]+x$. Determine if this information is valid, meaning it does not contradict any previously given valid information. Output whether this information is valid or not.

1 u v: Based on the valid information provided so far, output the value of $a[u]-a[v]$ if it can be determined; otherwise, output -1.

Problem 2

There is an unknown sequence of $2\times 2$ invertible matrices $(a_0, \ldots, a_{n-1})$, process $Q$ queries.

0 u v x_{00} x_{01} x_{10} x_{11}: You are provided with information that $a[u]=a[v]x$, where $x$ is a $2\times 2$ matrix with elements $x_{00}, x_{01}, x_{10}, x_{11}$. Determine if this information is valid, meaning it does not contradict any previously given valid information. Output whether this information is valid or not.

1 u v: Based on the valid information provided so far, output the value of $a[v]^{-1}a[u]$ if it can be determined; otherwise, output -1.

[Misuki743]

I think I can prepare them

[maspypy]

Thank you, and I appreciate your help. If you have any questions about the preparations, please feel free to ask.

[Misuki743]

how should we naming these two problem? I was thinking using

• Unionfind with Potential (commutative group)
• Unionfind with Potential (non-commutative group)

or maybe specify which group are used in (...)? In such case, what should it be? (I'm not very familiar with abstract algebra)

[maspypy]

How about
Unionfind with Potential
Unionfind with Potential (non-commutative group)

[maspypy]

If you want to avoid calculating the inverse, you can include the constraint $x_{00} x_{11} - x_{01} x_{10} \equiv 1 \pmod{998244353}$.