İ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;

}