PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Matvii Aslandukov
Developer: Matvii Aslandukov
Editorialist: Matvii Aslandukov
DIFFICULTY: 2788
Before describing the solution for each individual block let’s prove the following lemma: if both players can remove all the elements from the array a using only their own rounds, then the answer is 0. Indeed, in such a case both players can make the sum of the remaining elements in the array a equal to 0 regardless of the actions of the second player. The first player wants to minimize the sum, therefore the answer is not bigger than zero. At the same time, the second player wants to maximize the sum, therefore the answer is not less than zero. Thus the only possible answer is 0.
Subtask 1
In the first subtask two own rounds are enough for each player to remove all the elements: the first player can remove all the numbers that are divisible by b_1 and are not divisible by b_3, and the second player can do the same using b_2 and b_4. Thus by the lemma above the answer is 0 for m > 3. For m \leq 3 you can either recursively solve the problem by considering each possible game scenario, or consider up to 8 cases manually. Time complexity: O(n).
Subtask 2
In the second subtask no additional observations are required. The entire game can be simulated recursively: you can represent the state of the game as a pair (a, pos), where a is an array with remaining elements and pos is a current round. Then at each state of the recursion you can try to make all two possible operations and select the best one. The total number of states is O(2^m) but the total size of all arrays a across all states is only O(nm) due to the fact that each initial element of the array a is contained in exactly m states. Therefore such a solution works in O(2^m+nm). See the following code on \texttt{Python} for a better understanding.
def solve(a, pos):
if pos == len(b):
return sum(a)
na = [[], []]
for x in a:
na[(x % b[pos]) == 0].append(x)
return [min, max][pos % 2](solve(na[0], pos + 1), solve(na[1], pos + 1))
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
print(solve(a, 0))
Subtask 3
In the third subtask you can notice that the majority of O(2^m) states inside the recursion have an empty array a that allows to immediately return 0 as a result:
def solve(a, pos):
if len(a) == 0:
return 0
...
Such optimization gives time complexity O(nm) which is enough for the third subtask.
Subtask 4
In the fourth subtask O(\log n) own rounds are enough for each player to remove all the elements. Indeed, at each round one of the two possible operations removes at least half of all remaining elements, therefore \left \lceil \log_2 n \right \rceil rounds are always enough to remove all the elements. It means that the only difference from the third subtask is that we can just output 0 when m > 100 by the lemma above.
Bonus: what is the maximum value of m where the answer is not equal to zero?