Solução Soma de Subconjuntos

Solução por Rogério Júnior

Para ver o problema original, clique aqui.

Vamos salvar a sequência no array $vetor$ , e depois ordená-lo. Vamos agora processar ordenadamente cada um dos números do vetor. Seja $resp$ o menor inteiro que não conseguimos formar com os elementos que já temos. Antes de processar qualquer elemento, o valor de $resp$ é $1$ , pois não temos elementos para formá-lo.

Agora, para cada elemento, observe o processamento do $i$ -ésimo elemento do array. Se $resp$ é o menor elemento que não podemos formar, então conseguimos formar todas as somas de $1$ a $resp-1$ . Se $vetor[i] > resp$ , então não há como formarmos o valor de $resp$ usando elemento anteriores a $i$ (por definição de $resp$ ) nem com elemento a partir de $i$ (pois serão todos maiores que $resp$ ). Logo não preciso mais processar o resto do vetor e a resposta é $resp$ .

Entretanto, se $vetor[i]<resp$ , consigo formar todos os valores de $resp$ a $vetor[i]+resp-1$ , pois sendo $s$ uma soma qualquer, seja $x=s-vetor[i]$ . Logo para utilizarmos $vetor[i]$ em um subconjunto a fim de obtermos soma $s$ , precisamos formar $x$ com outros, e só conseguimos formar $1 \leq x <resp \Rightarrow resp \leq s < resp+s$ . Logo, o novo valor de $resp$ é $resp+vetor[i]$ e partiremos para a análise do próximo elemento. Segue o código para melhor entendimento:

	// URI - 1690
	// Rogério Júnior
	// O(n log n)

	#include <cstdio>
	#include <algorithm>

	using namespace std;

	#define MAXN 10100

	int t, n, vetor[MAXN];

	int main(){

	scanf("%d", &t);

	// para cada caso
	while(t--){

	scanf("%d", &n);

	// salvo os números em vetor
	for(int i=0; i<n; i++) scanf("%d", &vetor[i]);

	// ordeno os elementos de vetor
	sort(vetor, vetor+n);

	// resp começa com 1
	long long int resp=1;

	// para cada elemento
	for(int i=0; i<n; i++){

	// se ele for maior que resp, não podemos formá-labs
	// e o algoritmo para
	if(vetor[i]>resp) break;

	// caso contrário, atualizamos o valor de resp
	else resp+=vetor[i];
	}

	// no fim, imprimimos o valor de resp
	printf("%lld\n", resp);
	}

	return 0;
	}

view raw

subconjuntos.cpp

hosted with ❤ by GitHub