İkinci Aşama Müfredatı

Basit veri yapılar
- Binary Tree
- Heap
- Tree
- Queue
- Stack
- Linked List
Graph teori
- Graph gösterimleri
- DFS & BFS
- Shortest Path(Dijkstra)
- Floyd Warshall
- Minimum Spanning Tree (Kruskal & Prim)
- Topological Sort
- SCC(strongly connected component)
- LCA(lowest common ancestor)
STL kütüphanesi
Dinamik Programalama
- LCS
- Knapsack
- MCP
- LIS (Longest Increasing Subsequence)
- Kadane Algorithm
Greedy Algoritmaları
Sort Algoritmaları
- Merge Sort
- Bubble Sort
- Quick Sort
- Radix Sort
Matematik
- Moduler aritmetik
- GCD&LCM(EBOB&EKOK)
- Asal sayılar
- Çarpanlarına ayırma

Greg and Array

Greg'in N elemanlı bir dizisi ve M tane işlemi var.
Her işlem l, r, d sayılarıyla gösteriliyor.
İşlem ise dizinin l(1 değil, harf olan l). indisinden r. indise kadar olan elemanları d kadar arttırmak.
Greg M tane işlemi bir listeye sırasıyla yazıyor ve ikinci bir işlem biçimi tanımlıyor.
İkinci işlemden de K tane yapacak.
Bu işlem x, y şeklinde gösteriliyor, M işlemlik listedeki x'den y'ye kadar olan işlemleri uygulamamızı sağlıyor.
Greg'in sizden istediği, dizinin K işlemden sonraki hâli.

Girdi Biçimi:

