Module: الالتقاء في منتصف الطريق


Problem

1 /5


Modulo القصوى اللاحقة اللاحقة

Theory Click to read/hide

لقاء في الوسط
Meet-in-the-middle - وسيلة للتحسين الحلول ، والتي تتمثل في تقسيم المشكلة الأصلية إلى نصفين ، وحل كل منهما على حدة ، ثم الحصول على حل للمشكلة الأصلية من خلال الجمع بين حلول النصفين.
وفقًا لذلك ، من المنطقي استخدام لقاء في الوسط في حالة استيفاء شرطين.
1) الوقت اللازم لحل نصف المشكلة أقل بشكل مقارب من الوقت لحل المشكلة برمتها.
2) من خلال حل نصف المشاكل ، يمكن للمرء الحصول على حلول للمشكلة الأصلية بأكملها ، وفي نفس الوقت ، أسرع بشكل مقارب من مجرد حل المشكلة برمتها.
نبسب ؛
مثال لنفترض أن هناك أربع مصفوفات من الأعداد الصحيحة A و B و C و D . من الضروري تحديد رقم واحد بالضبط من كل مصفوفة بحيث يكون مجموع هذه الأرقام مساويًا للصفر. & nbsp؛ يمكنك استخدام حل ساذج ، وهو ببساطة تعداد جميع الخيارات الممكنة. سيعمل هذا مع O (n 4 ) .

ومع ذلك ، يمكننا استخدام Meet-in-the-middle .
لاحظ أن a + b + c + d = 0 يعادل (a + b) = - (c + d) .
دعنا نقسم المهمة إلى نصفين ، أي في النصف الأول سنستخدم فقط المصفوفات A و B ، وفي النصف الثاني فقط C و D .
دعنا نكرر جميع خيارات (a + b) الممكنة في النصف الأول ونخزن جميع القيم في جدول تجزئة ( unordered_map ، HashMap أو ما شابه). يعمل هذا في O (n 2 ) .
الآن سوف نكرر جميع الخيارات الممكنة (c + d) في النصف الثاني. عند التفكير في خيار معين ، سوف نتحقق مما إذا كانت هناك قيمة في جدول التجزئة مرتبطة بالمجموع الحالي للعلامة المعاكسة (ثم وجدنا مقلدين يصل مجموعهما إلى الصفر). يعمل هذا الجزء أيضًا في O (n 2 ) .
ليس لدينا هنا مرحلة منفصلة " دمج الإجابات " ؛ في أحدهما ، قمنا بهذا أثناء حل كل نصفين. معظم المهام سيكون لها وضع مماثل.
انتهى بنا المطاف بحل في O (n 2 ) باستخدام meet-in-the-middle .

من الجدير بالذكر أن Meet-in-the-middle يُستخدم غالبًا عند تحسين الحلول الأسية ، مما يؤثر بشكل كبير على وقت التشغيل.

Problem

إعطاء مصفوفة A تتكون من n أعداد صحيحة موجبة ورقم m . & nbsp؛ حدد تسلسل المواضع B 1 ، B 2 ، ... ، B k (1 & lt؛ = B 1 & lt؛ B 2 & lt؛ ... & lt؛ B k & lt؛ = n) هكذا & nbsp ؛ & nbsp؛ \ ((\ sum_ {i = 1} ^ {k} A_ {B_i}) mod \؛ m \) & nbsp؛ كان الحد الأقصى (هذا هو ، بحيث & nbsp ؛ ما تبقى من قسمة مجموع عناصر اللاحقة على الرقم m & nbsp ؛ هو أقصى حد ممكن). & nbsp ؛ يمكن أن يكون التسلسل المحدد فارغًا.
احسب أقصى قيمة ممكنة لـ \ ((\ sum_ {i = 1} ^ {k} A_ {B_i}) mod \؛ m \) .

إدخال
يحتوي السطر الأول على عددين صحيحين n و m (1 & lt؛ = n & lt؛ = 35، 1 & lt؛ = m & lt؛ = 10 9 ). & nbsp؛ يحتوي السطر الثاني على n أعداد صحيحة A 1 ، A 2 ، ... ، A n (1 & lt؛ = A i & lt؛ = 10 9 ) < ر />
بصمة
إخراج رقم واحد - الحد الأقصى للقيمة \ ((\ sum_ {i = 1} ^ {k} A_ {B_i}) mod \؛ m \)

نبسب ؛
أمثلة <الجسم>
# إدخال الإخراج
1 4 4
5 2 4 1 		3
2 3 20
299 4199 		19
نبسب ؛
التفسيرات في المثال الأول ، يمكنك اختيار B = {1، 2} . (A 1 & nbsp؛ + A 2 ) mod m = (5 + 2)٪ 4 = 3 .
في المثال الثاني ، يمكنك تحديد 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!