この問題は、以下のように言い換えられます。

\(N - 1\) 枚のカードがあり、 \(i\) 番目のカードの表面には数 \(|A_i - A_{i+1}|\) が、裏面には数 \(|A_i + A_{i+1}|\) が書かれている。はじめ、全てのカードは全て表面を向いている。 \(2\) 枚以下のカードを選び、選んだカードを全てひっくり返すという操作を何度でも行えるとき、カードが向ける数字が全て相異なるようにするには最小で何回の操作が必要か？

この問題をさらに次のように言い換えます。

\(2 \cdot 10^9 + 1\) 頂点 \(N-1\) 辺からなる有向グラフがある。頂点には番号が \(0, 1, \ldots, 2 \cdot 10^9\) と振られており、各 \(i \, (1 \leq i \leq N-1)\) について、頂点 \(|A_i + A_{i+1}|\) から頂点 \(|A_i - A_{i+1}|\) に有向辺が張られている。ある辺を選び向きを変える、という操作を行い、各頂点の入次数を \(1\) 以下にすることを考える。操作の最小回数を \(k\) とするとき、 \(\lfloor \frac{k+1}{2} \rfloor\) を答えよ。

各辺を無向辺だとみなして、連結成分ごとに解くことにしましょう。

\(V\) 頂点 \(V-1\) 辺の場合

辺を無向とみなすと、グラフは木になります。 \(1\) 頂点のみ入次数が \(0\) になる頂点があるので、それを全方位木 DP を用いて探索することで、答えが求まります。

\(V\) 頂点 \(V\) 辺の場合

辺を無向とみなすと、グラフには閉路が \(1\) つだけ存在し、それを潰して \(1\) つの頂点にすると木になることが知られています。閉路の中では向きの付け方は \(2\) 通りしかなく、閉路の外の辺は向きづけは \(1\) 通りに定まるので、両方の向きづけを試すことで答えが求まります。

\(V\) 頂点 \(E \, (E > V)\) 辺の場合

このようなグラフが存在する場合、各頂点の入次数を \(1\) 以下にすることが不可能です。

このような場合分けを行うことで解くことができます。なお、実際には \(2 \cdot 10^9 + 1\) 頂点を保持すると実行時間制限に間に合わないため、座標圧縮と呼ばれる方法で頂点数を減らすことになります。