N M K( Hepsinin sınırı 100.000 )
Dizinin N elemanı( Sınır yine 100.000 )
l r d şeklinde M tane işlem( d'nin sınırı 100.000)
x y şeklinde K tane işlem

Çıktı Biçimi:

Tek satırda dizinin son hâli.

Örnek Girdi:

3 3 3
1 2 3
1 2 1
1 3 2
2 3 4
1 2
1 3
2 3

Örnek Çıktı:

9 18 17

________________________________________________________

Link: http://codeforces.com/contest/295/problem/A

________________________________________________________

Çözüm:

Online sorgu içermeyen problemlerde dizide l,r arasını d kadar arttırma işlemini şu şekilde yapabiliriz:
ar[r]+=d;
ar[l-1]-=d;

ar[x] şu demek: x ve solundaki bütün elemanların değerini ar[x] kadar arttırdık.
Diziyi bu şekilde tutarsak en sondan başa doğru her elemanı toplayarak gelince dizinin son halini elde ederiz.

İlk M işlemi bu tarz bir dizi olarak düşünürsek ikinci K işlemi bu M elemanlı dizi üzerinde uygulayabiliriz.
M elemanlı dizinin asıl hâlini bulunca İlk dizimizi de aynı şekilde son hâline getirebiliriz.

Eğer dizideki aralık arttırma işlemleri için Segment Tree kullansaydı problemi online olarak çözmüş olacaktık, fakat zaman karmaşıklığı artacaktı.

________________________________________________________

Çözüm Kodu:

#include <cstdio>
#include <iostream>

#define fi first
#define se second

using namespace std;

typedef pair<int,int> ii;
typedef unsigned long long int ULint;

const int MAXN=100100;

ULint N,M,K;
ULint l[MAXN];
ULint r[MAXN];
ULint t[MAXN];
ULint ar[MAXN];
ULint wr[MAXN];
ULint inc[MAXN];

int main(){

ios_base::sync_with_stdio(false);
cin >> N >> M >> K;

for( int a,i=1 ; i<=N ; i++ ){
cin >> a;
ar[i]+=a;
ar[i-1]-=a;
}

for( int i=1 ; i<=M ; i++ )
cin >> l[i] >> r[i] >> t[i];

for( int a,b,i=1 ; i<=K ; i++ ){
cin >> a >> b;
inc[b]++;
inc[a-1]--;
}

ULint cur=0;

for( int i=M ; i ; i-- ){
cur+=inc[i];
ar[r[i]]+=t[i]*cur;
ar[l[i]-1]-=t[i]*cur;
}

cur=0;

for( int i=N ; i ; i-- ){
cur+=ar[i];
wr[i]=cur;
}

for( int i=1 ; i<=N ; i++ )
cout << wr[i] << ' ';

cout << '\n';
return 0;
}

Random Task

Soru Metni:
Öyle bir n sayısı bulunuz ki n+1,n+2,n+3,...,2*n-1,2*n dizisindeki elemanlardan
kesinlikle m tanesi ikili gösterimlerinde tam olarak k tane bir biti içersin.

Girdi Formatı:
İlk ve tek satırda 2 adet sayı: m ve k(0 ≤ m ≤ 10^18; 1 ≤ k ≤ 64).

Çıktı Formatı:
Tek satırda istenen sayı n. n sayısının 1 ile 10^18 arasında olduğu garanti ediliyor.

Örnek Girdi:
1 1
Örnek Çıktı:
1

Örnek Girdi:
3 2
Örnek Çıktı:
5

Soru: codeforces.com/contest/431/problem/D

Çözüm Metni:

count(x) x sayısı içindeki bir bitleri sayısı k ise 1 değil ise 0 döndürsün.

f(n): n+1,n+2,n+3,...,2*n-1,2*n dizisinde tam olarak k tane bir biti içeren elemanların sayısı olsun.
f(n-1): n,n+1,n+2,...,2*n-3,2*n-2 dizisinde tam olarak k tane bir biti içeren elemanların sayısı olur.

f(n) = f(n-1) + count( 2*n-1 ) + count( 2*n ) - count( n ) olur.

count( 2*n ), count( n )'e eşit olur. 2*n sayısı n sayısının sonuna 1 adet 0 eklenmiş halidir.
O zaman bu iki sayıdaki bir bitleri sayısı eşittir.

f( n ) = f(n-1) + count( 2*n-1 ) olur.

Görüldüğü üzere n sayısı 1 artınca f fonksiyonunun değeri ya aynı kalır yada 1 artar.
Yani f azalmayan bir fonksiyondur.

f fonksiyonu azalmayan olduğu için cevabı binary search ile arayabiliriz.
Geriye kalan tek şey f(n) fonksiyonunu hesaplayabilmek.

1'den n'e kadar sayılardan kaç tanesi tam olarak k adet 1 biti içerdiğini bulursak iş biter.
Bunu da dinamik ile bulabiliriz.

dp[ind][k][t]
dp[70][70][2]

ind -> bulunduğum basamağın numarası kaç?
k -> kaç tane daha 1 biti koyacağım?
t -> şu anda bu basamağa ne koyarsam koyayım n sayısından küçük olur muyum?

Maliyet O( 70*70*2*log(10^18) ).

Çözüm Kodu:

#include <algorithm>
#include <string>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cassert>
#include <queue>
#include <cstdlib>
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <ctime>

#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define lli long long int
#define all( gg )        gg.begin(),gg.end()
#define foreach( gg,itit )        for( typeof(gg.begin()) itit=gg.begin();itit!=gg.end();itit++ )
#define FP( ii,aa,bb ) for( int ii=aa;ii<=bb;ii++ )
#define FM( ii,aa,bb ) for( int ii=aa;ii>=bb;ii-- )

using namespace std;

lli m,k,len,arr[70],dp[70][70][2];

lli bul( int ind,int k,int t ){
        if( ind==len+1 )        return k==0;
        lli &ret = dp[ind][k][t];
        if( ret!=-1 )        return ret;
        ret = bul( ind+1,k,!t ? 0 : arr[ind]==1 ? 0 : 1 );
        if( k and (!t or arr[ind]==1)  )        ret += bul( ind+1,k-1,t );
        return ret;
}

lli        F( lli orta ){
        len = 0;
        lli x = orta;
        while( x ){
                arr[++len] = (x&1);
                x >>= 1;
        }
        reverse( arr+1,arr+len+1 );
        memset( dp,-1,sizeof dp );
        return bul( 1,k,1 );
}

int main(){
        cin >> m >> k;
        lli bas=0,son=1e18,orta;
        while( bas<son ){
                orta = (bas+son)/2+1;
                if( F( 2*orta )-F( orta )>m )        son = orta-1;
                else        bas = orta;
        }
        cout << bas << endl;
}

Antimatter

Elimizde n tane doğal sayıdan oluşan a dizisi var. Bu dizinin bir bitişik alt dizisini seçelim. Sonrasında bu alt dizideki sayıların başlarına + veya - koyalım. Kaç farklı durum vardır ki bu işlemler uygulandığında alt dizideki sayıların toplamı 0 olsun. Bulduğunuz cevap büyük olabileceği için 1000000007'deki modunu alın.

Input Format

1. satırda n

2. satırda n tane sayıdan oluşan a dizisi

Output Format

Cevabın mod 1000000007'deki değeri

Constraints

1 <= n <= 1000

1 <= a_i <= 1000

sum(a) <= 10000

Input

4

1 1 1 1

Output

12

Açıklama
{1+,2-},{1-,2+},{2+,3-},{2-,3+},{3+,4-},{3-,4+},{1+,2+,3-,4-},{1+,2-,3+,4-},{1+,2-,3-,4+},{1-,2+,3+,4-},{1-,2+,3-,4+} ve {1-,2-,3+,4+}
_____________________________________________

Linkler

Soru: http://codeforces.com/contest/383/problem/D
Editorial: http://codeforces.com/blog/entry/10476
_____________________________________________

Çözüm

Bu soruda knapsack'i değiştiriyoruz çünkü önemli olan bitişik alt dizileri tutmak.

Yöntem
Ek olarak başka bir knapsack arrayi (dp2) tutuyoruz. Her a dizisi elemanını geziyoruz. Her seferinde dp2 arrayini sıfırlıyoruz. Klasik knapsack olayını biraz değiştirerek yapıyoruz. dp2 arrayini dp arrayini kullanarak dolduruyoruz. Ardından dp2 arrayine ek olarak şu anki elemanın + ve - halini koyuyoruz. Sonrasında dp arrayini dp2 arrayine eşitliyoruz.

Açıklama
Normal knapsack uygulasaydık {1+,3-} veya {2-,4+} gibi toplamı 0 olan bitişik olmayan alt dizileri ekleyecektik. Başka bir dp arrayi kullanarak dediğim yolu takip etmemizin nedeni bu.

Örnek Girdi
i=1 {1+},{1-}
i=2 {1+,2+},{1-,2+},{1+,2-},{1-,2-},{2+},{2-}
i=3 {1+,2+,3+},{1-,2+,3+},{1+,2-,3+},{1-,2-,3+},{2+,3+},{2-,3+},{1+,2+,3-},{1-,2+,3-},{1+,2-,3-},{1-,2-,3-},{2+,3-},{2-,3-},{3+},{3-}
i=4 {1+,2+,3+,4+},{1-,2+,3+,4+},{1+,2-,3+,4+},{1-,2-,3+,4+},{2+,3+,4+},{2-,3+,4+},{1+,2+,3-,4+},{1-,2+,3-,4+},{1+,2-,3-,4+},{1-,2-,3-,4+},{2+,3-,4+},{2-,3-,4+},{3+,4+},{3-,4+},{1+,2+,3+,4-},{1-,2+,3+,4-},{1+,2-,3+,4-},{1-,2-,3+,4-},{2+,3+,4-},{2-,3+,4-},{1+,2+,3-,4-},{1-,2+,3-,4-},{1+,2-,3-,4-},{1-,2-,3-,4-},{2+,3-,4-},{2-,3-,4-},{3+,4-},{3-,4-},{4+},{4-}
Her i.eleman için hesaplama bittiğinde dp arrayinde bitişi i olan bitişik alt dizileri tutmuş oluyoruz.
_____________________________________________

Kod

#include <algorithm>
#include <string.h>
#include <stdio.h>
#define  maxn      1000
#define  maxs      20001
#define  mod       1000000007
using namespace std;

int n,ans;
int ar[maxn];
int dp[maxs];
int dp2[maxs];

int main()
{
  scanf("%d",&n);
  for(int i=0 ; i<n ; i++)
    scanf("%d",&ar[i]);
  for(int i=0 ; i<n ; i++)
  {
    memset(dp2,0,sizeof(dp2));
    for(int j=0 ; j<maxs ; j++)
    {
 if(j>=ar[i])     dp2[j-ar[i]]=(dp2[j-ar[i]]+dp[j])%mod;
 if(j+ar[i]<maxs) dp2[j+ar[i]]=(dp2[j+ar[i]]+dp[j])%mod;
}
dp2[10000-ar[i]]=(dp2[10000-ar[i]]+1)%mod;
dp2[10000+ar[i]]=(dp2[10000+ar[i]]+1)%mod;
for(int j=0 ; j<maxs ; j++)  dp[j]=dp2[j];
ans=(ans+dp[10000])%mod;
  }
  printf("%d\n",ans);
  return 0;
}

Balanced Cow Breeds

   Size parantezlerden oluşan N uzunluğunda bir dizi veriliyor. Bu parantezleri H ve G grubu olarak ikiye ayıracaksınız, öyle ki her iki grubun parantezleri kendi içinde düzenli parantez olacak. Sizden bunun kaç farklı şekilde yapılabileceğini bulmanız isteniyor. Çıktıya 2012'ye göre modunu yazdırıyorsunuz.    Düzenli parantez dizileri açma ve kapama parantezleri sayısının birbirine eşit olduğu ve soldan sağa giderken kapamaların sayısının açmaları hiçbir zaman geçmediği parantez dizileridir. Örneğin: "()","(())", "(())()"

Kısıtlamalar

1 <= N <= 1000

Girdi Formatı

Tek satırda parantezlerden oluşan N uzunluğunda dizi

Örnek Girdi

(())

Çıktı Formatı

Tek satırda istenenin kaç farklı şekilde yapılabileceğinin 2012'ye göre modu.

Örnek Çıktı

6

Çıktı Açıklaması

6 gruplama:

(())
HHHH

(())
GGGG

(())
HGGH

(())
GHHG

(())
HGHG

(())
GHGH

ÇÖZÜM

Soru iki boyutlu dinamik kullanılarak çözülebilir. dp[i][j] sunu belirtiyor: i indisine kadar olan parantezleri bir sekilde gruplamisim ve H grubuna aldigim acmalarin sayisi kapamalarinkinden j fazla iken i ile n arasini kac farkli sekilde uygun sekilde gruplandirabilirim. Herhangi bir durumda iki secim yapabilirim: i. parantez ya H olacak ya da G. Dinamik yapmadan once dizinin her bir indisi icin oraya kadarki "acmalar - kapamalar"i hesaplamak dinamigi yaparken ise yarayacaktir.

Revamping Trails

Ipucu: soru shortest path sorusu ve dijkstra nin algoritmasiyla cozulebilir. Soruda k sinirinin kucuk olmasindan faydalanacagiz. K*n tane toplam durum var.

Cozum metnini soru ile birlikte en kisa surede koyacagim. Umarim ipucu faydali olur

Digraphs

Sizden kare şeklinde bir tablo doldurmanız isteniliyor. Bu tablo küçük harflerden oluşacak ve max 20x20'lik bir kare olabilecek. Bu tabloyu doldururken tabi ki bazı kurallara uymanız gerek.

Size n tane 2 küçük harften oluşan stringler verilecek. Örneğin stringlerden biri "xy" olsun. Sizin dolduracağınız tabloda y, x'in bir sağında veya x'in bir altında olamaz.

Amacınız olabildiğince büyük bir kare tablo oluşturmak. Ayrıca bu kare çok büyük olabileceği için sizden max 20x20'lik bir kare istenmektedir.

Input Format
İlk satırda T:Test Case sayısı
Case'in ilk satırı n: Yasaklı string sayısı
Sonraki n satırda yasaklı stringler

Output Format
Kurallara uyan ve size'i max 20x20 olan bir kare tablo

Constraints
0 <= n <= 676

Input
2
628
aa
az
ba
bb
bc
...
by
ca
cb
cc
...
cy
...
...
ya
yb
yc
...
yy
za
zb
zc
...
zy
zz
2
aa
bb

Output
aw
wz
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
_______________________________

Linkler

Soru: http://codeforces.com/gym/100299 (K sorusu)
pdf: http://codeforces.com/gym/100299/attachments/download/2035/20132014-acm-icpc-central-european-regional-contest-cerc-13-en.pdf
Solutions: http://cerc.tcs.uj.edu.pl/2013/data/cerc2013solutions.pdf
_______________________________

Çözüm

Alfabenin 26 harfini birer node kabul edelim. Başlangıçta tüm nodelar arasında yol olan tam graph oluşturalım. Yasaklı stringler verildikçe yolları silelim. Oluşan graph'ımızda 2 farklı ihtimal vardır. Ya cycle buluncak ya da bulunmayacak. Bu 2 ihtimale göre farklı tablo oluşturma stratejileri izleyeceğiz.

Cycle varsa

Herhangi bir cycle'i kullanarak kolaylıkla 20x20'lik kare şeklinde bir tablo oluşturabiliriz. Sırasıyla "abc" diye bir cycle olduğunu düşünelim. İlk satırı "abcabc..." şeklinde oluştururuz ve her sonraki satırda ilk karakterimizi bir kaydırırız. 2.satırda "bcabca...", 3.satıtda "cabcab...", 4.satırda tekrar "abcabc..." olur. Peki cycle'i nasıl bulabiliriz?
Yanlış yaklaşım: Akla ilk gelen SCC yapmak oluyor ki kodlaması yapacağımız işe göre uzun. SCC kodlamanın diğer bir problemi elimize gelen SCC'nin sıralı bir şekilde olmaması. Örneğin cycle sırasıyla "abc" olsun. Bizim elimize "acb" şeklinde geçebilir. Bunun için ekstradan SCC'yi gezme sırasına göre sıralamamız gerekecek ki işimiz uzayacak ve kod bazen patlayacak.( Ben ve Kamil beceremedik :( )
Cycle bulma: Dfs'i kodlarken mark array'ini 0-1 şeklinde tutarız. Burada array'i 0-1-2 şeklinde tutacağız ve ek olarak Stack kullanacağız. Bir node'a ilk kez geldiysek node'un mark'ini 2 yapacağız ve stack'e atacağız. Fonksiyondan çıkarken mark'i 1 yapacağız ve stack'ten çekeceğiz. Eğer ki bu node'a önceden gelindiyse ve mark'i 2 ise bu node hala stack'tedir ve cycle vardır. Stack'ten bu node gelene kadar node'ları çekeriz ve her gelen node'ları cycle listemizin başına atarız. Bundan sonra geriye kalan tek şey tabloyu oluşturmak.

Cycle yoksa

DP kullanarak en uzun yolu buluruz. Amacımız KxK'lık kare oluşturmak ve bunu oluştururken 2*k-1 uzunluğunda bir yol bulmak. Eğer en uzun yolumuz 2*k uzunluğunda ise ilk veya son karakterini sileriz. Stratejimiz şöyle olacak... Tablonun ilk satırını en uzun yolumuzun ilk k karakteri ile dizelim. Ardından gelen her satırda ilk karakteri bir kaydıralım. Örneğin yolumuz "abcdef" ise uzunluk çift olduğu için son karakteri sileriz. "abcde" stringi kalır. İlk satır "abc", sonraki satır"bcd", ondan sonraki satır "cde" olur.
_______________________________

Kod

#include <algorithm>

#include <string.h>

#include <stdio.h>

#include <vector>

#include <stack>

#define  pb       push_back

using namespace std;

int T,n;

int dp[26];

int best[26];

int mark[26];

int ar[26][26];

vector<int>v;

stack<int>sta;

void Cycle()

{

  int sz=v.size();

  for(int i=0 ; i<20 ; i++)

  {

    int bas=i%sz;

    for(int j=bas ; j<bas+20 ; j++)

      printf("%c",v[j%sz]+'a');

    printf("\n");

  }

}

int f(int node)

{

  if(v.size())      return dp[node];

  if(mark[node]==1) return dp[node];

  if(mark[node]==2)

  {

    while(sta.top()!=node)

    {

 v.pb(sta.top());

 sta.pop();

}

v.pb(node);

reverse(v.begin(),v.end());

Cycle();

return dp[node];

  }

  dp[node]=1;

  mark[node]=2;

  sta.push(node);

  for(int i=0 ; i<26 ; i++)

    if(!ar[node][i])

    {

 int x=f(i)+1;

 if(v.size())   break;

 if(x>dp[node]) dp[node]=x,best[node]=i;

}

  if(!sta.empty()) sta.pop();

  mark[node]=1;

  return dp[node];

}

void Reset()

{

  v.clear();

  memset(ar,0,sizeof(ar));

  memset(mark,0,sizeof(mark));

  while(!sta.empty()) sta.pop();

}

int main()

{

  scanf("%d",&T);

  while(T--)

  {

Reset();

    scanf("%d",&n);

    for(int i=0 ; i<n ; i++)

    {

 char s[5];

 scanf("%s",s);

 ar[s[0]-'a'][s[1]-'a']=1;

}

int b1=0,b2=0;

for(int i=0 ; i<26 ; i++)

 if(!mark[i])

 {

   int x=f(i);

   if(x>b1) b1=x,b2=i;

 }

if(v.size()) continue;

if(b1%2==0)  b1--;

v.pb(b2);

for(int i=1,x=b2 ; i<b1 ; i++)

{

 x=best[x];

 v.pb(x);

}

for(int i=0 ; i<(b1+1)/2 ; i++,printf("\n"))

 for(int j=0 ; j<(b1+1)/2 ; j++)

   printf("%c",'a'+v[i+j]);

  }

  return 0;

}

Cow Jogging

Soru Metni:

Sarikiz fazla kilolarindan kurtulmak icin, tepedeki ahirindan, gole kadar

yuruyus yapmak istiyor. Yuruyus sirasinda hep asagiya inecek ve geri

donerken de sallana sallana gelecek. Sarikiz sikilmamak icin hep ayni

yoldan gitmek istemiyor ayrica cok fazla yurumek istemedigi icin de

uzun yollari kullanmak istemiyor.

Ciftlikte toplam M (1 <= M <= 10,000) adet patika var. Bu patikalar otlaklari

birbirine bagliyor. Sirayla 1..N (1 <= N <= 1000) olarak numaralandirilmislar.

Bu numuralandirma yapilirken eger X>Y ise, otlak X'ten otlay Y'ye giden patika

yokul asagi. Otlak N en tepede ve Sarikiz'in yuruyuse baslayacagi ahir burada,

gol otlak 1'de bulunuyor. Otlak 1 en asagida.

Sarikiz'a otlak N'den otlak 1'e giden en kisa K (1 <= K <= 100) yolun uzunlugunu

hesaplamasi konusunda yardimci olunuz. Eger iki yol farkli patika dizilerinden

olusuyorsa farkli kabul ediliyorlar. Size X_i'den Y_i'ye giden patikalarin listesi

uzunluklari ile birlikte verilecek: (X_i, Y_i, D_i) (1 <= Y_i < X_i; Y_i < X_i <= N),

D_i (1 <= D_i <= 1,000,000).

SORUNUN ISMI: cowjog

GIRDI BICIMI:

* Satir 1: Boslukla ayrilmis uc tamsayi: N, M, ve K

* Satirlar 2..M+1: Satir i+1 yokus asagi bir yolu uc tamsayi ile tarif ediyor:

                               X_i, Y_i, ve D_i

ORNEK GIRDI (dosya cowjog.in):

5 8 7

5 4 1

5 3 1

5 2 1

5 1 1

4 3 4

3 1 1

3 2 1

2 1 1

GIRDI BICIMI:

* Satirlar 1..K: Satir i, i'inci en kisa yolun uzunlugunu iceriyor. Eger boyle bir yol

               mevcut degilse -1. Eger birden fazla en kisa yolun uzunlugu ayni ise, bu uzunlugun

               her yol icin ayri yazilmasi gerekiyor.

ORNEK CIKTI (dosya cowjog.out):

1

2

2

3

6

7

-1

CIKTININ ACIKLAMASI:

Yollar (5-1), (5-3-1), (5-2-1), (5-3-2-1), (5-4-3-1), (5-4-3-2-1).

Link: http://cerberus.delosent.com:790/MAR08

Çözüm:

Bize cycle olmayan bir graph verilmiş ve bu graph taki node lar zaten sıralı olduğu için dynamic programming güzel bir yaklaşım olur.

Varsayın ki i>=1 olmak üzere bütün i’ler için o node a ulaşan en kısa K yolu biliyoruz. Bu durumda (i-1). node a ulaşan en kısa K yolu bulmak için bu node una giren kenarları göz önünde bulundurmamız gerekiyor. Bu node a giren kenarların sayısı d olsun. Zaten d kenarın diğer ucundaki node lar için en kısa K yolu hesapladığımız için d*K yol içinden en kısa K tanesi (i-1). node a ulaşan en kısa  K yol olmuş olacaktır. Yöntemimiz her node için d*K zamana ihtiyaç duymaktadır ve graph ın genelinde bu rakam O(M*K) ya eşit olacaktır. M=10,000 ve K=100 olduğu için toplam işlem sayısı 1,000,000 dur yani çalışıyor.

Çözüm Kodu:

#include <stdio.h>

const int BIG = 1000000000;

const int MAXN = 2000;

const int MAXE = 20000;

const int MAXK = 200;

int n,e,k;

int ea[MAXE];

int eb[MAXE];

int elen[MAXE];

int d[MAXN];

int *out[MAXN];

int *len[MAXN];

int path[MAXN][MAXK];

int ei[MAXN];

int main() {

  FILE *fin;

  fin = fopen("cowjog.in", "r");

  fscanf(fin, "%d %d %d", &n, &e, &k);

  for(int i = 0; i < n; ++i){

    d[i] = 0;

  }

  for(int i = 0; i < e; ++i){

    int a,b,l;

    fscanf(fin, "%d %d %d", &b, &a, &l);

    --a; --b;

    ++d[a];

  }

  fclose(fin);

  out[0] = &eb[0];

  len[0] = &elen[0];

  for(int i = 1; i < n; ++i){

    out[i] = out[i-1] + d[i-1];

    len[i] = len[i-1] + d[i-1];

  }

  fin = fopen("cowjog.in", "r");

  fscanf(fin, "%d %d %d", &n, &e, &k);

  for(int i = 0; i < n; ++i){

    d[i] = 0;

  }

  for(int i = 0; i < e; ++i){

    int a,b,l;

    fscanf(fin, "%d %d %d", &b, &a, &l);

    --a; --b;

    out[a][d[a]] = b;

    len[a][d[a]] = l;

    ++d[a];

  }

  fclose(fin);

  path[n-1][0] = 0;

  for(int i = 1; i < k; ++i){

    path[n-1][i] = BIG;

  }

  for(int i = n-2; i >= 0; --i){

    for(int j = 0; j < d[i]; ++j){

      ei[j] = 0;

    }

    for(int j = 0; j < k; ++j){

      int best_m = 0;

      int best_d = BIG;

      for(int m = 0; m < d[i]; ++m){

               if(len[i][m] + path[out[i][m]][ei[m]] < best_d) {

                 best_m = m;

                 best_d = len[i][m] + path[out[i][m]][ei[m]];

               }

      }

      path[i][j] = best_d;

      ++ei[best_m];

    }

  }

  FILE *fout = fopen("cowjog.out", "w");

  for(int i = 0; i < k; ++i){

    fprintf(fout, "%d\n", (path[0][i] == BIG) ? -1 : path[0][i]);

  }

  fclose(fout);

  return(0);

}

Here is a concise solution that France's Louis Jachiet thinks might be easier to understand:

#include <stdio.h>

#include <algorithm>

#include <vector>

using namespace std;

int nb_paturages, nb_chemins, nb_itineraires;

vector<int> plus_court[1001];

vector<int> suiv      [1001];

vector<int> poids     [1001];

int main() {

    freopen("cowjog.in","r",stdin);

    freopen("cowjog.out","w",stdout);

    scanf( "%d %d %d", &nb_paturages, &nb_chemins, &nb_itineraires);

    // making the reverse graph

    for (int chem = 0; chem < nb_chemins ; chem++) {

        int dep, arr, pds;

        scanf ("%d %d %d", &dep, &arr, &pds);

        suiv [arr].push_back (dep);

        poids[arr].push_back (pds);

    }

    plus_court[1].push_back (0);

    for (int pat = 1; pat <= nb_paturages ; pat++) {

        sort (plus_court[pat].begin(), plus_court[pat].end());

        // exploring the current node for all  the shortest path

        for (int id = 0; id < plus_court[pat].size() &&

                                                             id < nb_itineraires; id++) {

            int tps = plus_court[pat][id];

            for (int id1 = 0; id1 < suiv[pat].size() ; id1++)

                plus_court[suiv[pat][id1]].push_back (tps + poids[pat][id1]);

        }

        // printing all the shortest path

        if (pat == nb_paturages)

            for (int id = 0; id < nb_itineraires ; id++)

                if (id < plus_court[pat].size())

                    printf ("%d\n", plus_court[pat][id]);

                            else

                    printf ("-1\n");

            plus_court[pat].clear();

    }

    return 0;

}

Kayak

Kış olimpiyatlarındaki kayak parkuru M x N lik (1 <= M,N <= 500) bir arazide belirlenmiştir. Her birim kare 0 .. 1,000,000,000 arasında bir yüksekliğe sahiptir.

Bazı kareler parkur yolu olarak seçilmiştir. Kış olimpiyatı organizatörleri parkur boyunca bir zorluk seviyesi (D) olması konusunda anlaşırlar. Bu şekilde bir ineğin kayarken bir kareden diğerine geçebilmesi için aralarındaki yükseklik D yi aşamayacak şekilde olmaktadır. İnek kayarken sadece güney, kuzey, doğu ve batı yönündeki komşu birim karelere gidebilmektedir.

PROBLEM ADI: ccski

GİRDİ ŞEKLİ:

* Satır 1: M ve N sayıları.

* Satır 2..1+M: Her satır N tane yükseklik içermektedir.

* Satır 2+M..1+2M: Her satır toplam N tane olmak üzere 0 ya da 1 değerlerini içermektedir. Bu değerler parkurda gidilmesi gereken yolları göstermektedir.

ÖRNEK GİRDİ (dosya ccski.in):

3 5

20 21 18 99 5

19 22 20 16 26

18 17 40 60 80

1 0 0 0 1

0 0 0 0 0

0 0 0 0 1

GİRDİ AÇIKLAMASI:

Parkur 3 x 5 lik bir arazide tanımlanmıştır. Sol ve sağ üst, sağ alt gidilmesi gereken yerleri göstermektedir.

ÇIKTI ŞEKLİ:

* Satır 1: Zorluk seviyesi (Gidilmesi gereken tüm yerlere ulaşabilecek şekilde en küçük D).

ÖRNEK ÇIKTI (dosya ccski.out):

21

ÇIKTI AÇIKLAMASI:

Eğer D = 21, 3 yere de birbirinden gidilebilir. Eğer D < 21 ise, sağ üstteki noktaya diğer iki yerden varılamaz.

Çözüm Metni :

Reachable(X) diye bir fonksiyon tanımlayalım ki bu fonksiyon bize tüm gidilmesi gereken yerlere gidilebilecek derecede olan X değerinin doğru olup olmadığını versin. Bu sayede farklı X değerleri kullanıp D değerini bulabiliriz. 0 .. 1000000000 arasında tüm X değerleri yerine ikili arama yapıp D değerini elde edebiliriz.

Dmin=0, Dmax=1000000000

while Dmin < Dmax

    X = (Dmin + Dmax) / 2

    if Reachable(X)

        Dmax = X

    else 

        Dmin = X + 1

D = Dmin

Reachable fonksiyonu üstüne bir de gidilmesi gereken noktalar arasındaki yolları belirlemek için bir algoritmaya ihtiyacımız var. Aradaki yükseklik farklı D olacak şekilde belirlemek için DFS ya da BFS kullanabiliriz. Ancak DFS bazı girdilerde çok uzun dallanmalara sebebiyet vereceği için BFS ile bunu belirlemek daha iyi olacaktır.
Her Reachable fonksiyonu çağrılması O(NM) çözüm karmaşıklığına denk gelir. İkili arama fonksiyonu da O(log R) çözüm karmaşıklığındadır. (R 0..1,000,000,000 arasındadır). Toplam çözüm karmaşıklığı O(MN log R) dir.

Soru Linki : http://usaco.org/index.php?page=viewproblem2&cpid=380
Çözüm Kodu :  http://usaco.org/current/data/sol_ccski.html

Lopov

LOPOV

Ülkedeki güç ekonomik şartlar ve hükümetin tarımsal desteği kesmesi Mirko'yu mesleğini değiştirmeye iter, artık bir hırsızdır.Elmas çalma işindedir.

Bir depoda N tane elmas parçası , ve her elmasın Mi

ağırlığı ve Vi değeri vardır.

Mirko'nun ise K tane torbası ve her torbanın Ci maksimum kapasitesi vardır.

Bütün çaldıklarını bu torbada taşıyacaktır fakat elmaslara zarar gelmemesi için her torbada yalnız bir elmas taşıma hakkı vardır.

Mirko'nun çalabileceği toplam maksimum elmas değerini bulunuz.

GİRDİ

İlk satırda iki sayı, N ve K (1 ≤ N, K ≤ 300 000).

Ardından gelen N satırda ikişer sayı vardır, Mi ve Vi (1 ≤ Mi, Vi≤ 1 000 000).

Geri kalan K satırda bir sayı, Ci (1 ≤ Ci ≤ 100 000 000).

Girdideki tüm sayılar pozitiftir.

ÇIKTI

Tek satırda Mirko'nun taşıyabiliceği maksimum toplam elmas değeri.

Dataların %50'sinde N ve K 5000'i aşmıyacaktır.

Örnek Girdi-Çıktılar

girdi

2 1

5 10

100 100

11

çıktı

10

girdi

3 2

1 65

5 23

2 99

10

2

çıktı

164

Çözüm:

Soruyu çözerken bulmak istediğimiz şey, her bir çanta için kendi ağırlığına eşit veya kendi ağırlığından küçük ağırlığı olan ve en büyük değere sahip elması bulmak. Bunun için de çantaları küçükten büyüğe, elmasları da ağırlığına göre küçükten büyüğe sıralıyoruz.

Sonra 1'den N'e doğru her bir çanta için sıradaki işlemleri yapacağız:

1- O çantanın içine sığabilecek ağırlıktaki tüm elmasların değerlerini max heap'e atacağız (Eğer daha önce atılmamışsa).

2- Sonra heap'ten ilk elemanı alarak o çantanın içine koyarak heap'ten çıkartırız.

3- Çantaya koyduğumuz değeri toplama ekleriz.

Bu işlemi en büyük çanta için de yaptığımızda dolabilecek olan bütün çantalar optimum şekilde dolmuş olur ve sonuca ulaşmış oluruz.

Soru : http://www.hsin.hr/coci/contest1_tasks.pdf

Girdi-Çıktı: http://www.hsin.hr/coci/contest1_testdata.zip

İngilizce Çözüm: http://www.hsin.hr/coci/contest1_solutions.zip

Putnik

PUTNIK

Traveling Salesman problemini duymuşsunuzdur. Eğer duymuşsanız o problemin NP-hard olduğunu bilirsiniz çünkü iyi bir çözüm bulmak zordur.Pekala, bu soru ünlü problemin az rastlanan bir versiyonudur! Az rastlanması temel olarak 'çözülebilmesi'nden gelir.

Postacımız N tane şehri her birini tam olarak sadece bir kez dolaşmakla görevlidir.Şehirler 1,2,3...N olarak adlandırılır. Elimizde her şehirden birbirine giden yolların ne kadar sürdüğünü belirten bir tablo vardır. Postacı, mükemmel bir insan olduğundan, elindeki tablodan yola çıkarak öyle bir yol haritası oluşturmak ister ki toplam şehirleri dolaşma süresi minimum olsun.

Fakat herşey bu kadar kolay değildir. Postacının bir takıntısı vardır. O da şudur, her hangi bir K. şehir için kendinden önce gelen K-1 tane şehrin hepsini ya K'ya gitmeden önce dolaşmış, yada aynı şekilde hepsini K'ya gittikten sonra dolaşıcak olmalıdır.Başka bir deyişle, eğer K'dan küçük numaralı bir şehri K'ya gitmeden önce dolaşmışsa, K'ya gitmeden önce 1...K-1 şehirlerinin hepsini dolaşmış olması gerekmektedir.

Bu şartlara uyarak, postacının istediği şehirden başladığı ve istediği şehirde bitirdiği, bütün şehirleri dolaşmış olduğu minimum süreyi bulunuz.

GİRDİ

ilk satırda N (2 ≤ N ≤ 1500)

alt satırda NxN'lik bir tablo, i'inci satırdaki şehir ile j'inci sütundaki şehir arasındaki süreyi gösterir.

ÇIKTI

Tek satırda Minimum süre

ÖRNEKLER

girdi

3

0 5 2

5 0 4

2 4 0

çıktı

7

girdi

4

0 15 7 8

15 0 16 9

7 16 0 12

8 9 12 0

çıktı

31

Birinci girdideki çözümün şehir sıralaması : 2,1,3 veya 3,1,2

İkinci girdideki çözümün şehir sıralaması : 3, 1, 2, 4 veya 4, 2, 1, 3.

ÇÖZÜM

Postacının takıntısını giderecek tüm sıralamalara şu yolla ulaşabiliriz. İlk olarak 1. şehir sıralamaya eklenir sonra 2. şehir sıralamanın sağına veya soluna konulur, bu işlem N. şehire kadar devam eder ve bu yolla elde edilen her sıralama Postacının takıntısına uygundur.Artık soru dinamik programlama ile çözülebilir.Elde ettiğimiz sıralamaları listenin sağındaki ve solundaki şehir ile adlandıracağız.Bu iki şehiri bilmemiz demek bir sonraki eklenecek şehri bilmemiz demektir.Neden ? Çünkü o sıralamaya en son eklediğimiz şehir o sıranın ya solunda ya da sağında bulunmak zorundadır.Böylece ekliyceğimiz şehirin numarası onun bir fazlası olacaktır.Bu noktada ekleyeceğimiz şehir için sağa veya sola ekleme olmak üzere iki ihtimal vardır,Önceki bulduğumuz dinamik değerler ile, sağına veya soluna koyduğumuzda oluşucak minimum süreleri yeni dinamik değerler olarak bulabiliriz.Böyle ilerleyerek bütün şehirleri dolaştığımız en kısa süreyi dinamik dizi üzerinden buluruz.

O(N 2 ).

Soru: http://www.hsin.hr/coci/contest2_tasks.pdf

Girdi-Cikti: http://www.hsin.hr/coci/contest2_testdata.zip

İngilizce Çözüm: http://www.hsin.hr/coci/contest2_solutions.zip