Official Analysis

Explanation

For this problem, we are given $n \leq 35$ numbers and have to find a combination such that the sum of all elements in this combination modulo $m$ is maximized. A naive approach, i.e. trying out all $2^{35}$ possible combinations, is not feasible. However, we can use the Meet-In-The-Middle Technique to reduce the time complexity to $2^{\frac{n}{2}}$, which would be enough for our time bound.

We first split the given array into two halves that are equally long. In case of odd $n$, we just put one more element into the first half. Then, we generate all combinations of numbers in the first half by using a bit mask and save the results modulo $m$ in a sorted set. For the second half, let's also generate all combinations for them. For each of these combinations, the maximal sum is the sum of all elements in this combination, $current\_sum$, plus the largest sum of a combination of the first half, $left\_sum$, which is less than $m - current\_sum$. It is never optimal to choose a value larger than $m - current\_sum$ since otherwise the result would be $left\_sum + current\_sum - m$, which is strictly less than $current\_sum$.

Implementation

Time Complexity: $\mathcal{O}(2^{\lceil \frac{n}{2} \rceil} \cdot n)$

Copy
#include <bits/stdc++.h>
using namespace std;

/**
 * Calculate the sum of all elements in arr, represented by the binary mask, and
 * take modulo mod.
 */
int unmask(int mask, const vector<int> &arr, int mod) {
	int current_sum = 0;
	for (int bit = 0; bit < arr.size(); bit++) {

Copy
import java.io.*;
import java.util.*;

public class MaxSubseq {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());