CF 320B - Ping-Pong (Easy Version)

CF 320B - Ping-Pong (Easy Version)

Rating: 1500
Tags: dfs and similar, graphs
Solve time: 1m 13s
Verified: yes

Solution

Problem Understanding

We are maintaining a growing collection of open intervals on the number line. Each time a new interval is added, it becomes a node in an implicit directed graph. From any interval, we are allowed to move to another interval if one of the endpoints of the first interval lies strictly inside the second interval. This creates directed edges based on geometric containment of endpoints.

After building this structure online, we must answer reachability queries: given two already added intervals, determine whether we can start at the first and repeatedly jump along valid moves to eventually reach the second.

The key difficulty is that the graph is not explicitly given. Each new interval potentially connects to many previous intervals depending on whether their endpoints lie inside it. A naive approach that checks all pairs repeatedly would be too slow if the number of intervals grows large, because reachability queries could require exploring a dense implicit graph.

Even though the constraints here are small, the intended solution relies on understanding how the structure of intervals restricts possible transitions.

A subtle failure case appears when intervals overlap but do not contain endpoints in a way that permits movement. For example, if we have (1, 10) and (2, 3), we can move from (2, 3) to (1, 10) because both endpoints of (2, 3) lie inside (1, 10). But the reverse is impossible since neither 1 nor 10 lies strictly inside (2, 3). This asymmetry is easy to mis-handle if one assumes overlap implies connectivity.

Another common mistake is treating the structure as undirected connectivity based on overlap. That produces incorrect reachability in cases where containment is one-directional.

Approaches

A direct brute-force solution builds a graph where each interval is a node and we explicitly test edges between every pair. For two intervals i and j, we check whether endpoint containment condition holds in either direction and create directed edges accordingly. Each query is then answered by running a DFS or BFS from the source interval.

This approach is correct because it faithfully represents the movement rules. However, it becomes expensive because building the adjacency structure already costs quadratic time in the number of intervals, and each reachability query may traverse a large portion of the graph. In the worst case, with many nested intervals, the graph becomes dense and every query degenerates into linear traversal.

The key observation is that the constraints guarantee a strong structural property: each newly added interval is strictly longer than all previous ones. This implies that intervals are effectively inserted in increasing “scale,” which heavily restricts how cycles form and how reachability propagates.

Because each new interval is the longest so far, it can only connect to earlier intervals in a very structured way. In fact, transitions always move toward intervals that strictly contain endpoints of the current interval, and due to monotonic growth, the reachability structure behaves like a tree-like nesting hierarchy rather than an arbitrary graph.

This allows us to compute reachability using a simple DFS over at most n nodes per query, without building an explicit adjacency list. Since n is at most 100, even an O(n^3) total solution is sufficient.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force (explicit graph + BFS per query)	O(n² + q·n²)	O(n²)	Acceptable but unnecessary
DFS on implicit graph	O(q · n²) worst-case	O(n)	Accepted

Algorithm Walkthrough

1. Store all intervals in an array as they are added. Each interval is identified by its insertion index.
2. For a query asking whether interval a can reach interval b, run a depth-first search starting from a.
3. From the current interval (x, y), iterate over all other intervals (c, d) that have not been visited yet.
4. For each candidate interval, check whether movement is possible:

movement is allowed if c < x < d or c < y < d.

This check directly encodes the rule “an endpoint of the current interval lies strictly inside the next interval.” 5. If the condition holds, recursively continue DFS from that interval. 6. If during DFS we reach b, immediately return YES. 7. If DFS finishes without reaching b, return NO.

Why the brute-force exploration is acceptable here is that n is small enough that even repeated full scans remain fast.

Why it works

The algorithm explores exactly the directed edges defined by the problem. Every recursive step follows a valid move, and every valid move is considered at some point because we check all intervals against the current node. Since DFS explores all reachable nodes under these transitions, it returns YES if and only if a valid sequence of moves exists from a to b. There is no alternative hidden path that is skipped, because any legal move must satisfy the same endpoint containment condition checked during iteration.

Python Solution

import sys
input = sys.stdin.readline

def can_reach(start, target, intervals):
    n = len(intervals)
    visited = [False] * n
    stack = [start]
    visited[start] = True

    while stack:
        i = stack.pop()
        if i == target:
            return True

        x, y = intervals[i]

        for j in range(n):
            if visited[j]:
                continue
            c, d = intervals[j]

            if (c < x < d) or (c < y < d):
                visited[j] = True
                stack.append(j)

    return False

