Module: ortada buluşmak


Problem

1 /5


Modulo maksimum alt dizisi

Theory Click to read/hide

Ortada Buluşma
Meet-in-the-middle - optimize etmenin bir yolu orijinal problemi ikiye bölmek, her birini bağımsız olarak çözmek ve daha sonra bu yarıların çözümlerini birleştirerek orijinal probleme bir çözüm elde etmekten oluşan çözümler.

Buna göre, iki koşul karşılanırsa ortada buluş kullanmak mantıklıdır.
1) Problemin yarısını çözmek için gereken süre, asimptotik olarak tüm problemi çözmek için gereken süreden daha azdır.
2) Yarım problemleri çözerek, orijinal problemin tamamına çözümler elde edilebilir ve aynı zamanda asimptotik olarak tüm problemi çözmekten daha hızlıdır.
 
Örnek
A, B, C ve D tamsayılarından oluşan dört dizi olsun. Bu sayıların toplamının sıfıra eşit olması için her diziden tam olarak bir sayı seçmek gerekir. Safça bir çözüm kullanabilir, yani tüm olası seçenekleri sıralayabilirsiniz. Bu, O(n4) için çalışacak.

Ancak, ortada buluş kullanabiliriz.
a + b + c + d = 0'ın (a + b) = -(c + d)'ye eşdeğer olduğuna dikkat edin.
Görevi ikiye bölelim, yani ilk yarıda sadece A ve B dizilerini, ikinci yarıda sadece C dizilerini kullanacağız. > ve D.
İlk yarıdaki tüm olası (a + b) seçeneklerini tekrarlayalım ve tüm değerleri bir karma tabloda (unordered_map, HashMap veya benzeri. ). Bu, O(n2) içinde çalışır.
Şimdi ikinci yarıda tüm olası (c + d) seçeneklerini tekrarlayacağız. Belirli bir seçeneği göz önünde bulundururken, hash tablosunda karşıt işaretin mevcut toplamıyla ilişkili bir değer olup olmadığını kontrol edeceğiz (sonra toplamı sıfıra ulaşan iki karşılıklı bulduk). Bu kısım O(n2) içinde de çalışır.
Burada ayrı bir "yanıt birleştirme" aşamamız yok; birinde, bunu her bir yarım için çözme sürecinde yaptık. Çoğu görevde benzer bir durum olacaktır.
meet-in-the-middle kullanarak O(n2) içinde bir çözüm bulduk.

meet-in-the-middle'ın çoğunlukla, çalışma süresini önemli ölçüde etkileyen üstel çözümleri optimize ederken kullanıldığını belirtmekte fayda var.

Problem

n pozitif tam sayı ve m sayısından oluşan bir A dizisi verildi. Konumların sırasını seçin B 1, B2, ..., Bk > (1 <= B1 < B2 < ... < Bk <= n) öyle ki   ; \((\sum_{i=1}^{k} A_{B_i}) mod \; m\) maksimumdu (yani , böylece alt dizinin öğelerinin toplamının m  sayısına bölünmesinden kalan, mümkün olan maksimum sayıdır). Seçilen dizi boş olabilir.
\((\sum_{i=1}^{k} A_{B_i}) mod \; m\)'nin olası maksimum değerini hesaplayın.

Girdi
İlk satır iki tam sayı n ve m içerir (1 <= n <= 35, 1 <= m <= 109). İkinci satır, n tam sayılarını içerir A1, A2, ..., An (1 <= Ai <= 109 )< br />
Künye
Çıktı bir sayı - maksimum değer \((\sum_{i=1}^{k} A_{B_i}) mod \; m\)

 
Örnekler
 
Açıklamalar
İlk örnekte B = {1, 2} seçebilirsiniz. (A1 + A2) mod m = (5 + 2) % 4 = 3.
İkinci örnekte, B = {3} öğesini seçebilirsiniz.

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!

# Girdi Çıktı
1 4 4
5 2 4 1 		3
2 3 20
199 41 299 		19