Skip to Content
CTRL K

Maximum Subsequence

Análisis oficial 

Explicación

Para este problema, se nos dan n≤35n \leq 35 números y hay que hallar una combinación tal que la suma de todos los elementos de esta combinación módulo mm se maximice. Un enfoque naive, es decir, probar las 2352^{35} combinaciones posibles, no es factible. Sin embargo, podemos usar la técnica Meet-In-The-Middle  para reducir la complejidad temporal a 2n22^{\frac{n}{2}}, que sería suficiente para nuestro límite de tiempo.

Primero partimos el arreglo dado en dos mitades de igual longitud. En caso de nn impar, simplemente ponemos un elemento más en la primera mitad. Luego, generamos todas las combinaciones de números de la primera mitad usando una máscara de bits y guardamos los resultados módulo mm en un conjunto ordenado. Para la segunda mitad, también generemos todas las combinaciones. Para cada una de estas combinaciones, la suma máxima es la suma de todos los elementos de esta combinación, current_sumcurrent\_sum, más la suma más grande de una combinación de la primera mitad, left_sumleft\_sum, que sea menor que m−current_summ - current\_sum. Nunca es óptimo elegir un valor mayor que m−current_summ - current\_sum porque de lo contrario el resultado sería left_sum+current_sum−mleft\_sum + current\_sum - m, que es estrictamente menor que current_sumcurrent\_sum.

Implementación

Complejidad temporal: O(2⌈n2⌉⋅n)\mathcal{O}(2^{\lceil \frac{n}{2} \rceil} \cdot n)

#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++) {
		if ((mask >> bit & 1) == 1) {
			current_sum += arr[bit];
			current_sum %= mod;
		}
	}
	return current_sum;
}
 
int main() {
	int n, m;
	cin >> n >> m;
 
	// split the input array into two parts
	vector<int> left_arr((n + 1) / 2);
	vector<int> right_arr(n / 2);
	for (int &i : left_arr) { cin >> i; }
	for (int &i : right_arr) { cin >> i; }
 
	// stores the sums of all combinations from the left_arr modulo m
	set<int> left_sums;
	for (int mask = 0; mask < (1 << left_arr.size()); mask++) {
		left_sums.insert(unmask(mask, left_arr, m));
	}
 
	// the best value from all combinations of left_arr
	int best = *left_sums.rbegin();
	for (int mask = 0; mask < (1 << right_arr.size()); mask++) {
		int current_sum = unmask(mask, right_arr, m);
		/*
		 * a possible new maximum value is the sum of current_sum and the
		 * largest value below m - current_sum from the combinations in left_arr
		 */
		best = max(best, *prev(left_sums.lower_bound(m - current_sum)) + current_sum);
	}
 
	cout << best << endl;
}
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());
 
		int[] arr = Arrays.stream(br.readLine().split(" "))
		                .mapToInt(Integer::parseInt)
		                .toArray();
		// split the input array into two parts
		int[] leftArr = Arrays.copyOfRange(arr, 0, (n + 1) / 2);
		int[] rightArr = Arrays.copyOfRange(arr, (n + 1) / 2, n);
 
		// stores the sums of all combinations from the leftArr modulo m
		SortedSet<Integer> leftSums = new TreeSet<>();
		for (int mask = 0; mask < (1 << leftArr.length); mask++) {
			leftSums.add(unmask(mask, leftArr, m));
		}
 
		// the best value from all combinations of leftArr
		int best = leftSums.last();
		for (int mask = 0; mask < (1 << rightArr.length); mask++) {
			int currentSum = unmask(mask, rightArr, m);
			/*
			 * a possible new maximum value is the sum of currentSum and the
			 * largest value below m - currentSum from the combinations in
			 * leftArr
			 */
			best = Math.max(best, currentSum + leftSums.headSet(m - currentSum).last());
		}
 
		System.out.println(best);
	}
 
	/**
	 * Calculate the sum of all elements in arr, represented by the binary mask,
	 * and take modulo mod.
	 */
	static int unmask(int mask, int[] arr, int mod) {
		int currentSum = 0;
		for (int bit = 0; bit < arr.length; bit++) {
			if ((mask >> bit & 1) == 1) {
				currentSum += arr[bit];
				currentSum %= mod;
			}
		}
		return currentSum;
	}
}
Fundamentos