โ† Back to posts

What is This Weird Parallel Binary Search Problem

5 min read
Competitive Programming

Prerequisites

If you don't understand any of these topics, it would be hard for you to understand what I'm discussing:

  • Disjoint Set Union
  • Binary Search
  • Basic Discrete Mathematics
  • 1400 ELO

Descriptions

It's been a while since I've done competitive programming, but somehow I came across this problem. https://atcoder.jp/contests/joisp2025/tasks/joisp2025_c. You're given a grid of size $H \times W \leq 3\times10^5$.

The grid has a value $T[i][j] \leq 10^9$. You can jump from a cell $S(X_s, Y_s)$ to any other cell $E(X_e, Y_e)$, as long as there is a path from your current start point $S$ to the end target $E$. A path is defined by a movement in 4 directional directions (NESW), and every cell in your path has height $\leq T[X_s][Y_s] + L$. Where $L$ is like your "jumping" power.

You're given $Q \leq 3\times10^5$ queries. Each query asks whether you can travel from a cell $S (X_S, Y_S)$ to $E (X_S, Y_S)$, and what's the minimum amount of jumps you need..

image-20260429230036268

Let's say you start at red $(2, 2)$, and your jumping power $L$ is $1$. In one jump, you can reach all those cells shaded in green.

image-20260429230147251

If your jumping power, again, is $1$, and you start from $(1, 2)$, you can jump to many places!

So basically, if you wanna jump from $(2, 2)$, you need to jump to $(1, 2) \rightarrow (2, 1) \text{ or } (2, 3) ... \rightarrow (1, 3) \rightarrow (2, 3)$. Thus, you need $4$ jumps.

Inputs are given in the current format:

H W L
[The Grid]
Q
Xs Ys Xe Ye
...
...

2 4 5
1 3 22 1
8 13 6 16
6
1 1 2 2
1 1 1 3
1 1 2 3
1 1 2 4
1 1 1 4
1 1 1 2

would have

3
-1
3
4
4
1

Observation and Discussion

  • Observation 1: As someone who has a strong sense of data structures, you'll know this needs DSU. You'll sort it based on its height, either ascending or descending, for each cell, and run a merging algorithm on it.

  • Observation 2: From a cell $S$, if you want to go to any cells, it makes sense to jump as high as possible to the cell you can reach. Because any other cells within the same connected components are reachable anyway after that jump.

After this 2 trivial observations, things get hard.

  • Observation 3: From observation 2, I tried to develop the idea, and ended up making a tree out of it, equipped with binary lifting ability:
    • $\text{lift}(v, k)$ where it will return the $k$-th ancestor of $v$.

I was stuck here for a good 2 hours, trying to know the meaning of "shortest distance" here. I developed some more useless observations, like:

  • If you are in a higher cell, you can always go down in one jump if and only if your next cell is in one connected component. I was also stuck thinking about the idea that you can get over a barrier. A case like 3 8 1, and your jumping power $L$ is $6$, starting from $3$. I was thinking of the idea using $LCA$ to find on whether $1$ needs to find a way to $8$ โ€” which would be impossible, because it's a oneway jump from $3$ or $8$ to $1$ but not otherwise.
  • Then I came up with the core observation. Observation 4: Indeed, you'll build the tree from observation $3$, but to use the tree, you need to find the lowest element from your starting point $S$, going up to the very root, and you would like to know whether it can reach your target $E$.
image-20260429234247100

Imagine $E$ is in one of these subtrees. Let's say $E$ is this $2$, at position $(4, 1)$. Your jumping power is $4$, and you start from the other $2$ at $(1, 2)$.

Now, you will need to find whether you can connect $S$ and $E$. So LCA is definitely not in the play here. What I'm doing is that we know that UFDS is connecting the components one by one, starting from the smallest number. What if I wanna know whether S and E are connected?

  • Observation 5: If you start at $S$, you climb up to an upper platform $A$, and some cells unlock, the upper platform $B$ will have the superset of the cells that you unlock too. With this monotonicity intuition, it makes sense to binary search.
    • From the path of root $R$ to $S$, what is the lowest node $X$ that, when ๐‘‹ is processed, both ๐‘† and ๐ธ are already connected? ted.
  • Observation 6: There are multiple queries, so the only thing that makes sense is to do parallel binary search... This would give you something like a $Q \log^2(HW)$, which will run fast enough if you're good at implementing it!

Comments