İ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 :) .

İTÜ IEEE Yazılım Maratonu

İTÜ IEEE kulübü 2 turdan oluşan bir yazılım maratonu düzenliyor. Yarışmanın ilk turu dün gece başladı ve bu gece sona erecek. 2. turunda ise ilk turda ilk 20'ye giren takımlar İTÜ kampüsünde yarışacak.

Sorular Yeditepe SAP Contest'e göre daha eğlenceli. Yine aynı yarışmaya göre test case'leri daha iyi hazırlanmış gibi duruyor.

C ve E soruları güzeldi. Yarışma bittikten sonra burada çözmeye çalışayım.

SAP Code Contest

Ocak ayı içinde Yeditepe Üniversitesi SAP ile birlikte bir kod yarışması düzenledi. Ben de yaşını başını almış bir alaylı competitive programmer olarak şansımı deneyeyim dedim.

6 soruluk ilk tur SAP'nin sitesinden online olarak yapıldı. Çözmek için 5 gün süre vardı. İlk turun soruları (şu an yarışma sitesine erişilemiyor o yüzden hatırlayamıyorum tam olarak) 5 gün sürecek bir yarışmaya göre çok da zor değildi açıkçası. Codeforces falan gibi sitelerden farklı olarak soruları dan diye sormuşlar, öyle hikayeydi geyikti yoktu pek. Bir soruda edge'leri vermiş, bu ağaç balanced mıdır değil midir onu bulun demiş mesela.

İlk turda belirli bir puan alanları da onsite finale davet ettiler. Normalde competitive programming'den gerçekten zevk alan biri olarak diyebilirim ki, bir odaya toplaşıp yarışmak çok daha heyecanlıymış. Burada nispeten daha zor sorular olsa da (haliyle) yine de ilk turdaki gibi çok lafı dolandırmayan sorulardı. 170 max puan üzerinden 156 alıp üniversite öğrencileri arasında 4. oldum. Bir araba eşantiyon ve 2 t-shirt dışında bir şey kazanamadım ama güzel bir tecrübe oldu diyebilirim benim için :).

Bir fotoğraf falan edinebilirsem bir yerlerden (o kadar fotoğraf çekmişler ama kimse bir yerlerden paylaşmadı henüz) buraya da koyarım :).