The block size
Before synchronising a file a block size B must be chosen. A file of n bytes is cut into blocks of B bytes, the last block possibly shorter. Each block costs s bytes, the weight of its checksums. Besides, it is known which bytes of the file have changed, and every block containing at least one changed byte will have to be sent in full, as many bytes as it holds.
So the cost of a size B is s·(the number of blocks) plus the total length of the blocks with changes. Find the size B from 1 to n with the smallest cost; if there are several, the smallest. Three tests are the sites of real edits of a chapter of this site’s basic course: the bytes of the new version that were inserted or replaced.
Input
The first line holds the file length n, the cost of one block’s sums s and the number of changed bytes k (1 ≤ n ≤ 105, 1 ≤ s ≤ 1000, 0 ≤ k ≤ n). The second holds k distinct numbers of changed bytes in increasing order, from 0 to n − 1 (the line is empty when k = 0).
Output
Two numbers: the best block size and its cost.
In the first example with B = 12 there are two blocks, which is 8 bytes of sums, and only the first block has changes, another 12 bytes, 20 in all. With B = 4 the changed bytes 3, 4 and 11 spoil three blocks of five: 20 + 12 = 32. In the second example it pays to cut the changed last byte off into a separate short block: with B = 9 the cost is 2·3 + 1 = 7.
Examples
Example 1
20 4 3 3 4 11
12 20
Example 2
10 3 1 9
9 7
Limits
- Time · Python
- 8000 ms
- Time · Go
- 2000 ms
- Memory
- 256 MB
- Judging
- 11 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The article estimates the best size by the formula √(n·s/k). Why is that not enough here, while trying all B from 1 to n seems expensive: for each one you need to know which blocks are spoiled. How many blocks are there at all for size B?
2The idea
There are ⌈n/B⌉ blocks, and no more spoiled ones than blocks. If for each B you go through only the spoiled blocks, jumping from one to the next, the work over all B is at most n/1 + n/2 + … + n/n = n·Hn ≈ n ln n steps: the harmonic series. For the jumps you need an array “the next changed byte from position x on”.
3Walkthrough
Fill nxt[x], the number of the first changed byte not to the left of x, or n if there is none; that is one pass from right to left. For size B start with x = nxt[0]. Byte x lies in the block that starts at x − x mod B and ends at min(n, start + B). Add the length of this block to the cost and jump to nxt[end], the first change after it. The cost is s·⌈n/B⌉ plus the sum of lengths; among all B take the smallest cost, and on a tie the first size.
Why not the formula. The article’s model assumes each edit spoils exactly one block and all edits are scattered. In reality edits come in clusters: in the style pass (the third test) a thousand-odd bytes changed in a few dozen places, and the best size is 183 bytes; in the non-breaking spaces (the fourth test), 520. The formula gets the order of magnitude right, but only a search gives the exact answer. The extreme cases are instructive too: if sums are expensive (the eighth test), one block for the whole file is better; if only the last byte changed (the tenth), it is better to cut it off into a short tail.
3+Solution
4Complexity
O(n log n) time: for each B, at most min(k, ⌈n/B⌉) jumps. O(n) memory for the jump array.
5Common mistakes
- The last block is B bytes too. It is shorter, and cheaper to send. The second example catches this.
- Going through all changed bytes for each B. That is O(n·k): in the seventh test every byte changed, and the steps come to ten billion.
- Trying only B near the formula. The answer can be far from it, as in the eighth and tenth tests.
Algorithms behind it
O(n + m): the window sum shifts in O(1), the strong sum only on a weak match
2 problems
TEC
Technique
Prefix sums
The sum of any segment in O(1) after one pass; the two-dimensional version gives the sum of any rectangle of a picture.
O(n) to build, O(1) per query
2 problems