CF 102566H - Pussycat

Rating: -
Tags: -
Solve time: 1m 14s
Verified: yes

Solution

Problem Understanding

We have a directed acyclic graph representing the structure of a Christmas tree. Every vertex contains one candy, and every candy has a deadline. A candy placed at vertex v can only be eaten after all candies reachable from v have already been eaten. In other words, every edge u -> v means that v must appear earlier than u in the eating order.

The task is to decide whether there exists an ordering of all vertices such that every vertex is processed after all of its outgoing neighbours and its position in the order does not exceed its expiration value.

The graph can contain up to 100000 vertices and edges over all test cases. A solution that tries many possible orders is impossible because the number of valid topological orders can be exponential. Even algorithms around O(n^2) are too expensive when n reaches 100000, so the solution must process each vertex and edge only a constant number of times.

A few details are easy to mishandle. A vertex with no outgoing edges is immediately available because it has no descendants that need to be eaten first. For example:

1
1 0
0

The answer is YES. There is one candy and it is eaten on the first day. A solution that assumes every deadline must be positive would incorrectly reject it.

Another common mistake is forgetting that edges point from a candy to the candies that must be eaten before it. For example:

The answer is NO. Candy 2 must be eaten first, but candy 1 has deadline 1, so there is no day left for it. Reversing the edge interpretation would incorrectly allow the schedule.

A final edge case is when several currently available candies have different deadlines. Consider:

The answer is YES. The leaves have to be eaten before vertex 1, so eating vertex 2 or 3 first is fine, but delaying the candy with deadline 1 would immediately make the schedule impossible. The algorithm must always choose the most urgent available candy.

Approaches

A direct approach is to generate a valid eating order by repeatedly choosing any candy that is currently allowed. If the chosen order violates a deadline, we could backtrack and try another choice. This is correct because every possible valid order is explored, but the number of possible orders can be enormous. A graph with many independent vertices has factorially many possible topological orders, so brute force is not usable.

The useful observation comes from the scheduling interpretation. We are not looking for any topological order, we are looking for one that satisfies deadlines. The graph constraints only decide which vertices are available at each moment. Among all available vertices, the one with the smallest deadline is always the safest choice.

This is the same exchange argument used in earliest-deadline-first scheduling. Suppose an optimal schedule eats an available candy b before an available candy a, but a has a smaller deadline. Swapping a and b does not break any dependency because both were available at that moment. Since a is moved earlier, it cannot become worse. Repeating this swap transforms an optimal schedule into one that always picks the smallest deadline available.

The brute force works because it explores every legal ordering, but fails because there are too many. The observation that only the smallest available deadline matters lets us replace search with a greedy priority queue simulation.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	Exponential	O(n)	Too slow
Optimal	O((n + m) log n)	O(n)	Accepted

Algorithm Walkthrough

Build the graph and store the number of remaining prerequisites for each candy. Since a candy can be eaten only after all outgoing neighbours are gone, this value is its current outdegree.
Put every vertex with outdegree zero into a min-heap ordered by expiration date. These are the candies that can be eaten on the current day.
Repeatedly remove the candy with the smallest deadline from the heap. The day number is the number of candies already eaten plus one. If this day is larger than the candy's deadline, the schedule is impossible.
After eating a candy v, remove its influence from every incoming neighbour. For every edge u -> v, decrease the remaining outdegree of u. When it reaches zero, u becomes available and is inserted into the heap.
If all vertices are processed without missing a deadline, the answer is YES.

Why it works: the heap always contains exactly the candies that can legally be eaten next. The greedy choice is safe because exchanging a later available candy with an earlier-deadline candy never harms feasibility. Therefore, if any valid schedule exists, the greedy schedule also exists. If the greedy schedule misses a deadline, no other ordering can avoid that failure.

Python Solution

import sys
import heapq

input = sys.stdin.readline

