Forum: D Programlama Dili RSS
Maşka ile şehir şehir dolaşmaca
kerdemdemir #1
Üye Eyl 2013 tarihinden beri · 53 mesaj
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Konu adı: Maşka ile şehir şehir dolaşmaca
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ı.

[Resim: 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 1*2 + 2*3 + 3*4 + 4*1 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 mesaj kerdemdemir tarafından değiştirildi; zaman: 2016-08-04, 12:21.
acehreli (Moderatör) #2
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4389 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
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
kerdemdemir #3
Üye Eyl 2013 tarihinden beri · 53 mesaj
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
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
acehreli (Moderatör) #4
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4389 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Öyle söyleyince olur gibi geliyor. :)

Ali
kerdemdemir #5
Üye Eyl 2013 tarihinden beri · 53 mesaj
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
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?

1 ,2 ,3 ,4 gibi bir dizi var for döngüsüz 1*2 + 2*3 + 3*4 + 4*1 nasıl yapabilirim? 

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.
acehreli (Moderatör) #6
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4389 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
kerdemdemir:
sık boğaz etmek gibi olmazsa

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

şu işi yapan bir std fonksiyonu var mıdır döngüsüz?

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);
}

Şu şu index harici elemanların aralığını dön diyecek.

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
kerdemdemir #7
Üye Eyl 2013 tarihinden beri · 53 mesaj
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
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!([b]indeks [/b]=> !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
acehreli (Moderatör) #8
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4389 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
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
acehreli (Moderatör) #9
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4389 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
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
Doğrulama Kodu: VeriCode Lütfen resimde gördüğünüz doğrulama kodunu girin:
İfadeler: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Özel Karakterler:
Bağlı değilsiniz. · Şifremi unuttum · ÜYELİK
This board is powered by the Unclassified NewsBoard software, 20100516-dev, © 2003-10 by Yves Goergen
Şu an: 2017-03-23, 11:22:57 (UTC -07:00)