Merhaba Arkadaşlar,

Bu haftaki sorum şu olacak, http://codeforces.com/contest/703/problem/B

Basitce anlatıcak olacaksam Maşka kardeşimiz şehir şehir dolaşan biri. Bu dolaştığı şehirlerden bazıları başkent.
Sehirler birbirine bağlı ve başkentler bütün şehirlere bağlı. Her şehrin bir güzellik değeri var bizden istenen toplam güzellik sayısını bulmamız.

Bir örnek aşağıda görülebilir :

1. şehir 2'ye, 2. şehir 3'e , 3 şehir başkent olduğu için herkese 4 de 1 bağlı.

http://codeforces.com/predownloaded/17/1d/171ddc86762c931ed2d5f9f3b8ebed6d12503783.png

Bu resim şu datadan oluşuyor

4 1 ---> 4 şehir ve 1 tane başkent var
2 3 1 2 ---> Her şehir için güzellik sayısı
3 ----> 1 tane olan başkentin indexi

Benim çözümüm şu oldu , doğru çalışıyor fakat performansı yetersiz olduğundan kabul edilmedi.
Algoritmayı özetliyecek olursam :

1 - Bütün guzellikSayilari 'ni

toplamGuzellikSayisi += guzellikSayilari[i]*guzellikSayilari[i+1];

şeklinde geziyorum çünkü yanyana olan şehirlerin birbirne bağlı olması gerekior

2- Eğer i, başkent ise o zaman

guzellikSayilari[i]*guzellikSayilari[i+1]

yerine bütün diziyi bir daha dolaş ve hepsi ile çarp çünkü başkent herkese bağlı olması gerekiyor.
3- İkinci maddeyi yaparken

if ( k == i || k == i-1 ||  ( k < i && baskentIndexleri.canFind(k)))
	continue;

Gibi bir kontrolle iki kere bağlamanın önüne geçtim.

int toplamGuzellikSayisi = 0;

void main() {

   auto ilkSatir = stdin.readln.strip.split().map!(a => to!int(a));
	auto toplamSehirSayisi    = ilkSatir[0];
   auto toplamBaskentSayisi  = ilkSatir[1];

   auto guzellikSayilari = stdin.readln.strip.split().map!(a => to!int(a));
	auto baskentIndexleri = stdin.readln.strip.split().map!(a => to!int(a) - 1);
	int  enSonBaskentIndeksi = 0;
	for ( int i = 0; i < guzellikSayilari.length; i++) // İkiser ikiser carpma yapamadim
	{
		if ( enSonBaskentIndeksi < toplamBaskentSayisi &&  i == baskentIndexleri[enSonBaskentIndeksi] )
		{
			enSonBaskentIndeksi++;
			for ( int k = 0; k < guzellikSayilari.length; k++) // Filter yapilabilirdi
			{
				if ( k == i || k == i-1 ||  ( k < i && baskentIndexleri.canFind(k)))
					continue;

				toplamGuzellikSayisi += guzellikSayilari[i]*guzellikSayilari[k];
			}
		}
		else if ( i < guzellikSayilari.length -1 )
			toplamGuzellikSayisi += guzellikSayilari[i]*guzellikSayilari[i+1];
	}

	if ( baskentIndexleri[0] != 0 && baskentIndexleri[$-1] != toplamSehirSayisi-1)
		toplamGuzellikSayisi += guzellikSayilari[0]*guzellikSayilari[$-1];

	writeln(toplamGuzellikSayisi);
}

Dediğim gibi algoritma çalıştı ama performansı düşük çıktı ben aklımda daha iyi bir algoritma buldum O(N) ile çalışıcak sizde görebiliyormusunuz?

Şimdi geleyim yapmak isteyip yapamadıklarıma:

1 -

toplamGuzellikSayisi += guzellikSayilari[i]*guzellikSayilari[i+1];

işi for döngüsü yerine aralıklar ile nasıl yapardım.

Yani elimde 1 ,2 ,3 ,4 gibi bir dizi var for döngüsüz 12 + 23 + 34 + 41 nasıl yapabilirim?

2 - Diyelimki yine elimde 1'den 10 kadar bir dizi var ben 6. ve 8. indexleri atmak istiyorum.
Acaba doğru yöntem auto a = chain(dizi[0..6], dizi[7], dizi[8..$]) midir? Acaba biraz kötü durmuyormu?
Drop fonksiyonları gördüğüm kadarıyla sadece baştan atıyor.

Saygılarımla
Erdemdem

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Ben çizge olmadan şöyle bir şey düşündüm(belki farkında olmadan çizge yapıyor olabilirim).

1 - sadece bir for döngüsü ile bir sonraki başkent değilse toplayarak şehirleri dolaş O(N)

2 - Başkent olmayan şehirleri filtrele ve reduce ile toplamlarını bul O(N)

3 - Başkentleri filtrele ve 2. adımda bulunan toplamla çarpıp toplama ekle O(N)