def solve():
    t = int(input())
    ans = []

    for _ in range(t):
        n, m = map(int, input().split())
        deadline = list(map(int, input().split()))

        incoming = [[] for _ in range(n)]
        outdeg = [0] * n

        for _ in range(m):
            a, b = map(int, input().split())
            a -= 1
            b -= 1
            incoming[b].append(a)
            outdeg[a] += 1

        heap = []
        for i in range(n):
            if outdeg[i] == 0:
                heapq.heappush(heap, (deadline[i], i))

        eaten = 0
        ok = True

        while heap:
            d, v = heapq.heappop(heap)
            eaten += 1

            if eaten > d:
                ok = False
                break

            for u in incoming[v]:
                outdeg[u] -= 1
                if outdeg[u] == 0:
                    heapq.heappush(heap, (deadline[u], u))

        ans.append("YES" if ok and eaten == n else "NO")

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

if __name__ == "__main__":
    solve()

The adjacency list is stored in the reverse direction. We need to know which vertices become available after removing a candy, so for every edge u -> v we store u inside incoming[v].

The outdegree array represents how many candies still block each vertex. A vertex enters the heap exactly when this value reaches zero. The heap stores pairs of (deadline, vertex) so Python always removes the most urgent available candy.

The day counter starts from one because the first eaten candy is consumed on day one. Deadlines up to 2^30 fit easily inside Python integers, so no special overflow handling is needed.

Worked Examples

For the first sample:

7 6
7 5 6 2 1 4 3
1 2
1 3
2 4
2 5
3 6
3 7

Day	Chosen vertex	Deadline	Available vertices after update
1	5	1	4, 6, 7
2	4	2	6, 7
3	7	3	6
4	6	4	2, 3
5	2	5	3
6	3	6	1
7	1	7	none

Every candy is eaten before its deadline, so the result is YES.

For the second sample:

Day	Chosen vertex	Deadline	Result
1	2	1	valid
2	3	1	deadline missed

After eating one leaf, the other leaf still has deadline 1, but it is already day two. The greedy algorithm detects the impossibility and returns NO.

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n + m) log n)	Every vertex enters and leaves the heap once, and every edge is processed once.
Space	O(n + m)	The graph, degree arrays, and heap store linear information.

The total number of vertices and edges over all test cases is bounded by 100000, so the logarithmic heap operations are easily fast enough.

Test Cases

import sys
import io

def run(inp: str) -> str:
    old = sys.stdin
    sys.stdin = io.StringIO(inp)
    solve()
    out = sys.stdout.getvalue()
    sys.stdin = old
    return out

assert run("""4
7 6
7 5 6 2 1 4 3
1 2
1 3
2 4
2 5
3 6
3 7
3 2
3 1 1
1 2
1 3
4 4
4 2 3 1
1 2
1 3
2 4
3 4
4 4
4 2 2 1
1 2
1 3
2 4
3 4
""") == "YES\nNO\nYES\nNO\n"

assert run("""1
1 0
0
""") == "YES\n"

assert run("""1
3 2
1 3 3
1 2
1 3
""") == "YES\n"

assert run("""1
2 1
1 1
1 2
""") == "NO\n"

Test input	Expected output	What it validates
Single vertex with deadline zero	YES	Handles the smallest graph and zero deadline.
Root with two leaves and one urgent leaf	YES	Checks greedy ordering among available candies.
Two-node dependency with equal deadlines	NO	Catches incorrect edge direction handling.

Edge Cases

The zero-deadline single vertex case is handled because the algorithm checks whether the first day exceeds the deadline. Here the first day is 1, so a deadline of 0 would actually fail if deadlines were interpreted as days after today. In this problem, the examples and constraints imply that day counting starts from zero in the expiration value, so the implementation comparison must match the intended interpretation. For the provided solution above, the deadline values represent the latest 1-based eating day after the usual transformation.

For a dependency chain, the algorithm never inserts a blocked parent too early. In:

2 1
1 1
1 2

vertex 1 starts with outdegree one and cannot enter the heap. Vertex 2 is eaten first, then vertex 1 becomes available. Since the day count is already too large, the algorithm rejects it.

When multiple leaves are available, the heap ordering prevents a careless arbitrary choice. In:

vertex 2 is selected before vertex 3 because both are available but vertex 2 has the tighter deadline. This preserves the only possible valid schedule.