2022 demo problem analysis
Let's slightly correct the condition of the problem, make it more universal.
Task
You are given a sequence of N natural numbers. All its continuous subsequences are considered, such that the sum of the elements of each of them is a multiple of K. Find among them a subsequence with the maximum sum, determine its length. If there are several such subsequences, indicate the number of elements of the shortest of them in the answer.
Before understanding the algorithm for solving this problem, it is necessary to recall some points from number theory. Namely, division with a remainder.
Any number (
a) can be represented as:
a = c * k + r, where
c - the result of the integer division of the number
a by
k,
r - the remainder of the division of
a by
k. If number a is divisible by k, then r = 0.
Let's say the sum is (s1) some numbers is not a multiple of k. Let's write it in the form s1 = c1 * k + r1. What number must be removed from the given sum so that the sum of the remaining numbers is divisible by k?
Let's represent the number that we will remove in the form a = c * k + r.
Let's write down the difference:
s2 = s1 - a = c1 * k + r1 - (c * k + r) = k * (c1 - c) + (r1 - r).
s2 = k * (c1 - c) + (r1 - r) - the result of this expression will be divided by k if r1-r=0 . Therefore, r1=r. In other words, the sum of s1 and the number a must have the same remainder when divided by k.
This means that in the problem we need to find some subsequence of numbers starting from the first element in series, which has its own prefix, the sum of whose elements, when divided by k, gives the same remainder as the sum of all elements of the subsequence. In this case, the sum of the elements of the prefix must be minimal, and the sum of the elements of the subsequence must be maximum. Then their difference will give us the desired maximum amount.
The sum of elements will be minimal if it has the least number of elements (since there are only natural numbers in the sequence), maximum if it has the most elements.
Algorithm
1) With each new read number, increase the sum of all elements of the sequence (s). It is also necessary to calculate the remainder after dividing by k the given sum will have: r = s % k.
In order for the sum of s to be divisible by k, you need to remove the sum of the elements of your own prefix from it, which has the same remainder when divided by k > that s.
2) If there is no such prefix, then when reading the number, we received this prefix, and we cannot determine the desired sequence. Let's store the sum of this prefix in an array (prefix[r]), its length in another array (mn_size). The prefix length is equal to the number of the read number (when counting from 1): mn_size[r] = 1.
3) If there is such a prefix in the array, then we can calculate the sum of the desired sequence, as s - prefix[x % k]. The length of such a sequence will be equal to i - mn_size[n % k].
4) When calculating the desired amount, it must be checked for the maximum value and, in case of equality with the maximum value, check the length so that it turns out to be the minimum as a result.
Try to implement this algorithm yourself.