A2SV G7 — Round #8

What does "book with the highest number" mean? Does it mean the highest number of pages, or the highest index? Read the note carefully!

"Book with the highest number" refers to the book's index ($$$1$$$-st, $$$2$$$-nd, $$$\dots$$$, $$$n$$$-th), not the number of pages it contains.

When we divide the $$$n$$$ books into two non-empty piles, the absolute highest index $$$n$$$ must end up in one of the piles. Therefore, the maximum index in that pile will always be $$$n$$$, meaning Temesgen will always read the $$$n$$$-th book and read $$$a_n$$$ pages from it.

For the other pile, we want its highest index, let's call it $$$k$$$, to have the maximum possible pages $$$a_k$$$. Can we make $$$k$$$ be any index from $$$1$$$ to $$$n-1$$$? Yes! We can simply place our chosen book $$$k$$$ into the second pile, and put all other books (including $$$n$$$) into the first pile. Thus, the second pile only contains book $$$k$$$, making $$$k$$$ its highest index.

Therefore, the maximum total number of pages Temesgen can read is $$$a_n + \max(a_1, a_2, \dots, a_{n-1})$$$.

1. Read the array of books $$$a$$$.
2. The pages from the first pile will always be $$$a_n$$$ (the last element in the array).
3. The pages from the second pile will be the maximum value among the first $$$n-1$$$ elements.
4. Add these two values together and print the sum.

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    
    # a[-1] is the n-th book
    # max(a[:-1]) is the max pages among the first n-1 books
    print(a[-1] + max(a[:-1]))

• Time Complexity: $$$O(n)$$$ per test case to find the maximum in the first $$$n-1$$$ elements.
• Space Complexity: $$$O(n)$$$ to store the array.

There are no zeros in the string. How does the number of digits affect the integer value of a string?

Since the digits are only from $$$1$$$ to $$$9$$$ (no leading zeros to worry about), any number with $$$2$$$ or more digits will always be strictly greater than a $$$1$$$-digit number.

This means if we split the string immediately after the first character, the first part has length $$$1$$$, and the second part has length $$$n-1$$$. If $$$n \ge 3$$$, the second part will have at least $$$2$$$ digits and will inherently be greater than the first part. The only edge case is when $$$n = 2$$$, where both parts have length $$$1$$$. In that case, we just need to ensure the first digit is strictly less than the second digit.

1. If $$$n = 2$$$ and the first digit is greater than or equal to the second digit, output NO.
2. Otherwise, output YES, set the number of splits to $$$2$$$, and print the first character followed by the rest of the string.

q = int(input())
for _ in range(q):
    n = int(input())
    s = input().strip()
    
    if n == 2 and s[0] >= s[1]:
        print("NO")
    else:
        print("YES")
        print(2)
        print(s[0], s[1:])

• Time Complexity: $$$O(n)$$$ per test case for string slicing.
• Space Complexity: $$$O(n)$$$ to store the substrings.

A bulb flips its state for every divisor of its index. Which numbers have an odd number of divisors?

A bulb $$$j$$$ starts ON and is flipped exactly $$$d(j)$$$ times, where $$$d(j)$$$ is the number of divisors of $$$j$$$. It will end up OFF if it is flipped an odd number of times.

The only numbers with an odd number of divisors are perfect squares. Therefore, out of the first $$$n$$$ bulbs, the number of bulbs that end up OFF is exactly $$$\lfloor \sqrt{n} \rfloor$$$. This means the number of bulbs remaining ON is $$$n - \lfloor \sqrt{n} \rfloor$$$.

Since the function $$$f(n) = n - \lfloor \sqrt{n} \rfloor$$$ is monotonically non-decreasing, we can find the minimum $$$n$$$ that yields exactly $$$k$$$ ON bulbs using binary search.

1. Set the binary search range: low = 1 and high = 2 * 10^18.
2. Calculate $$$mid$$$ and find how many bulbs are ON: $$$mid - \lfloor \sqrt{mid} \rfloor$$$.
3. If the number of ON bulbs is $$$\ge k$$$, update our answer to $$$mid$$$ and search the left half (high = mid — 1) to minimize $$$n$$$.
4. Otherwise, search the right half (low = mid + 1).

import math
import sys

input = sys.stdin.readline

def solve():
    t = int(input())
    for _ in range(t):
        k = int(input())
        
        low, high = 1, 2000000000000000000
        ans = high
        
        while low <= high:
            mid = (low + high) // 2
            on_bulbs = mid - math.isqrt(mid)
            
            if on_bulbs >= k:
                ans = mid
                high = mid - 1
            else:
                low = mid + 1
                
        print(ans)

solve()

• Time Complexity: $$$O(\log(\text{MAX\_N}))$$$ per query. With $$$MAX\_N \approx 2 \cdot 10^{18}$$$, this takes around 60 iterations, making it extremely fast overall.
• Space Complexity: $$$O(1)$$$.

If you know the maximum number of elements $$$k$$$ you can keep in the array, which elements from array $$$a$$$ and array $$$b$$$ should you pick to maximize the chances that $$$a_i \lt b_i$$$?

To minimize the number of operations (deletions), we need to maximize the final array length $$$k$$$. To maximize the probability of forming $$$k$$$ valid pairs $$$(a_i, b_i)$$$ where $$$a_i \lt b_i$$$, we should pair the $$$k$$$ smallest elements of array $$$a$$$ with the $$$k$$$ largest elements of array $$$b$$$.

