[HNOI 2019] Tour

Difficulty Ratings

Idea Creativity: 3/5
Techniques Used: 2/5
Implementation : 2/5

Problem Link

Link (Simplified Chinese) by matthew99 afaik

Simplified Statement

Given an undirected graph with $N$ vertices and $M$ edges, where each edge has a label of either $0$ or $1$. Answer $Q$ queries of the following form: given $x,y$, determine whether there exist a path (not necessarily wihtout cycles) from $x$ to $y$ such that if we concatenate the labels along the path, we can obtain a palindrome. $N \le 5000, M \le 500000, Q\le 100000$.

Solution

First we try to figure out a solution with polynomial complexity. Consider we create a new graph where each node is a pair of ordered indices $(u,v)$, and we add a special node $S$. We create a directed edge $(u,v) \rightarrow (p,q)$ if there exists edges $u-p$ and $v-q$, and they have the same label. Also, we create edges $S\rightarrow (u,u)$, and $S\rightarrow (u,v)$ if $u$ and $v$ is connected by an edge. We have created a new graph with $O(N^2)$ vertices and $O(M^2)$ edges. It is easy to see that if there exists a palindrome path between $x$ and $y$, then $(x,y)$ is reachable from $S$. Therefore, we can run a bfs and answer queries in $O(1)$. The complexity is $O(M^2+Q)$, which would get 30% of the points.

It turns out that we can improve the about solution slightly, through some little tricks. We add another label to the nodes so it becomes $(u,v,w)$, where $w$ is $0,1$ or $2$. We create edges $(u,v,2)\rightarrow (p,v,$label of edge $u-p)$. We also create edges $(p,v,$label of $v-q)\rightarrow (p,q,2)$. Similar as above, we also create edges $S\rightarrow (u,u,2)$ and $S\rightarrow (u,v,2)$. Now, there exists palindrome path between $x,y$ if and only if $(x,y,2)$ is reachable from $S$. In this model, we created $O(N^2)$ vertices and $O(NM)$ edges, so the complexity is $O(NM+Q)$, which would get 70% of the points.

We need another idea to optimize the solution. It turns out that we can reduce $M$ into $O(N)$ range. To do this, imagine that $x$ and $y$ are people walking on the path simutaenouly at same speed. Lets consider that $x$ walked $k$ edges with label 0 to reach $u$, and $y$, at the same time, walked $k$ edges to reach $v$. What if $x$ chooses another path that needs $k+8$ edges instead? Then, $y$ can walk back and forth on the same edge to "wait" for $x$. Therefore, we noticed that we only need to see whether or not we can reach $x$ to $p$ using odd or even number of edges of the each label. Back to solving the problem. Consider only edges of label 0. Find a spanning tree for each connected component. Then, if that component has an odd cycle, we add a self-loop to one of its nodes, otherwise the component is bipartite and we don't need to add self-loop. Now, keep only the spanning trees and self-loop. Do the same for edges with label 1. We noticed that there exists palindrome path in new graph if and only if there exists palindrome path in original graph. However, there are only $O(N)$ edges in the new graph. Therefore, we can run $O(M^2)$ solution on new graph and the complexity would be $O(N^2+Q)$, which can get AC.

Intuitions

In this kind of problems about finding a path in a general graph, usually it is about creating a new graph with new sets of nodes. After getting the $O(M^2)$ solution, we realise that iterating two edges at a time is slow, so we split the edge $(u,v)\rightarrow(p,q)$ into $(u,v,2)\rightarrow(p,v,w)\rightarrow(p,q,2)$ so that we only have to iterate one edge each time. For full solution, these kind of problems where $M$ is big and $N$ is small uses time trick of removing useless edges sometimes(and bitset otherwise...). See TIOJ 2050, for the hardest problem of this setting. We try to restrict our path into certain pattern, proving that if some path exist, a path of this kind must exist (similar to greedy). I failed to solve this problem on my own, gamegame is so unskillful.