Nerunun İtmiş Bağlantısı#12447

Nerunun İtmiş Bağlantısı (Həll təhlili)

Məsələnin müəllifi:	Taras Derkach
Hazırlayan:	Taras Derkach
İzah:	Taras Derkach

Həll

Əvvəlcə birləşmənin başlanğıc qiymətini hesablayaq:

(p_{1} \oplus p_{2}) + (p_{2} \oplus p_{3}) + \dots + (p_{n - 1} \oplus p_{n}) .

(p_1 \oplus p_2) + (p_2 \oplus p_3) + \ldots + (p_{n-1} \oplus p_n).

Daha sonra yeni qiymətin özünü deyil, iki yerdəyişmədən sonra mümkün olan maksimum artımı axtaracağıq.

$s$ mövqeyindən başlayan uzunluğu $4$ olan bir parça nəzərdən keçirək.

Bu parçadakı elementləri yenidən düzəndən sonra yalnız bu parçanın ətrafındakı kənarlar dəyişir:

(s - 1, s), (s, s + 1), (s + 1, s + 2), (s + 2, s + 3), (s + 3, s + 4) .

(s-1,s), (s,s+1), (s+1,s+2), (s+2,s+3), (s+3,s+4).

Əgər hansısa kənar massiv sərhədindən kənara çıxdığı üçün mövcud deyilsə, onu sadəcə nəzərə almırıq.

Parçanın uzunluğu $4$ olduğuna görə onun bütün permutasiyalarını yoxlamaq olar. Onların sayı cəmi $4! = 24$ 4! = 24-dür.

Hər başlanğıc mövqeyi $s$ üçün $d e l t a_{s}$ delta_s qiymətini hesablayaq. Bu qiymət yalnız $[s, s + 3]$ [s,s+3] parçasını yenidən düzdükdə alınan maksimum artımdır.

İndi iki parça seçmək lazımdır.

İki hal var.

Birinci hal: parçalar arasında ən azı bir mövqe var.

Əgər birinci parça $i$ mövqeyindən, ikinci parça isə $j$ mövqeyindən başlayırsa və $j - i \geq 5$ j-i \ge 5 olarsa, onların təsir etdiyi kənarlar kəsişmir.

Buna görə ümumi artım belə olur:

d e l t a_{i} + d e l t a_{j} .

delta_i + delta_j.

Maksimumu tez tapmaq üçün $d e l t a_{i}$ delta_i üçün prefiks maksimumlarını saxlayacağıq.

İkinci hal: parçalar yanaşı yerləşir.

Bu, $j = i + 4$ j=i+4 olduğu haldır.

Bu zaman parçalar kəsişmir, lakin onların arasında ortaq bir kənar var:

(i + 3, i + 4) .

(i+3,i+4).

Bu kənar eyni anda hər iki permutasiyadan asılıdır, ona görə sadəcə $d e l t a_{i} + d e l t a_{j}$ delta_i + delta_j toplamaq olmaz.

Bu hal üçün əlavə qiymətləri ayrıca saxlayacağıq.

Hər parça üçün bunları biləcəyik:

parçanın son elementi müəyyən bir element olduqda sol hissənin ən yaxşı qiyməti;
parçanın ilk elementi müəyyən bir element olduqda sağ hissənin ən yaxşı qiyməti.

Sonra iki qonşu parça üçün yalnız birinci parçanın sonunda hansı elementin, ikinci parçanın əvvəlində isə hansı elementin durduğunu yoxlamaq kifayətdir. Belə variantların sayı cəmi $4 \cdot 4$ 4 \cdot 4-dür.

Bundan sonra cavab başlanğıc qiymət ilə tapılmış maksimum artımın cəminə bərabərdir.

Nümunə

Birinci nümunədə $p [1..4]$ və $p [5..8]$ parçalarını seçmək olar.

Yenidən düzəndən sonra massiv belə ola bilər:

[1, 2, 4, 3, 5, 6, 8, 7] .

[1,2,4,3,5,6,8,7].

Onda birləşmənin qiyməti belə olur:

(1 \oplus 2) + (2 \oplus 4) + (4 \oplus 3) + (3 \oplus 5) + (5 \oplus 6) + (6 \oplus 8) + (8 \oplus 7) = 54.

(1 \oplus 2) + (2 \oplus 4) + (4 \oplus 3) + (3 \oplus 5) + (5 \oplus 6) + (6 \oplus 8) + (8 \oplus 7) = 54.

Mürəkkəblik

Uzunluğu $4$ olan hər parça üçün $24$ permutasiyanı yoxlayırıq.

Qonşu parçalar üçün əlavə olaraq $4 \cdot 4$ 4 \cdot 4 variant yoxlayırıq.

Bütün bu ədədlər sabitdir, buna görə həllin ümumi mürəkkəbliyi $O (n)$ -dir.

(p_{1} \oplus p_{2}) + (p_{2} \oplus p_{3}) + \dots + (p_{n - 1} \oplus p_{n}) .

(s - 1, s), (s, s + 1), (s + 1, s + 2), (s + 2, s + 3), (s + 3, s + 4) .

4! = 24

d e l t a_{s}

[s, s + 3]

j - i \geq 5

d e l t a_{i} + d e l t a_{j} .

d e l t a_{i}

j = i + 4

(i + 3, i + 4) .

d e l t a_{i} + d e l t a_{j}

4 \cdot 4

[1, 2, 4, 3, 5, 6, 8, 7] .

(1 \oplus 2) + (2 \oplus 4) + (4 \oplus 3) + (3 \oplus 5) + (5 \oplus 6) + (6 \oplus 8) + (8 \oplus 7) = 54.

4 \cdot 4