Bilgisayar Olimpiyatı 2023, 1. Aşama, Soru 7

Ali her birinin üzerinde bir tam sayı yazılı olan kartlarla bir oyun oynuyor. Başlangıçta, n adet kart bir masanın üzerinde yanyana dizili ve açık olarak duruyor ve Ali'nin skoru 0. Ali bir dizi hamle yaparak skorunu artırabilir. Her defasında olası iki hamle arasında seçim yapabiliyor:
a) En soldaki kartı masadan alıp, skorunu sabit bırakmak, veya
b) En soldaki iki kartın üzerindeki sayıların toplamını skoruna ekledikten sonra en soldaki üç kartı masadan almak. (Eğer masada 1 veya 2 kart kaldıysa, Ali (a) hamlesini seçmek zorunda.)
Masada hiç kart kalmadığında oyun bitiyor. Ali'nin amacı oyun sonundaki skorunu maksimize etmek. Ali skorunu maksimize etmek için aşağıdaki özyineli denklemleri kullanıyor.
A[1..n] dizisi masada soldan sağa dizilmiş n kartı temsil etsin. Örneğin A: {7, 3, -2, 1} dizisi toplam n=4 kart ve soldan sağa kartların üzerlerinde 7, 3, -2 ve 1 sayılarının olduğu anlamına geliyor.
Oyuna dizinin j. elemanından sonuncu elemanına kadar olan kartlar ile başlanırsa oyun sonunda elde edilebilecek maksimum skoru F(j) ile gösterirsek:
\[F(n) = 0\]
\[F(n-1) = 0\]
\[F(n-2) = \max(0, A[n-1] + A[n-2])\]
\[F(j) = \max(F(j+1), A[j] + A[j+1] + F(j+3)), \quad 1 \le j \le n-3\]
Bu durumda F(1) oyuna A[1..n] dizisindeki bütün kartlarla başlandığında elde edilebilecek maksimum skoru gösterir. Örneğin A: {2,5,7,3,10,10,1} olduğunda elde edilebilecek maksimum skor F(1) = 5+7+10+10 = 32'dir.
A: {12, -7, 9, -1, 1, 8, 2, 0, 6, -3} olduğunda elde edilebilecek maksimum skor ne olur?

Şıklar:
A) 10 | B) 15 | C) 18 | D) 19 | E) 20

Cevap: E 20