4 - Filtrelenmiş başkentleri toplamını bul ve başkentleri dolaşırak bu toplamla çarp her çarpımda çarpım yapılan başkentin değerini toplamdan çıkar O(N)

Sanıyosam çalışacak bu algoritma benim daha önce yazdığım O(N^3) yerine ~ 4*O(N) olacaktı.

Bu soruların bu yönlerini seviyorum biraz insanı sanki düşündürüyolar bazen.

Saygılarımla
Erdemdem

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Ali Hocam çok sık boğaz etmek gibi olmazsa şu işi yapan bir std fonksiyonu var mıdır döngüsüz?

Alıntı:

Birde dizinin ortasından belirli bir indexlerden çıkarma yapmak istiyorsam bunun en güzel yolu nedir sizce yani range.indexed methodunu tersi gibi birşey varmı? Şu şu index harici elemanların aralığını dön diyecek.

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Bence burada çizge (graph) veri yapısını kullanmak gerekiyor. Verilerden yola çıkarak bağlantılar kurulacak ve çizgenin bütün elemanları ziyaret edilecek.

Sanırım başka türlü yapınca ya belleğe sığmıyoruz (çünkü bütün N kare olası yol için baştan yer ayırmak gereksiz veya bahsettikleri belleğe sığamıyor) ya da algoritma fazla yavaş kalıyor.

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Öyle söyleyince olur gibi geliyor. :)

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Ali Hocam,

Zip&Cycle çözümü gerçekten çok hoş. Kullanırım bunu ben.

2. durumda sanırım ya ben yanlış anlattım yada tam anlayamadım.

   auto kötüİndeksler = [ 1, 42 ];
   filter!(indeks => !kötüİndeksler.canFind(indeks))

Şimdi elimde 50 lik bir dizi var diyelim elemanların değerleride 0 ile 100 arasında random. İsmide "randomDizi" olsun.

   auto kötüİndeksler = [ 1, 42 ];
   randomDizi.filter!(**indeks **=> !kötüİndeksler.canFind(indeks))

Filter elemanların değerine teker teker bakacaktır diye düşünüyorum benim isteğimse indexleri ile filter yapılması.
Acaba filter methoduna bir dizinin elemanlarını değilde elemanlarının indexisini nasıl aktarabilirim sizce.

Saygılar
Erdemdem

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Alıntı (kerdemdemir):

Olur mu hocam. Daha çok yazalım. :)

Alıntı:

Tam onu yapan olduğunu sanmıyorum ama şöyle bir şey çalıştı:

import std.algorithm;
import std.range;

void main() {
   auto a = [ 1, 2, 3, 4 ];

   auto r = zip(a, a.cycle.dropOne)
            .map!(t => t[0] * t[1])
            .sum;
   assert(r == 24);
}

Az farklı olarak:

import std.algorithm;
import std.range;

void main() {
   auto a = [ 1, 2, 3, 4 ];

   auto r = zip(a, a[1..$])
            .map!(t => t[0] * t[1])
            .sum(a[0] * a[$-1]);    // sonuncu terim
   assert(r == 24);
}

Alıntı:

Tam filter'ın işi ama indeks verirsen her seferinde verilen indeksler arasında arama yapacağından O(NxM)'e gider. Derlemeden:

   auto kötüİndeksler = [ 1, 42 ];
   filter!(indeks => !kötüİndeksler.canFind(indeks))

Onun yerine, eğer elemanları baştan başkent diye belirlemişsen:

   filter!(eleman => !eleman.başkent)

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

enumerate olur ama çokuzlu döndürdüğü için bir de map'ten geçirmek gerekiyor.

import std.algorithm;
import std.range;

void main() {
   auto a = [ 1, 7, 42, 100 ];
   auto atlanacaklar = [ 0, 2 ];
   assert(a
          .enumerate
          .filter!(t => !atlanacaklar.canFind(t[0]))
          .map!(t => t[1])
          .equal([ 7, 100 ]));
}

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Bu çözüm ise indexed'i kullanmaya olanak veriyor:

import std.stdio;
import std.algorithm;
import std.range;

void main() {
   auto atlanacaklar = [ 0, 1, 10, 17, 19 ];

   // Bütün indeksler 0..20 aralığında ise
   int baş = 0;
   int son = 20;

   // İşimizi kolaylaştırmak için baş-1'i ve son'u da atlanacak indekslere ekleyelim
   auto kötüler = chain((baş - 1).only, atlanacaklar, son.only);

   // Şimdi dahil edilecek aralıkları iota ile oluşturacağız
   auto r = zip(kötüler.map!(i => i + 1),    // bir sonraki indeks dahil demektir
                kötüler.dropOne)
            .map!(t => iota(t[0], t[1]))
            .joiner;
   writeln(r);

   // Şimdi bu indeksleri .indexed'ten geçirebiliriz
}

Çıktısı:
'
[2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 18]
'
Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]