Notice that $$$m=1$$$ in the constraints, so we only need to consider the case where the first element of $$$a$$$ is set to $$$1$$$. Once $$$a$$$ is updated and both arrays are sorted, the property of "being able to form $$$k$$$ pairs" is monotonic. If we can form $$$k$$$ pairs, we can also form $$$k-1$$$ pairs. Thus, we can use binary search on the answer!

1. Construct array $$$a$$$ by prepending $$$1$$$ to the given $$$n-1$$$ elements.
2. Sort both array $$$a$$$ and array $$$b$$$ in ascending order.
3. Binary search the maximum possible $$$k$$$ in the range $$$[0, n]$$$.
4. To check if a specific $$$k$$$ is valid: compare the first $$$k$$$ elements of $$$a$$$ with the last $$$k$$$ elements of $$$b$$$. If $$$a[i] \lt b[n - k + i]$$$ holds true for all $$$0 \le i \lt k$$$, then this $$$k$$$ is valid.
5. If valid, try to look for a larger $$$k$$$ by searching the right half. Otherwise, search the left half.
6. The minimum operations needed will be the total elements minus the maximum paired ones: $$$n - k$$$.

import sys

input = sys.stdin.readline

def solve():
    t = int(input())
    for _ in range(t):
        n, m = map(int, input().split())
        a = [1] + list(map(int, input().split()))
        b = list(map(int, input().split()))
        
        a.sort()
        b.sort()
        
        def check(k):
            # check if first k elements of 'a' are strictly less than the last k elements of 'b'
            for i in range(k):
                if a[i] >= b[n - k + i]:
                    return False
            return True
            
        low, high = 0, n
        max_k = 0
        
        while low <= high:
            mid = (low + high) // 2
            if check(mid):
                max_k = mid       # valid, store answer
                low = mid + 1     # try to find a larger k
            else:
                high = mid - 1    # invalid, try a smaller k
                
        # the minimum deletions is n minus the max elements we could keep
        print(n - max_k)

solve()

• Time Complexity: $$$O(n \log n)$$$. Sorting both arrays takes $$$O(n \log n)$$$. The binary search iterates $$$\log n$$$ times, and each `check` function takes $$$O(n)$$$ time in the worst case, contributing another $$$O(n \log n)$$$.
• Space Complexity: $$$O(n)$$$ to store the inputs.

For a given voucher, you need another non-overlapping voucher with a specific remaining duration that has the minimum possible cost. How can you efficiently query this using binary search?

Since the two chosen vouchers must equal exactly $$$x$$$ in total duration, a voucher of duration $$$dur$$$ strictly requires a partner voucher of duration $$$x - dur$$$.

We can group all the vouchers by their duration. Inside each group, if we sort the vouchers by their start time $$$l$$$, we can quickly find a non-overlapping partner! Specifically, for a voucher ending at $$$r_i$$$, we can binary search (using bisect_right) in the target duration group for the first voucher whose start time $$$l_j$$$ is strictly greater than $$$r_i$$$.

To quickly get the minimum cost among all valid partners that start at or after this index, we can precalculate a suffix minimums array for costs in each duration group.

1. Group all vouchers in a dictionary mapped by their duration: $$$r - l + 1$$$.
2. For each duration group, sort the vouchers by their start time $$$l$$$.
3. For each sorted group, create an array of just the start times (to be used for binary search) and a `suffix_mins` array that stores the minimum cost from that index to the end of the group.
4. Iterate over all vouchers. For a voucher with duration $$$dur$$$, end time $$$r$$$, and cost $$$c$$$, the target complementary duration is $$$rem = x - dur$$$.
5. If the $$$rem$$$ group exists, use binary search to find the first index where the start time is $$$ \gt r$$$.
6. If such an index exists, add $$$c$$$ to the value in the `suffix_mins` at that index, and update the global minimum total cost.
7. If the global minimum remains infinity, output -1.

import sys
from bisect import bisect_right
from collections import defaultdict

input = sys.stdin.readline

def solve():
    n, x = map(int, input().split())
    
    vouchers = []
    groups = defaultdict(list)
    
    for _ in range(n):
        l, r, cost = map(int, input().split())
        dur = r - l + 1
        vouchers.append((l, r, cost, dur))
        groups[dur].append((l, r, cost))
        
    start_times = {}
    suffix_mins = {}
    
    # Sort each duration group and build suffix minimums for O(1) minimum queries
    for dur in groups:
        groups[dur].sort(key=lambda v: v[0])
        st = [v[0] for v in groups[dur]]
        start_times[dur] = st
        
        # Build suffix minimums
        sm = [0] * len(st)
        sm[-1] = groups[dur][-1][2]
        for i in range(len(st)-2, -1, -1):
            sm[i] = min(sm[i+1], groups[dur][i][2])
        suffix_mins[dur] = sm
        
    ans = float('inf')
    
    for l, r, cost, dur in vouchers:
        rem = x - dur
        
        if rem in groups:
            st = start_times[rem]
            # Binary search for the first valid voucher that starts after this one ends
            pos = bisect_right(st, r)
            
            if pos < len(st):
                ans = min(ans, cost + suffix_mins[rem][pos])
                
    print(ans if ans != float('inf') else -1)

solve()

• Time Complexity: $$$O(n \log n)$$$. Grouping and sorting the vouchers takes $$$O(n \log n)$$$. Iterating through $$$n$$$ vouchers and performing a binary search on the start times takes $$$O(n \log n)$$$ as well.
• Space Complexity: $$$O(n)$$$ to store the dictionary groups, start times, and suffix minimums.