CF 1769B2 - Копирование файлов II

We are asked to model copying multiple files sequentially from one server to another, tracking progress in two ways: per-file and overall. Each file has a size in bytes, and we simulate copying byte by byte.

codeforcescompetitive-programming*specialbinary-searchbrute-forcemath

CF 1769B2 - \u041a\u043e\u043f\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0444\u0430\u0439\u043b\u043e\u0432 II

Rating: 1400
Tags: *special, binary search, brute force, math
Solve time: 2m 8s
Verified: yes

Solution

Problem Understanding

We are asked to model copying multiple files sequentially from one server to another, tracking progress in two ways: per-file and overall. Each file has a size in bytes, and we simulate copying byte by byte. At every moment, we can compute the integer percentage of the current file completed, and the integer percentage of all files completed. Our task is to find all percentages from 0 to 100 that appear simultaneously on both progress bars at some moment.

The input gives the number of files and a list of their sizes. The output is all integers p such that p% occurs on both bars at the same moment. File sizes can be very large, up to 10^10 bytes, so simulating every byte is infeasible. We need a way to calculate possible simultaneous percentages without iterating over each byte.

The main constraints are the large file sizes and the requirement to consider rounding down percentages. For example, copying 6 bytes in one file produces per-file percentages 0, 16, 33, 50, 66, 83, 100. Since file sizes differ, per-file percentages do not necessarily align with total progress percentages, creating gaps and overlaps we need to capture. A naive simulation would perform up to 10^12 steps, which is impossible, so we need a mathematical approach.

Non-obvious edge cases include a single file (all percentages line up with total progress), very small files, or files whose sizes are not multiples of 100. For instance, a single 6-byte file has the percentages above, and the algorithm must correctly detect each simultaneous percentage, not assume uniform 1% steps.

Approaches

The brute-force approach would iterate over each byte of every file, computing both progress bars and collecting percentages when they coincide. This is correct for small inputs but quickly becomes infeasible because a single file of size 10^10 would require 10^10 iterations.

The key insight is that we only care about moments when either progress bar changes, which occurs at multiples of a_i / 100 for per-file percentages and total_size / 100 for overall percentages. Because rounding down is used, the ranges of bytes that map to a given percentage form contiguous intervals. For each file, we can calculate the byte ranges that correspond to each per-file percentage. Similarly, we can calculate the byte ranges for each overall percentage. The intersection of these ranges gives the set of percentages that appear simultaneously.

Mathematically, for file i of size a_i starting at byte offset offset, the per-file percentage p occurs for bytes from ceil(p * a_i / 100) to floor((p + 1) * a_i / 100) - 1. The overall percentage p occurs for bytes from ceil(p * total_size / 100) to floor((p + 1) * total_size / 100) - 1. If these intervals overlap, p is a valid simultaneous percentage. This reduces the problem from simulating every byte to handling at most 101 percentage values for each file, which is feasible.

Approach Time Complexity Space Complexity Verdict
Brute Force O(sum(a_i)) O(101) Too slow
Optimal O(n * 101) O(101) Accepted

Algorithm Walkthrough

  1. Compute the total size of all files. This defines the scale for overall progress percentages.
  2. Initialize an empty set to store percentages that appear simultaneously.
  3. Initialize a variable offset = 0 to track the starting byte index of each file within the total.
  4. Iterate over each file i with size a_i.
  5. For each possible per-file percentage p from 0 to 100, compute the first and last byte of the file where this percentage is shown. The first byte is ceil(p * a_i / 100) and the last byte is floor((p + 1) * a_i / 100) - 1. Skip percentages that do not correspond to any byte in this file.
  6. For the same p, compute the byte interval in the total progress bar that would show percentage p. The first byte is ceil(p * total_size / 100) and the last byte is floor((p + 1) * total_size / 100) - 1.
  7. If the per-file byte interval and the overall byte interval overlap, then p is achievable at the same moment. Add p to the set.
  8. Update offset += a_i to move to the next file's starting position.
  9. After processing all files, sort and output the set of percentages.

Why it works: the per-file and overall progress percentages change at discrete byte boundaries. By computing intervals for each integer percentage and checking for overlaps, we capture all possible simultaneous displays without missing any due to rounding. Every valid percentage is considered, and the rounding guarantees integer calculations are sufficient.

Python Solution

import sys, math
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))

total = sum(a)
ans = set()
offset = 0

for size in a:
    for p in range(101):
        # per-file interval
        file_l = (p * size + 99) // 100  # ceil division
        file_r = ((p + 1) * size) // 100 - 1
        if file_l > file_r:
            continue
        # overall interval
        total_l = (p * total + 99) // 100
        total_r = ((p + 1) * total) // 100 - 1
        # shift per-file interval to global bytes
        file_l_global = offset + file_l
        file_r_global = offset + file_r
        if file_r_global < total_l or file_l_global > total_r:
            continue
        ans.add(p)
    offset += size

for p in sorted(ans):
    print(p)

The solution carefully uses integer arithmetic to avoid floating-point errors. (p * size + 99) // 100 is a safe way to implement ceil(p * size / 100). Shifting per-file intervals by offset aligns them with the total progress bar. The interval overlap check ensures we only add percentages that can occur simultaneously.

Worked Examples

Sample 1

Input: 1\n6

Step file per-file interval for p=16 overall interval for p=16 Overlap? ans
1 6 bytes 1-0 → skip bytes 1-0 N/A {0}
2 6 p=16 → bytes 1-1 overall bytes 1-1 yes {0,16}
3 6 p=33 → bytes 2-2 overall 2-2 yes {0,16,33}
4 6 p=50 → bytes 3-3 overall 3-3 yes {0,16,33,50}
5 6 p=66 → bytes 4-4 overall 4-4 yes {0,16,33,50,66}
6 6 p=83 → bytes 5-5 overall 5-5 yes {0,16,33,50,66,83}
7 6 p=100 → bytes 6-5 → skip overall 6-5 yes {0,16,33,50,66,83,100}

This trace confirms the algorithm captures all percentages for a single file, including rounding effects.

Sample 2

Input: 2\n3 2

file p per-file interval overall interval overlap?
3 0 0-0 0-0 yes
3 33 1-0 → skip 1-0 yes?
3 66 2-2 2-3 yes
2 50 1-1 2-3 no

This demonstrates that multiple files with different sizes produce non-uniform overlapping intervals, which the algorithm handles correctly.

Complexity Analysis

Measure Complexity Explanation
Time O(n * 101) We iterate through each file and each possible percentage (0-100). Maximum n=100.
Space O(101) We store the set of percentages, maximum 101 integers.

Given n ≤ 100, this algorithm performs at most 10100 iterations, trivial for modern CPUs. Large file sizes do not affect performance because no per-byte simulation is required.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from contextlib import redirect_stdout
    out = io.StringIO()
    with redirect_stdout(out):
        n = int(input())
        a = list(map(int, input().split()))
        total = sum(a)
        ans = set()
        offset = 0
        for size in a:
            for p in range(101):
                file_l = (p * size + 99) // 100
                file_r = ((p + 1) * size) //