CF 1062473 - Advertising

CF 1062473 - Advertising

Rating: -
Tags: -
Solve time: 34s
Verified: yes

Solution

Problem Understanding

The problem describes a shop that wants to choose one pack size a. Every customer wants to buy some amount of cans between l and r. A customer first takes as many full packs of size a as possible. If the remaining cans are at least half of a pack, the customer also buys one extra full pack instead of buying the leftover cans separately.

The task is to decide whether there exists some pack size a such that every possible customer amount in the interval [l, r] ends up buying strictly more cans than they originally wanted.

The important observation is that a chosen pack size only needs to make the interval of possible purchases land inside the "round up" region of the pack. The values of l and r can be as large as 10^9, so checking every possible pack size is impossible. Even a loop over all values up to r would take too many operations in the worst case. With up to thousands of test cases, the solution needs to work in constant time or close to it.

The tricky part is understanding the boundary. If the customer wants exactly a multiple of a, they already bought the exact amount and cannot be forced to buy more. Also, if the leftover part is less than half of the pack, the customer keeps the original number of cans. A careless solution might only check one endpoint of the interval and miss that another value inside the interval behaves differently.

For example, consider:

1
1 2

The correct answer is:

NO

Trying a = 2 looks promising because a customer buying 2 cans fills a pack. However, a customer buying 1 can has a remainder of 1, and since it is not strictly enough to trigger the extra pack in the intended way, they do not buy more. The smallest possible intervals need special attention.

Another example:

1
3 4

The correct answer is:

YES

Choosing a = 5 works. A customer buying 3 cans has remainder 3, and a customer buying 4 cans has remainder 4. Both remainders are at least half of the pack, so both customers take the full pack and buy more.

Approaches

The direct approach is to try every possible pack size a and test whether every value from l to r becomes larger after the customer's decision. For a fixed a, we can simulate the customer behavior for every possible purchase amount. This is correct because it checks the exact condition required by the problem.

The problem is the number of checks. The interval length can be as large as 10^9, and the possible pack sizes can also be very large. A brute force solution could require around 10^18 checks in the worst case, which is far beyond what can run in time.

The key insight comes from rewriting the condition. For a value x to increase after choosing pack size a, the value x must lie in the second half of some block of length a. The first half of every block fails because the customer keeps the original amount. The second half succeeds because the leftover is large enough to make the customer take one more pack.

For a fixed a, every successful range has the form:

[a / 2, a - 1] relative to each block of size a

The easiest way to guarantee that all numbers from l to r are successful is to choose a pack size a that is larger than twice the left boundary. If a = 2 * l, then the first successful region begins exactly at l, and all values before the end of the first pack can be covered. The only requirement is that the right boundary does not reach the end of the pack.

This reduces the question to checking whether there exists a value a where:

2 * l <= a
and
r < a

Such a value exists exactly when r < 2 * l. This single comparison is enough for every test case.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O((r-l+1) * r)	O(1)	Too slow
Optimal	O(1)	O(1)	Accepted

Algorithm Walkthrough

1. Read the interval [l, r] representing all possible customer purchases.
2. Compare r with 2 * l. The reason for this comparison is that the pack size must be large enough to make l the beginning of the profitable half of a pack, but it must also be larger than every value in the interval so that no customer hits an exact pack boundary.
3. If r < 2 * l, print YES. Otherwise, print NO.

Why it works: when r < 2 * l, choosing a = 2 * l makes every number from l to r fall before the end of the first pack and inside the region where the leftover is at least half of the pack. Every customer buys one extra pack. If r >= 2 * l, any pack large enough to help l will have a boundary reached by some value in the interval, and that value will not increase.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    t = int(input())
    ans = []
    for _ in range(t):
        l, r = map(int, input().split())
        if r < 2 * l:
            ans.append("YES")
        else:
            ans.append("NO")
    print("\n".join(ans))

if __name__ == "__main__":
    solve()

The solution only needs to store the answers for printing. The comparison uses 2 * l, and Python integers handle these values safely.

The condition directly implements the mathematical observation from the algorithm. There is no simulation, no loops over the interval, and no need to construct the pack size itself.

The boundary condition uses a strict inequality. If r == 2 * l, the interval reaches the exact point where a customer can fail, so the answer must be NO.

Worked Examples

Sample 1

Input:

3
3 4
1 2
120 150

Trace:

l	r	2*l	Check	Answer
3	4	6	4 < 6	YES
1	2	2	2 < 2 is false	NO
120	150	240	150 < 240	YES

The first and third cases have intervals completely inside a profitable part of a possible pack. The second case touches the boundary and fails.

Custom Trace

Input:

1
5 9

Trace:

l	r	2*l	Check	Answer
5	9	10	9 < 10	YES

Choosing a = 10 works. The possible purchases are all from 5 to 9, which are all in the second half of a pack of size 10.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(t)	Each test case performs one arithmetic comparison
Space	O(t)	The output list stores one answer per test case

The constraints allow this easily because even thousands of test cases only require a few thousand operations.

Test Cases

import sys, io

def solve_data(data):
    sys.stdin = io.StringIO(data)
    input = sys.stdin.readline

    t = int(input())
    res = []
    for _ in range(t):
        l, r = map(int, input().split())
        res.append("YES" if r < 2 * l else "NO")
    return "\n".join(res)

# provided samples
assert solve_data("""3
3 4
1 2
120 150
""") == """YES
NO
YES"""

# minimum size
assert solve_data("""1
1 1
""") == "YES"

# boundary where answer changes
assert solve_data("""2
5 9
5 10
""") == """YES
NO"""

# large values
assert solve_data("""1
500000000 999999999
""") == "YES"

# all values in a narrow failing range
assert solve_data("""1
100 200
""") == "NO"

Test input	Expected output	What it validates
1 1	YES	Checks the smallest possible interval
5 9	YES	Confirms a range just below the critical boundary
5 10	NO	Catches the strict inequality error
Large interval	YES	Confirms large values are handled without iteration
100 200	NO	Tests an interval that reaches a failing boundary

Edge Cases

For the interval:

1
1 2

the algorithm computes 2 * l = 2. Since r is not smaller than 2, it returns NO. The reason is that any pack size large enough to help the customer buying one can also have the customer buying two land exactly on a pack boundary.

For the interval:

1
3 4

the algorithm computes 2 * l = 6. Since 4 < 6, it returns YES. A valid pack size is 6, where both possible purchases have leftovers large enough to trigger buying the full pack.

For a large boundary case:

1
100000000 200000000

the algorithm does not iterate through any values. It only checks whether 200000000 < 200000000, which is false, so it returns NO. This demonstrates why the comparison must be strict and why the constant time solution handles maximum values safely.