PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Shanu Singroha
Tester: Harris Leung
Editorialist: Pratiyush Mishra, Jakub Safin
DIFFICULTY:
Medium
PREREQUISITES:
Bitset
PROBLEM:
A_1, A_2, \ldots, A_N are written down. In one operation, you should remove two of these elements and write down their difference. When there’s only one element remaining, how many distinct values can it have?
EXPLANATION:
Key observation: the final element is always in the form \sum_{i=1}^N s_i A_i, where s_i \in \{-1,1\} (for each valid i) are suitably chosen signs.
More generally, whenever we have a sequence B_1, B_2, \ldots, B_M, then each of its elements is created by adding/subtracting a subset of the original elements; let’s denote the subset of indices forming B_i by R_i. Naturally, R_1, R_2, \ldots, R_M are disjoint and cover all elements 1, 2, \ldots, N. It’s easy to see why this holds: |B_i-B_j| is B_i-B_j or B_j-B_i, so it’s formed by merging R_i and R_j and flipping the signs of original elements forming B_i or B_j.
This is a necessary condition, but not a sufficient one. The most obvious reason is that we cannot create \sum_{i=1}^N s_i A_i \lt 0, but values like \sum_{i=1}^N A_i (for N \gt 1) are also impossible since the first operation already gives two different signs. Could there be any other impossible sequences of signs? From now on, let’s assume that the sequence A is sorted. A bit of testing with bruteforce shows that if m is the largest index such that s_m = 1, then \sum_{i=1}^N s_i A_i \in [0,A_m] can be constructed, and this condition is both necessary and sufficient.
Necessary: After N-M operations, let’s denote the current sequence by B_1, B_2, \ldots, B_M as above and its elements by B_j = \sum_{i \in C_j} s_{M,i} A_i. Further, let’s denote the maximum index in C_j with a positive sign by m_j = \max(k \in C_j: s_{M,k} = 1); elements are non-negative, so there must be a positive sign. We want to prove that B_j \le A_{m_j}.
For M = N, this holds since B_j = A_j for each valid j. The sequence for M is created by picking some elements x \le A_{mx} and y \le A_{my} from the sequence for M+1, removing them and adding |x-y|. W.l.o.g. for x \le y, we have |x-y| \le y \le A_{my}. The signs of elements that formed y don’t change, so s_{M,my} = 1. By induction, if the claim holds for M+1, then we see that it holds for |x-y| since the largest index with positive sign there is at least my, and obviously nothing changes for the other elements, so the claim also holds for M.
Sufficient: We want to inductively construct \sum_{i=1}^N s_i A_i, where we know that it’s in the range [0,A_m] and s_m = 1. For N = 1, we don’t need to do anything. In the induction step, the construction works for sequences with size N-1 so far.
- If s_N = -1, the range [0,A_m] tells us 0 \le \sum_{i \neq m} (-s_i) A_i \le A_m \le A_N. We already know that we can construct this sum (from N-1 elements) and simply subtract it from A_m.
- If s_N = 1 and all other s_i = -1, we can directly subtract everything from A_N and we’re done.
- The last case is when s_N = 1 and there are two indices j \lt k \lt N such that s_j \neq s_k. Then we subtract A_j from A_k and recursively construct \sum_{i \neq j,k} s_i A_i + s_k (A_k-A_j), which is the same sum from N-1 remaining elements. Since element A_N still has sign 1 in this sum, we already know that it can be constructed.
Note that elements 0 can appear during this process, but we can get rid of them instantly, letting us assume that we’re only working with positive elements.
Implementation
First, we sort A. Then for each m, we want to find all values of \sum s_i A_i such that s_m = 1 and all signs \gt m are -1. Among these values, we discard those not in the range [0,A_m] and finally count how many distinct values there are in total.
The only hard part here is finding all values of \sum s_i A_i. We actually have to do it the simple, slow way, listing all values of \sum_{i=1}^M s_i A_i and either adding or subtracting A_{M+1} to get all values of \sum_{i=1}^{M+1} s_i A_i. (When we add A_{M+1}, we can just check values in the range [0,A_{M+1}].) Constant-optimisation is important - efficiently implemented bitsets (e.g. std::bitset) are crucial since adding A_{M+1} is just left shift, subtracting is right shift and combining that is bitwise OR.
Temporary sums obtained during this can be negative, so we can either work with the sum of elements with positive signs (we know the total sum S so it’s easy to recalculate) or with all bits in the bitset shifted by S (then it needs to hold 2S+1 bits). The first option’s more efficient. A custom, more dynamic implementation of bitset also lets us skip ranges of temporary sums that are larger than the current \sum_{i=1}^M A_i or too large/small to give a valid value no matter how we choose remaining signs. There’s a lot that can be constant-optimised since many or all elements A_i can be much smaller than S.
TIME COMPLEXITY:
Let S = \sum_{i=1}^N A_i. Sort takes O(N \log N). Then we perform O(N) operations shift/OR on bitsets with size O(S), which takes O(NS) time. Checking valid values takes only O(S) in total, so the resulting time complexity is O(NS) with a good constant factor.