İTÜYM Finalinden Bir Soru

Geçen haftasonu ITU IEEE Yazılım Maratonu finali vardı. Etkinlik 2 gün sürdü ve her gün ayrı ayrı şirketlerin hazırladığı 3'er soru soruldu. Ben bir kez daha şunu farkettim ki başlangıçta her ne kadar soruyu çözen algoritmayı bulmak daha zor görünse de asıl zor olan hatasız kod yazabilmek. Ya da ben çok iyi bir günümde değildim bilmiyorum :) . 20 takım arasından 10. oldum, seneye daha iyi yaparım artık. Takım arkadaşım olmadan en azından sonuncu olmadım diye kendimi avutuyorum :) .

Yarışmada sorulan ve benim kodunu düzgün yazamadığım için kaçırdığım güzel bir soru vardı: Elimizde 3 harften (A, B ve C olsun) oluşan bir alfabe ve bu alfabeden türetilen rastgele kelimeler var. Kelimeler arasında ise şöyle bir ilişki var;

- A ile biten bir kelimeden sonra B ile başlayan bir kelime gelmeli
- B ile biten bir kelimeden sonra C ile başlayan bir kelime gelmeli
- C ile biten bir kelimeden sonra A ile başlayan bir kelime gelmeli

Elimizdeki kelime dağarcığını kullanarak \(K (K \leq 10^{18})\) kelime uzunluğunda bir yazı yazmak istiyoruz. Kaç farklı yazı yazabiliriz?

Her kelime çeşidini (A,B,C ile başlayan ve A,B,C ile biten toplam 9 olasılık) bir düğüm olarak düşünürsek  aslında soruda sorulmak istenen şey şu; herhangi bir düğümden başlayarak herhangi başka bir düğüme, aradaki her düğümü istediğimiz kadar ziyaret ederek \(K\) adımda kaç farklı şekilde varabiliriz? Bir düğümden başlayarak diğer bir düğüme, her düğümü istediğimiz kadar ziyaret etme işine graph theory'de walk (yürüyüş) diyoruz. Belirli bir uzunluktaki yürüyüşlerin sayısını bulmak için ise komşuluk matrisinin şu özelliğinden faydalanacağız;

\(A\) komşuluk matrisi olmak üzere, \(A^K\) matrisinin \(A_{i,j}\) değeri, \(n_i\) düğümünden \(n_j\) düğümüne yapılan \(K\) uzunluktaki yürüyüşlerin sayısını verir.

O zaman ilk olarak komşuluk matrisini oluşturmamız gerekiyor. İhtiyacımız olan \(3 \times 3\) lük bir komşuluk matrisi, satır indeksi bize kelimenin ilk karakterini, sütun indeksi ise kelimenin son karakteri ile gidebileceğimiz kelime grubunun ilk karakterini verecek. Örneğin A için 0, B için 1 ve C için 2 değerlerini atarsak, "ABAB" kelimesinin satır indeksi, ilk karakter A olduğu için 0, sütun indeksi ise B'den sonra C geleceği için 2 olacak. Her bir kelimenin bu matriste denk geldiği hücreyi bulup bir arttıracağız.

Son olarak ise \(A^K\) değerini hesaplamamız gerekiyor. \(K\)'nın çok büyük olduğunu göz önünde bulundurursak \(A\)'yı art arda \(K\) kez çarpmak iyi bir yöntem değil, onun yerine 2'li üs alma yöntemini kullanabiliriz.

Bu işlem karmaşıklığı \(O(K \times N^3)\)'ten \(O(N^3 \times logK)\)'ya düşürecek. En sonunda yapacağımız işlem ise tüm hücre değerlerini toplamak.

Benim yarışmada yaptığım hata ise, mul fonksiyonunda matrisleri çarparken indeksleri karıştırmak :) .