Authors of the problem: | Igor Barenblat, Matviy Aslandukov |
Prepared by: | Igor Barenblat, Matviy Aslandukov |
Analysis written by: | Matviy Aslandukov |
Let us introduce the following notations:
x = \max\limits_{i=1}^n a_i;
N = \sum\limits_{i=1}^T n_i, where n_i is the value of in the -th test case;
X = \max\limits_{i=1}^T x_i, where x_i is the value of in the -th test case;
is the minimum possible number of strange subsequences among the formed.
Block 1 (k = 1).
There is a unique way to split the array into one subsequence. To find the number of strange subsequences among the one formed, it is sufficient to check whether the sum of the elements of the array is a prime number — this can be done using a standard algorithm in O(\sqrt{s}), where s = \sum_{i=1}^n a_i \leq nx.
The complexity of processing one test case is O(n + \sqrt{nx}).
The complexity of processing all test cases is O(N + N \sqrt{X}).
Blocks 2, 3, 4, 5, 6, 7, 8.
To solve the next blocks, we will prove two auxiliary lemmas.
Lemma 1.
Statement. Let q = n - k. Consider the following process:
Create subsequences, where the -th initially consists of one element a_i.
Perform "merge" operations: during each operation, select two specific subsequences and merge them into one.
Then the problem of splitting the array into non-empty subsequences is equivalent to the problem of merging single-element subsequences using the operations described above.
Proof. Indeed, during one operation, the number of subsequences decreases by 1, and thus after performing operations, the number of subsequences will equal n - q = n - n + k = k. It is also easy to notice that any partition can be formed using the operations described above: for this, during the execution of the next operation, it is necessary to select two arbitrary subsequences whose elements belong to one corresponding partition.
Lemma 2.
Statement. ans \geq n - 2q.
Proof. Indeed, in the process described above, there were initially strange subsequences, and each "merge" operation decreased the number of strange subsequences by at most 2. Therefore, after performing any operations, there should still be at least (n - 2q) strange subsequences remaining.
Block 6 (2 k \geq n + 1).
Since k = n - q, we have 2 \cdot (n - q) \geq n + 1 \Rightarrow n - 2q \geq 1. In this case, it is always possible to form the answer with exactly (n - 2q) strange subsequences, which is the optimal answer according to the second lemma. Specifically, during the execution of the next "merge" operation, we will select two single-element subsequences with the same parity of elements. It is easy to see that this can always be done:
For odd , there is an even number of either even or odd elements, so at most one element can remain unpaired, which corresponds to the condition (n - 2q) \geq 1.
For even , at most two elements can remain unpaired (one even, the other odd), which corresponds to the condition (n - 2q) \geq 2, which holds since (n - 2q) is an even number and (n - 2q) \geq 1.
Since the sum of two numbers with the same parity is an even number greater than two, as a result of the "merge," instead of two strange subsequences, one non-strange subsequence will be formed. Thus, each operation will decrease the number of strange subsequences by 2, resulting in ans = n - 2q.
The complexity of processing all test cases is .
Blocks 2, 3, 7.
Before processing all test cases, we will calculate the auxiliary array isPrime[1..2X] (isPrime[1..10X] in the third block), where isPrime[i] indicates whether the number is prime. This can be done in O(X \log X) using the "Sieve of Eratosthenes" algorithm.
Block 2 (n \leq 4).
With solutions for the first and sixth blocks, we only need to consider the case n = 4, k = 2, since for all other cases at least one of the conditions 2k \geq n + 1, k = 1 holds.
For n = 4, k = 2, it is sufficient to consider only cases where both subsequences consist of two elements. This can be done by iterating over one of the three elements that will be in the subsequence along with . If in any of the three cases there are no strange subsequences (this can be checked using the isPrime array), then ans = 0. Otherwise, among these cases, we need to find any with one strange subsequence. Such a case will always exist, as in an array of length 4 there is a pair of elements with the same parity (and thus their sum is not a prime number). Therefore, there is no need to consider cases where one subsequence consists of one element and the other consists of three, as there will be guaranteed to be at least one strange subsequence (which consists of one element that is a prime number).
Without solutions for the first and sixth blocks, we can separately consider all possible combinations of values , , and solve the problem for each of them separately by iterating through all necessary options for forming subsequences.
The complexity of processing all test cases is O(X \log X + N).
Block 3 (T \leq 20, n \leq 10).
In this block, it is sufficient to iterate through all possible partitions of the array into subsequences. Specifically, any partition can be defined using an array of length , where indicates the number of the subsequence to which belongs.
To ensure that the partition is uniquely defined by the array , it is sufficient to consider only such where ids[1] = 1 and 1 \leq ids[i] \leq (\max\limits_{j=1}^{i-1} ids[j] + 1) for i > 1. Indeed, since the order of subsequences does not matter, without loss of generality, we can assume ids[1] = 1, and for each subsequent , the -th element will either belong to a subsequence that has already encountered some previous element of the array (then 1 \leq ids[i] \leq \max\limits_{j=1}^{i-1} ids[j]), or will be the leftmost element of a new subsequence (then without loss of generality, we can assume ids[i] = \max\limits_{j=1}^{i-1} ids[j] + 1).
All partitions can be iterated through using recursive generation of the array . For example, the following code in Python3 iterates through and counts the number of partitions of an array of length 10:
def countPartitions(ids):
if len(ids) == 10:
return 1
return sum(countPartitions(ids + [id]) for id in range(1, max(ids) + 2))
print(countPartitions([1]))Experimentally, it can be observed that for n = 10, the number of partitions C = 115975. For each of them with a total number of subsequences in the partition, we can count the number of strange subsequences using the isPrime array and select the partition with the minimum number.
The complexity of processing all test cases is O(X \log X + C \cdot N).
Blocks 4, 5, 7, 8.
For these blocks, a solution will be provided for 1 < k, 5 \leq n and 2 k < n + 1 \Rightarrow 2 k \leq n \Rightarrow n \leq 2q. If these conditions are not met, see the solutions for blocks 1, 2, and 6.
Block 4 ( is even, a_i > 2).
Since all a_i > 2, all elements of the array are odd. Since q \geq \frac{n}{2}, we will first split all elements into pairs, thus performing \frac{n}{2} "merge" operations, and making all subsequences non-strange, since the sums of their elements will be even numbers greater than two. After that, we will have to perform (q - \frac{n}{2}) "merge" operations, which can be done arbitrarily, since the sum of any two even numbers is an even number. The number of strange subsequences in the result will be zero, which is obviously the minimum possible number.
The complexity of processing all test cases is .
Blocks 5, 7, 8.
To solve the next blocks, we will prove an auxiliary lemma.
Lemma 3.
Statement. Among five prime numbers, it is always possible to find three numbers whose sum is divisible by 3 and is not a prime number.
Proof. Notice that the sum of any three prime numbers exceeds 3, and thus this sum is not a prime number if it is divisible by 3. Now we will prove that it is possible to find three numbers whose sum is divisible by 3. Suppose this is not the case. Consider the remainders when dividing all given numbers by 3. If any remainder occurs at least 3 times, then the sum of the three corresponding numbers will be divisible by 3, which by assumption is impossible. Also, if all remainders (0, 1, 2) occur at least once, then the sum of the three corresponding numbers will be divisible by 3, which by assumption is impossible. This means that the array of remainders contains only two different numbers, each of which occurs at most twice, and therefore the total length of the array does not exceed 4. We have reached a contradiction, as the lemma was proven for five numbers.
Block 5 ( is odd, a_i > 2).
Since is an integer, for odd , the inequality q \geq \frac{n}{2} can be strengthened: q \geq \frac{n + 1}{2}. Since n \geq 5, according to the third lemma, among the first five elements of the array , we can find a triplet with a sum that is not divisible by 3. We will find such a triplet by exhaustively checking all C_5^3 = 10 triplets and merge the corresponding elements into one subsequence, performing two "merge" operations. The remaining (n - 3) elements will be split into pairs arbitrarily, performing \frac{n - 3}{2} "merge" operations. After these (2 + \frac{n - 3}{2} = \frac{n + 1}{2}) "merge" operations, all subsequences will be non-strange, and only the first will have an odd sum of elements.
Since k>1, having only one non-strange subsequence with an odd sum and the rest non-strange subsequences with even sums, the final c = (q - \frac{n+1}{2}) "merge" operations can be spent on merging (c+1) subsequences with even sums into one subsequence also with an even sum. The number of strange subsequences in the result will be zero, which is obviously the minimum possible number.
The complexity of processing all test cases is .
Block 8 ( is odd).
Similarly to the fifth block, here the inequality q \geq \frac{n+1}{2} will hold.
We will gradually consider all possible "types" of the array :
The number of twos in the array is odd.
Then the number of odd elements in the array is even. We will leave one two in a separate single-element subsequence and use \frac{n-1}{2} "merge" operations to split the remaining (n - 1) elements of the array into pairs: even elements with even, odd with odd. We will use an additional "merge" operation to merge the single-element subsequence with the two with any other subsequence. After these (1 + \frac{n - 1}{2} = \frac{n + 1}{2}) "merge" operations, all subsequences will be non-strange and will have even sums of elements. The final (q - \frac{n+1}{2}) "merge" operations can be done similarly to the final part of the solution of the fifth block, resulting in zero strange subsequences in the result.
The number of twos in the array is even.
Then the number of odd elements in the array is odd. We will try to find a triplet of odd elements with a sum that is divisible by 3 (this can be done similarly to block 5):
If such a triplet is found, we will merge the corresponding elements into one subsequence, performing two "merge" operations. We will perform \frac{n - 3}{2} "merge" operations to split the remaining (n - 3) elements of the array into pairs: even elements with even, odd with odd. After these (2 + \frac{n - 3}{2} = \frac{n + 1}{2}) "merge" operations, all subsequences will be non-strange, and only the first will have an odd sum of elements. The final (q - \frac{n+1}{2}) "merge" operations can be done similarly to the final part of the solution of the fifth block, resulting in zero strange subsequences in the result.
If such a triplet is not found, it follows from the third lemma that the number of odd elements does not exceed 3, and thus the number of twos is at least 2. We will consider two cases:
Among the odd elements, there is some element x \neq 3. We will leave and two twos in separate single-element subsequences. We will perform \frac{n - 3}{2} "merge" operations to split the remaining (n - 3) elements of the array into pairs: even elements with even, odd with odd. Since is a prime number greater than three, can only have two possible remainders when divided by 3:
x \mod 3 = 2, meaning (x + 4) is divisible by 3. We will perform two "merge" operations to merge the single-element subsequences into one: [x, 2, 2].
x \mod 3 = 1, meaning (x + 2) is divisible by 3. We will perform one "merge" operation to create a two-element subsequence: , and a second operation to merge the last two with any other from the first \frac{n - 3}{2} pairs.
After these (2 + \frac{n - 3}{2} = \frac{n + 1}{2}) "merge" operations, all subsequences will be non-strange, and only one will have an odd sum of elements. The final (q - \frac{n+1}{2}) "merge" operations can be done similarly to the final part of the solution of the fifth block, resulting in zero strange subsequences in the result.
All odd elements are equal to three. This means that in the array there is only one odd element, as otherwise a triplet with a sum divisible by 3 would have been found in the previous step ((3+3+3) \mod 3 = 0). In other words, a = [2, 2, \ldots, 2, 2, 3]. We will consider two cases:
q = \frac{n + 1}{2}. In this case, at least one of the formed subsequences will be strange: either a subsequence with a triplet (, , [3, 2, 2]), or a single-element subsequence (such will always be found if the subsequence with the triplet consists of at least four elements).
We will perform \frac{n - 1}{2} "merge" operations to split all (n - 1) twos into pairs, and one more operation to merge and . We will obtain a partition with one strange subsequence.
q > \frac{n+1}{2} \Rightarrow q \geq \frac{n+3}{2}. In this case, n \geq 7, since for n = 5 the only possible value is q = \frac{n+3}{2} + 1 = 4, which has already been considered separately in the case k = n - q = 5 - 4 = 1.
We will merge the last four elements into the subsequence [2, 2, 2, 3], performing three "merge" operations. We will merge three twos into the subsequence [2, 2, 2], performing two "merge" operations. We will perform \frac{n - 7}{2} "merge" operations to split the remaining (n - 7) twos into pairs. After these (5 + \frac{n - 7}{2} = \frac{n + 3}{2}) "merge" operations, all subsequences will be non-strange, and only one of them will have an odd sum of elements. The final (q - \frac{n+3}{2}) "merge" operations can be done similarly to the final part of the solution of the fifth block, resulting in zero strange subsequences in the result.
The complexity of processing all test cases is .
Block 7 ( is even).
Recall that here we consider the solution for 1 < k, 5 \leq n, q \geq \frac{n}{2}. Since is even, the inequality n \geq 5 can be strengthened: n \geq 6.
We will gradually consider all possible "types" of the array :
The number of twos in the array is even.
Then the number of odd elements in the array is even. We will use \frac{n}{2} "merge" operations to split all elements of the array into pairs: even elements with even, odd with odd. After these \frac{n}{2} "merge" operations, all subsequences will be non-strange and will have even sums of elements. The final (q - \frac{n}{2}) "merge" operations can be done similarly to the final part of the solution of the fifth block, resulting in zero strange subsequences in the result.
The number of twos in the array is odd.
Then the number of odd elements in the array is odd. We will try to find an odd element such that (x+2) is not a prime number (this can be checked using isPrime[x + 2]):
If such an element is found, we will merge it with the two into one subsequence , performing one "merge" operation. We will perform \frac{n - 2}{2} "merge" operations to split the remaining (n - 2) elements of the array into pairs: even elements with even, odd with odd. After these (1 + \frac{n - 2}{2} = \frac{n}{2}) "merge" operations, all subsequences will be non-strange, and only the first will have an odd sum of elements. The final (q - \frac{n}{2}) "merge" operations can be done similarly to the final part of the solution of the fifth block, resulting in zero strange subsequences in the result.
If such an element is not found, it means that for all odd elements , the condition (x+2) \mod 3 \neq 0 \Rightarrow x \mod 3 \neq 1 holds. We will consider two cases:
q = \frac{n}{2}. In this case, at least one of the formed subsequences will be strange: either a single-element subsequence (which is always strange), or a subsequence , where x \neq 2 (such will always be found, since there is an odd number of twos, so at least one two must merge with an odd element ).
We will merge the two with any odd element and perform another \frac{n - 2}{2} "merge" operations to split the remaining (n - 2) elements of the array into pairs: even elements with even, odd with odd. We will obtain a partition with one strange subsequence.
q > \frac{n}{2} \Rightarrow q \geq \frac{n+2}{2}. First, we will perform the first \frac{n+2}{2} "merge" operations depending on the "type" of the array :
In the array , there are at least three twos and one three. We will merge these four elements into the subsequence [2, 2, 2, 3], performing three "merge" operations. We will perform \frac{n - 4}{2} "merge" operations to split the remaining (n - 4) elements of the array into pairs: even elements with even, odd with odd. The number of "merge" operations performed is (3 + \frac{n - 4}{2} = \frac{n + 2}{2}).
In the array , there are at least five twos. In this case, for each odd element , the condition x \mod 3 = 2 holds (otherwise, the previous case would have been considered).
We will merge two twos and any odd element into the subsequence [2, 2, x], performing two "merge" operations. We will merge three twos into the subsequence [2, 2, 2], performing two "merge" operations. We will perform \frac{n - 6}{2} "merge" operations to split the remaining (n - 6) elements of the array into pairs: even elements with even, odd with odd. The number of "merge" operations performed is (2 + 2 + \frac{n - 6}{2} = \frac{n + 2}{2}).
In the array , there are exactly three twos. Since n \geq 6, there are at least three odd elements in the array . Similarly to the previous case, for each odd element , the condition x \mod 3 = 2 holds.
We will merge three twos into the subsequence [2, 2, 2], performing two "merge" operations. We will merge any three odd elements , , into the subsequence [x, y, z], performing two "merge" operations (their sum will be divisible by 3, since x \mod 3 = y \mod 3 = z \mod 3 = 2). We will perform \frac{n - 6}{2} "merge" operations to split the remaining (n - 6) elements of the array into pairs: even elements with even, odd with odd. The number of "merge" operations performed is (2 + 2 + \frac{n - 6}{2} = \frac{n + 2}{2}).
In the array , there is exactly one two. Since n \geq 6, there are at least five odd elements. According to the third lemma, among them we can find three elements whose sum is divisible by 3.
We will find them by exhaustively checking all C_5^3 = 10 triplets and merge the corresponding elements into one subsequence, performing two "merge" operations. We will merge the two with two other odd elements , into the subsequence [2, x, y], performing two "merge" operations. We will perform \frac{n - 6}{2} "merge" operations to split the remaining (n - 6) elements of the array into pairs: even elements with even, odd with odd. The number of "merge" operations performed is (2 + 2 + \frac{n - 6}{2} = \frac{n + 2}{2}).
After these \frac{n + 2}{2} "merge" operations, all subsequences will be non-strange, and only one of them will have an odd sum of elements. The final (q - \frac{n+2}{2}) "merge" operations can be done similarly to the final part of the solution of the fifth block, resulting in zero strange subsequences in the result.
The complexity of processing all test cases is O(X \log X + N).
Author's implementation
For a better understanding of the solution described above, the author's implementation in Python3 can be found at the link https://ideone.com/owiZT3.