Çözüm:
A dizisi n=10 elemanlıdır. Sırasıyla hesaplanırsa F(10)=F(9)=0, F(8)=max(0, 0+6)=6, F(7)=max(F(8), A[7]+A[8]+F(10))=max(6, 2)=6, F(6)=max(F(7), A[6]+A[7]+F(9))=max(6,10)=10, ve benzer şekilde hesaplamaya devam edilirse F(5)=15, F(4)=15, F(3)=18, F(2)=18, F(1)=20 olur.
En fazla sayıda karşılaştırma 1. basamakta rastgele seçilen uzaylı a’nın (algoritmanın her çağrılışında) A grubundaki en düşük veya en yüksek IQ’ya sahip uzaylı olması durumunda gerçekleşir. Seçilen a’nın grubundaki en yüksek IQ’lu uzaylı olduğu durumu ele alalım. Bu durumda  (A ve B gruplarındaki eleman sayısı n ise) 2. ve 3. basamaklarda a’nın (ve b’nin) solunda oluşan grup (n-1) ve sağında oluşan grup 0 (sıfır) uzaylı içerecektir.
o Algoritma ilk olarak n = 15 için çalıştırılır: 1. basamakta en fazla 15, 2. ve 3. basamaklarda 14’er karşılaştırma işlemi yapar. Oluşan A1, B1 grupları n-1 = 14’er uzaylı içerir. A2, B2 grupları ise boştur. Bu durumda 6. basamakta algoritma sadece boş olmayan (A1, B1) için çalıştırılır.
o n = 14 için: 1. basamakta en fazla 14, 2. ve 3. basamaklarda 13’er karşılaştırma işlemi yapar, yine seçilen a’nın en büyük IQ’ya sahip olduğunu varsaydığımız için oluşan A1, B1 grupları 13’er uzaylı içerir. A2, B2 grupları ise boytur, ve algoritma sadece boş olmayan (A1, B1) için çaltırılır,
o n = 13 için: 1. basamakta en fazla 13, 2. ve 3. basamaklarda 12’şer karşılaştırma işlemi yapar.
o n = 2 için: 1. basamakta en fazla 2, 2. ve 3. basamaklarda 1’er karşılaştırma işlemi yapar. (Verilen algoritma n=2 için de 2. ve 3. basamakları yapmaktadır dolayısıyla 1+1 karşılaştırma işlemi gereksiz de olsa yapılacaktır.)
o n=1 için algoritma çağırılır fakat karşılaştırma işlemi yapmadan 1. Basamakta sonlanır.
Algoritmanın bütününe bakarsak 1. basamaklarda toplam 15+14+...+2 = 119 karşılaştırma işlemi, 2. ve 3. basamaklarda toplam 2x(14+13+...+1) = 210 karşılaştırma işlemi yapılır. Cevap 210+119 = 329 olup A şıkkında verilmiştir.
Hızlı Taşımacılık Şirketi'nde çalışan işçilerin büyük mobilya parçalarını taşımaları gerekiyor. Bir ev taşıma işini koordine eden şirket amiri, büyük mobilyaları birlikte taşıyabilmeleri için işçileri ikili gruplar halinde eşleştirmek istiyor. Her işçinin verimliliği, bir saatte taşıyabileceği toplam ağırlık ile ölçülsün. İki işçiden oluşan bir grubun verimliliği ise iki işçi arasında verimliği daha az olan işçinin verimliliğine eşit olsun. Örneğin, verimliliği 500 olan bir işçi, verimliliği 300 olan başka bir işçiyle eşleştirilirse, gruplarının verimliliği 300 olur. Toplam verimlilik, tüm grupların verimliliklerinin toplamı olsun. Bu taşıma işinde çalışan n işçi olduğunu ve n sayısının bir çift sayı olduğunu varsayalım. Amire n işçinin verimliliklerini gösteren, indisleri 1'den başlayan ve n elemanlı V[1..n] dizisi veriliyor, bu dizinin i. elemanı i. işçinin verimliliğini göstermekte. Amirin amacı işçileri toplam verimliliği maksimize edecek şekilde eşleştirmek.
Amir, işçileri eşleştirmek için şu stratejiyi düşünüyor: Aralarındaki verimlilik farkı en küçük olan iki işçiyi bulup onları eşleştirin. Tüm işçiler eşleştirilene kadar bu işlemi tekrarlayın. Bu stratejinin her zaman verimliliği maksimize etmeyeceğini aşağıdaki V dizilerinden hangisini örnek göstererek ispat edebiliriz?
A) V: {13, 3, 8, 12, 9, 6}
B) V: {1, 1, 2, 2, 3, 3}
C) V: {12, 5, 9, 24, 20, 18}
D) V: {25, 3,4, 22, 10, 15}
E) Hiçbiri
Soruda verilen stratejiye göre toplam verimlilik min(18,20)+min(9,12)+min(5,24) = 32 olur. Fakat eğer işçiler küçükten büyüğe verimlilik sırasına göre sıralanıp, sonra bu sıralamada en küçükten başlayarak ardışık her iki işçiyi eşleştirilecek şekilde bir strateji uygulanırsa (ki bu optimali veren stratejidir) verimlilik min(5,9) + min(12,18) + min(20,24) = 37 olur. Bu durumda 32'den daha iyi bir eşleştirme mümkün olduğu için C şıkkındaki örnek önerilen stratejinin optimal olmadığını ispatlar. Diğer şıklarda soruda önerilen strateji optimal çözümle aynı sonucu verdiğinden karşı örnek olarak kullanılamazlar.
Bu problemi bir çizge ile modelleyelim. Her alt proje bir düğümle temsil edilsin. Bir u alt projesinin v alt projesinden önce tamamlanmış olması gerekiyorsa u düğümünden v düğümüne yönlü bir kenar olsun. a(u,v), u düğümünden v düğümüne giden yönlü kenarın ağırlığını göstersin. u'ya gelen bütün kenarlara ağırlık olarak u'nun süresini atayalım. Öncelikle projenin bitirilebilir olması için bu çizgenin döngüsüz bir çizge olması gerekmektedir, verilen tablo ile oluşturduğumuz çizge döngü içermemektedir. Düğümleri 1'den 9'a kadar şu şekilde numaralandıralım: eğer u'dan v'ye bir kenar varsa u'nun numarası v'ninkinden küçük olsun. Bu numaralama birden fazla şekilde yapılabilir. Örneğin F:1, K:2, A:3, C:4, G:5, E:6, B:7, D:8, H:9 olsun.
[t[i], i. düğümün temsil ettiği alt projenin süresini, s[i] ise i. düğümün temsil ettiği alt projenin bitebileceği en erken zamanı (s[i]. günün sonu) göstersin. Başlangıçta bütün düğümler için s[i]=t[i] olarak atansın. Küçükten büyüğe numara sırasıyla her bir i düğümü ele alalım: i'ye gelen hiç kenar yoksa s[i] değişmez ve bir sonraki düğüm ile devam ederiz. Aksi takdirde, i düğümüne gelen kenarların (u₁,u₂,...uᵢ) numaralı düğümlerden geldiğini düşünelim. Numaralama koşulumuzdan dolayı, her j için uⱼ < i olacağından ve düğümleri numara sırasıyla ele aldığımız için bu aşamada s[uⱼ]'nin son değeri hesaplanmıştır ve s[i]=max (s[uⱼ]+a(u₁,i), s[u₂]+a(u₂,i),...,s[uⱼ]+a(uⱼ,i)) olarak
güncellenir. Sırasıyla i=1,2,...,9 için s[i] değerleri bu şekilde hesaplanmış olur: s[1] = 5, s[2] = 24, s[3] = 15, s[4] = 23, s[5] = 33, s[6]=31, s[7]= 35, s[8]= 36, ve s[9]=56'dır. s[9]=56 değeri 9 numaralı H alt projesinin en erken 56. günün sonunda bitebileceği anlamına gelir. H herhangi başka bir alt projenin önkoşul değildir. Bu durumda en geç tamamlanan alt proje H'dir ve bu büyük projenin de en erken H'nin tamamlanacağı 56. günün sonunda tamamlanabileceğini gösterir.
Bu problem çizgedeki en uzun yol problemi olarak da formüle edilebilir, öyle ki çizgeye ek olarak 0 numaralı bir düğüm eklediğimizi, t[0]=0, ve s[0]=0 olduğunu düşünelim. Orijinal çizgede hiç gelen kenarı olmayan her i düğümüne 0. düğümden gelen bir kenar ekleyelim ve i. düğüme gelen bu yeni kenara da ağırlık olarak i. düğümün süresini atayalım. Örneğin bu sorudaki tablo için 0 numaralı düğümden 1 ve 2 numaralı düğümlere giden, sırasıyla 5 ve 24 ağırlıklarına sahip, birer kenar eklenir. Oluşturduğumuz bu çizgedeki en uzun yolun uzunluğu projenin en erken bitebileceği günü verir. Örneğin bu sorudaki çizge için 0.düğüm ->K->G->D->H en uzun yoldur ve uzunluğu 24+9+3+20=56'dır.