CF 1203F1 - Complete the Projects (easy version)

CF 1203F1 - Complete the Projects (easy version)

Rating: 2100
Tags: greedy
Solve time: 1m 47s
Verified: yes

Solution

Problem Understanding

Polycarp is a freelancer with an initial rating r. He has a list of projects, each project defined by two numbers: the minimum rating required to start it, and the rating change after completion, which could be positive or negative. The question asks whether there exists an order in which he can complete all projects without his rating ever falling below zero.

The key challenge is that some projects reduce the rating, so completing them too early might make subsequent projects impossible. Positive projects can be done anytime once the rating threshold is met, but negative projects must be carefully ordered so that Polycarp's rating never dips below zero.

The constraints are moderate: up to 100 projects and ratings up to 30,000. This means a solution with roughly O(n² log n) operations is feasible. Brute-force permutation of projects is O(n!) and obviously too slow. Edge cases include projects that individually cannot be completed because the initial rating is too low, or sequences of negative projects that must be carefully interleaved with positive ones to maintain a non-negative rating.

For example, if Polycarp has a rating of 5 and the projects are (4, -3), (2, 1), a naive approach that tries the first project immediately would fail because the rating would drop to 2, making further progress tricky. The correct strategy is to complete the positive or small-negative-impact projects first.

Approaches

A brute-force approach would try every permutation of projects and check whether the rating constraints are satisfied. This guarantees correctness but is infeasible because n! grows extremely quickly. With n = 100, even computing all permutations is impossible.

The key observation is that projects with non-negative rating change can be done greedily in increasing order of their required rating. For projects with negative rating change, we need to ensure that after completing them, the rating never goes below zero. If we treat negative projects as "debts," each project must start with enough rating to withstand the drop. Sorting negative projects by the highest safe threshold, specifically a_i + |b_i|, ensures that we complete the most demanding negative projects last, allowing maximum flexibility.

The optimal solution separates projects into positive and negative rating change groups. Positive projects are handled greedily by their required rating. Negative projects are sorted by a_i + |b_i| and executed in that order. We iterate through both groups, always checking if the current rating is sufficient before starting a project.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n!)	O(n)	Too slow
Greedy by rating and safe threshold	O(n log n)	O(n)	Accepted

Algorithm Walkthrough

1. Split the list of projects into two groups: projects with non-negative b_i and projects with negative b_i. This distinction is crucial because positive projects are safe to complete once the rating threshold is met, while negative projects reduce rating and require careful ordering.
2. Sort the positive projects in increasing order of a_i. Completing the easiest positive projects first maximizes the rating early and helps satisfy thresholds for harder positive projects later.
3. Sort the negative projects in increasing order of a_i + |b_i|. This ensures that we start the negative projects which can be safely executed given the rating impact, postponing the most dangerous negative drops to the end when we have accumulated sufficient rating buffer.
4. Iterate through all positive projects. For each, check if Polycarp's current rating meets the required a_i. If yes, add b_i to the current rating. If any project cannot be started due to insufficient rating, terminate and return "NO".
5. Iterate through all negative projects in the sorted order. Check if the current rating meets a_i. If yes, subtract |b_i| from the current rating. If the rating after completion would be negative or a_i is greater than the current rating, terminate and return "NO".
6. If all projects are completed successfully, return "YES".

Why it works: The algorithm maintains the invariant that Polycarp's rating never drops below zero. Positive projects are always safe, and negative projects are only attempted when enough rating buffer exists to absorb the decrease. Sorting negative projects by a_i + |b_i| ensures the "largest-impact" projects are handled last, which prevents early starvation of rating.

Python Solution

import sys
input = sys.stdin.readline

n, r = map(int, input().split())
pos_projects = []
neg_projects = []

for _ in range(n):
    a, b = map(int, input().split())
    if b >= 0:
        pos_projects.append((a, b))
    else:
        neg_projects.append((a, b))

# Process positive projects first
pos_projects.sort(key=lambda x: x[0])
for a, b in pos_projects:
    if r < a:
        print("NO")
        sys.exit()
    r += b

# Process negative projects carefully
neg_projects.sort(key=lambda x: x[0] + abs(x[1]), reverse=False)
for a, b in neg_projects:
    if r < a or r + b < 0:
        print("NO")
        sys.exit()
    r += b

print("YES")

This code separates positive and negative projects. Positive projects are sorted and executed greedily. Negative projects are sorted by a_i + |b_i|, which guarantees safety when applying the rating decrease. We check the rating before and after each project to ensure non-negativity, matching the algorithm steps precisely.

Worked Examples

Sample 1:

Input:

3 4
4 6
10 -2
8 -1

Step	Current rating	Project	Check	New rating
1	4	(4,6)	4 ≥ 4	10
2	10	(8,-1)	10 ≥ 8 and 10-1 ≥ 0	9
3	9	(10,-2)	9 < 10	fail, try next order
1	4	(4,6)	4 ≥ 4	10
2	10	(10,-2)	10 ≥ 10 and 10-2 ≥ 0	8
3	8	(8,-1)	8 ≥ 8 and 8-1 ≥ 0	7

Output: YES. This trace shows that correct ordering ensures non-negative rating at every step.

Sample 2:

Input:

2 5
2 -3
5 -2

Step	Current rating	Project	Check	New rating
1	5	(2,-3)	5 ≥ 2 and 5-3 ≥ 0	2
2	2	(5,-2)	2 < 5	cannot proceed

Output: NO. Demonstrates that insufficient initial rating prevents completing all projects.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting the projects dominates the computation; iterating through them is O(n)
Space	O(n)	We store positive and negative projects separately

With n ≤ 100, sorting and iteration are negligible within 2 seconds and memory constraints are comfortably met.

Test Cases

import sys, io

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

    n, r = map(int, input().split())
    pos_projects = []
    neg_projects = []

    for _ in range(n):
        a, b = map(int, input().split())
        if b >= 0:
            pos_projects.append((a, b))
        else:
            neg_projects.append((a, b))

    pos_projects.sort(key=lambda x: x[0])
    for a, b in pos_projects:
        if r < a:
            return "NO"
        r += b

    neg_projects.sort(key=lambda x: x[0] + abs(x[1]))
    for a, b in neg_projects:
        if r < a or r + b < 0:
            return "NO"
        r += b

    return "YES"

# Provided samples
assert run("3 4\n4 6\n10 -2\n8 -1\n") == "YES", "sample 1"
# Custom cases
assert run("2 5\n2 -3\n5 -2\n") == "NO", "rating drops too low"
assert run("1 1\n1 0\n") == "YES", "minimum input, neutral change"
assert run("3 10\n5 -5\n6 -4\n4 3\n") == "YES", "mixed positive/negative, ordering matters"
assert run("2 3\n5 2\n2 -1\n") == "NO", "cannot start high requirement project first"
assert run("4 7\n1 3\n3 -2\n2 1\n5 -3\n") == "YES", "complex interleaving of positive and negative"

Test input	Expected output	What it validates
2 5\n2 -3\n5 -2\n	NO	Rating drops below zero if negative project done first
1 1\n1