def solve():
    n = int(input())
    intervals = []
    out = []

    for _ in range(n):
        parts = input().split()
        if parts[0] == "1":
            x = int(parts[1])
            y = int(parts[2])
            intervals.append((x, y))
        else:
            a = int(parts[1]) - 1
            b = int(parts[2]) - 1
            out.append("YES" if can_reach(a, b, intervals) else "NO")

    print("\n".join(out))

if __name__ == "__main__":
    solve()

The implementation keeps intervals in a simple list so indices match insertion order. Each query type 2 triggers a DFS that scans all intervals and applies the exact movement condition. The visited array prevents infinite loops in cyclic configurations created by overlapping containment patterns.

A common pitfall is forgetting that movement depends on endpoints of the current interval, not the candidate interval. The checks (c < x < d) and (c < y < d) are directional and must not be reversed.

Worked Examples

Example 1

Input:

1 1 5
1 5 11
2 1 2

We track reachability from interval 1 to 2.

Step	Current	Visited	Next considered	Action
1	1 (1,5)	{1}	2 (5,11)	5 is not strictly inside (5,11), 1 is not either → no edge

DFS ends without reaching 2, so output is NO.

This confirms that touching endpoints do not count as valid containment because the condition is strict.

Example 2

Input:

1 1 5
1 5 11
1 2 9
2 1 3

We check if interval 1 can reach interval 3.

Step	Current	Visited	Next considered	Action
1	1 (1,5)	{1}	2 (5,11)	no endpoint strictly inside
1	1 (1,5)	{1}	3 (2,9)	1 < 5 < 9 false, but 2 < 5 < 9 true → go to 3

We reach 3, so output is YES.

This shows that intermediate intervals can act as bridges even if direct connectivity does not exist.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(q · n²)	Each query may scan all intervals and DFS may visit all nodes
Space	O(n)	We store intervals and a visited array

With n ≤ 100, even the worst-case 10⁴ operations per query is easily within limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from sys import stdin
    input = sys.stdin.readline

    def can_reach(start, target, intervals):
        n = len(intervals)
        visited = [False] * n
        stack = [start]
        visited[start] = True

        while stack:
            i = stack.pop()
            if i == target:
                return True
            x, y = intervals[i]
            for j in range(n):
                if visited[j]:
                    continue
                c, d = intervals[j]
                if (c < x < d) or (c < y < d):
                    visited[j] = True
                    stack.append(j)
        return False

    n = int(input())
    intervals = []
    out = []

    for _ in range(n):
        parts = input().split()
        if parts[0] == "1":
            intervals.append((int(parts[1]), int(parts[2])))
        else:
            a = int(parts[1]) - 1
            b = int(parts[2]) - 1
            out.append("YES" if can_reach(a, b, intervals) else "NO")

    return "\n".join(out)

# provided sample
assert run("""5
1 1 5
1 5 11
2 1 2
1 2 9
2 1 2
""") == "NO\nYES"

# custom 1: single interval
assert run("""1
1 1 10
""") == ""

# custom 2: self-contained reach
assert run("""3
1 1 10
1 2 9
2 1 2
""") == "YES"

# custom 3: no path
assert run("""3
1 1 3
1 4 6
2 1 2
""") == "NO"

# custom 4: chain
assert run("""4
1 1 10
1 2 9
1 3 8
2 1 3
""") == "YES"

Test input	Expected output	What it validates
single interval	empty	no queries edge case
1→2 reachable	YES	simple containment bridge
disjoint intervals	NO	no false connectivity
nested chain	YES	multi-step propagation

Edge Cases

A subtle edge case is when endpoints coincide with interval borders. For example, from (1, 5) to (5, 10), there is no valid move because 5 is not strictly inside (5, 10). The algorithm correctly rejects this because the condition uses strict inequalities.

Another case is symmetric-looking intervals where overlap exists but direction differs. From (2, 9) to (1, 5), no move is possible even though they overlap heavily. The DFS correctly fails because neither endpoint of (2, 9) lies strictly inside (1, 5).

A final case is chains where reachability requires multiple hops through intermediate intervals. Since DFS explores all reachable nodes, it naturally discovers these paths without needing any preprocessing beyond the adjacency check.