Module: rencontrer dans le milieu


Problem

1 /5


Sous-séquence maximum modulo

Theory Click to read/hide

Meet-in-the-middle
Meet-in-the-middle – un moyen d'optimiser solutions, qui consiste à diviser le problème d'origine en deux moitiés, à résoudre chacune indépendamment, puis à obtenir une solution au problème d'origine en combinant les solutions des moitiés.

Par conséquent, il est logique d'utiliser meet-in-the-middle si deux conditions sont remplies.
1) Le temps nécessaire pour résoudre la moitié du problème est asymptotiquement inférieur au temps nécessaire pour résoudre l'ensemble du problème.
2) En résolvant des demi-problèmes, on peut obtenir des solutions à l'ensemble du problème d'origine et, en même temps, asymptotiquement plus rapidement qu'en résolvant simplement l'ensemble du problème.
 
Exemple
Soit quatre tableaux d'entiers A, B, C et D. Il est nécessaire de sélectionner exactement un nombre dans chaque tableau pour que la somme de ces nombres soit égale à zéro. Vous pouvez utiliser une solution naïve, à savoir simplement énumérer toutes les options possibles. Cela fonctionnera pour O(n4).

Cependant, nous pouvons utiliser meet-in-the-middle.
Notez que a + b + c + d = 0 est équivalent à (a + b) = -(c + d).
Divisons la tâche en deux moitiés, à savoir, dans la première moitié, nous n'utiliserons que les tableaux A et B, et dans la seconde moitié seulement C et D.
Parcourons toutes les options (a + b) possibles dans la première moitié et stockons toutes les valeurs dans une table de hachage (unordered_map, HashMap ou similaire. ). Cela fonctionne en O(n2).
Nous allons maintenant parcourir toutes les options possibles (c + d) dans la seconde moitié. Lors de l'examen d'une certaine option, nous vérifierons s'il existe une valeur dans la table de hachage associée à la somme actuelle du signe opposé (nous avons ensuite trouvé deux inverses qui s'additionnent à zéro). Cette partie fonctionne également en O(n2).
Nous n'avons pas de phase de "fusion de réponses" séparée ici ; dans l'un, nous l'avons fait au cours de la résolution de chacune des moitiés. La plupart des tâches auront une situation similaire.
Nous avons abouti à une solution en O(n2) en utilisant meet-in-the-middle.

Il convient de noter que meet-in-the-middle est le plus souvent utilisé lors de l'optimisation de solutions exponentielles, ce qui affecte considérablement le temps d'exécution.

Problem

Étant donné un tableau A composé de n entiers positifs et d'un nombre m. Sélectionnez la séquence de positions B 1, B2, ..., Bk (1 <= B1 < B2 < ... < Bk <= n) tel que   ; \((\sum_{i=1}^{k} A_{B_i}) mod \; m\) était le maximum (c'est-à-dire , de sorte que le reste de la division de la somme des éléments de la sous-séquence par le nombre m est le maximum possible). La séquence sélectionnée peut être vide.
Calculez la valeur maximale possible de \((\sum_{i=1}^{k} A_{B_i}) mod \; m\).

Entrée
La première ligne contient deux entiers n et m (1 <= n <= 35, 1 <= m <= 109). La deuxième ligne contient n entiers A1, A2< /code >, ..., An (1 <= Ai <= 109 )< br />
Mentions légales
Sortez un nombre - la valeur maximale \((\sum_{i=1}^{k} A_{B_i}) mod \; m\)

 
Exemples
# Entrée Sortie
1 4 4
5 2 4 1 		3
2 3 20
199 41 299 		19
 
Explications
Dans le premier exemple, vous pouvez choisir B = {1, 2}. (A1 + A2) mod m = (5 + 2) % 4 = 3.
Dans le deuxième exemple, vous pouvez sélectionner B = {3}.

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!