Cow Photography

Farmer John'un çiftliğinde N ineği ve her birinin farklı id numarası vardır. Farmer John tüm ineklerin 5 kere fotoğrafını çekecektir. İlk başta bu N inek orijinal sıralarındadırlar. Farmer John'un her fotoğraf çekişinde bir grup inek(boş grup olabilir) istediği gibi yerini değiştirebilir. Bir inek 2 grupta olamaz yani her ineğin maksimum 1 kere yer değiştirme hakkı vardır. Sizden istenilen bu N inekin orijinal sırası.

Input Format
İlk satırda N: inek sayısı
Sonraki 5*N satır: Her fotoğraf için her ineğin id'sini gösteren N satır

Output Format
N satırda ineklerin orijinal sırası.

Constraints
1 <= N <= 20,000
0 <= id <= 1,000,000,000

Input

5

10

20

30

40

50

20

10

30

40

50

30

10

20

40

50

40

10

20

30

50

50

10

20

30

40

Output

10

20

30

40

50

______________________________________

Link

Soru, Test Data ve Solutions : http://usaco.org/index.php?page=dec11problems
______________________________________

Çözüm

Bu soru aslında her ne kadar basit olsa da çözüm yolu ilginçtir ve sorting ile çözülmektedir.

1 <= t <= 5 , 1 <= x,y <= N olmak üzere
g(t,x,y): t. fotoğrafta x.ineğin y.ineğin önünde olup olmadığını göstersin. Eğer x öndeyse 1, y öndeyse değerimiz 0 olsun.
f(x,y): g(1,x,y)+g(2,x,y)+g(3,x,y)+g(4,x,y)+g(5,x,y) toplamı olsun.

Şimdi söyle düşünelim...
x, y'nin önünde olsun. f(x,y) en kötü ihtimalde 3 olur. x, y'nin arkasına ve bundan ayrı bir fotoğrafta y, x'in önüne geçerse toplamda y 2 kere öne geçmiş olur ve x, y'nin 3 kere önünde kalmış olur.
x, y'nin arkasında olsun. f(x,y) en iyi ihtimalde 2 olur. Bu sefer x, y'nin önüne ve bundan ayrı bir fotoğrafta y, x'in arkasına geçerse x, y'nin toplamda 2 kere öne geçmiş olur.

Sonuç olarak f(x,y) >= 3 ise x, y'nin önündedir.

Bundan sonra her inek için bir struct yapısı oluşturup bir sort çekersek kolayca orijinal sırayı hesaplamış oluruz.
______________________________________

Kodum

#include <algorithm>
#include <stdio.h>
#include <vector>
#include <map>
#define  maxn    20003
#define  pb         push_back
using     namespace std;

struct data
{
  int val;
  vector<int>v;
}ar[maxn];

int n,m;
map<int,int>hash;

bool comp(data a , data b)
{
  int cnt=0;
  for(int i=0 ; i<5 ; i++)
    if(a.v[i]<b.v[i])
      cnt++;
  return (cnt>=3);
}

int main()
{
  scanf("%d",&n);
  for(int i=1 ; i<=5 ; i++)
    for(int j=1 ; j<=n ; j++)
    {
 int x;
 scanf("%d",&x);
 if(i==1 && !hash[x]) { hash[x]=++m; ar[m].val=x; }
 (ar[hash[x]].v).pb(j);
    }
  sort(ar+1,ar+n+1,comp);
  for(int i=1 ; i<=n ; i++)
    printf("%d\n",ar[i].val);
  return 0;
}

Cow Curling

İnek Curling'i 

İnek Curling'i, Moolympics'te yer alan popüler bir soğuk hava sporudur.

Normal Curling'deki gibi İnek Curling'i de 2 takım ile oynanır. Her takımın N(3 <= N <= 50,000) adet ağır taşı vardır ve bunları bir buz şeridi üzerinde kaydırarak bu oyun oynanır. Oyunun sonunda buzun üzerinde her biri farklı konumda olan 2N adet taş bulunur.

İnek Curling'inde skor olayı normal curlinge göre biraz farklıdır. Eğer bir taş rakip takımın taşları üçgenin köşeleri olacak şekilde herhangi bir üçgenin içerisindeyse o taş ele geçirilmiştir (Eğer taş üçgenin kenarlarından birinin üzerindeyse o da ele geçirilmiş sayılır). Bir takımın skoru karşı takımın ele geçirilmiş taş sayısına eşittir.

Sizden istenen 2N adet taşın hepsinin final durumları verildiğinde, maç skorunu bulmanız.

SORU İSMİ : curling

INPUT FORMAT:

* 1. satır: N sayısı.

* Satır 2..1+N: Her bir satır A'nın bir taşının x ve y koordinatlarını belirten iki tam sayıdan oluşuyor.(her bir koordinat [-40,000 , +40,000] aralığındadır).

* Satır 2+N..1+2N: Her bir satır B'nin bir taşının x ve y koordinatlarını belirten iki tam sayıdan oluşuyor. (her bir koordinat [-40,000 , +40,000] aralığındadır).

ÖRNEK INPUT (file curling.in):

4

0 0

0 2

2 0

2 2

1 1

1 10

-10 3

10 3

INPUT Açıklama:

Her bir takımın 4 taşı var. A'nınkilerin konumları (0,0), (0,2), (2,0), and (2,2), ve B'ninkilerin konumları (1,1), (1,10), (-10,3), and (10,3).

OUTPUT FORMAT:

* 1. satır: A ve B takımlarının skorlarını veren boşlukla ayrılmış 2 sayı.

ÖRNEK OUTPUT (file curling.out):

1 2 

OUTPUT Açıklama:

A, B'nin (1,1)'deki taşını ele geçiriyor. B de A'nın (0,2) ve (2,2)'deki taşlarını ele geçiriyor. Yani A'nın skoru 1, B'ninki 2. 

______________________________________________________________________

ÇÖZÜM:

Çözümde sadece, kaç tane mavi noktanın kırmızı noktalar tarafından oluşturulan üçgenler içerisinde yer aldığını nasıl bulacağımızı anlatacağız.Çünkü kaç kırmızının mavi üçgenler içerisinde yer aldığını da aynı yöntemle bulabiliriz.

Herhangi bir mavi nokta, kırmızı noktalardan oluşturulan herhangi bir üçgenin içerisindeyse, o nokta maviler tarafından “ele geçirilmiş” oluyor. O zaman burdan şunu da çıkarabiliriz:

Bir mavi nokta kırmızı noktalardan oluşan üçgenlerin birleşiminin oluşturduğu alanın içerisindeyse o nokta “ele geçirilmiş” tir. Üçgenlerin birleşimi üzerine biraz düşündüğümüz zaman üçgenlerin birleşiminin N tane kırmızı noktanın “Convex Hull”'ı olduğunu görüyoruz. “Convex Hull” 'ı herhangi bir O(N(log N))'lik algoritmayla bulabiliriz.

O zaman sorumuz şu hale geliyor:

N tane noktanın bu konveks alanın içerisinde olup olmadığını nasıl anlayabiliriz? Bu soruyu da konveks üzerindeki noktaları dairesel ya da soldan sağa sırayla tutarak çözebiliriz.

Önce dairesel şekilde tutarsak nasıl yapacağımıza bakalım.

Convex hull'ın içerisinde rastgele bir O noktası seçelim ve O noktasını orjin kabul edip, tüm noktaların koordinatlarını buna göre güncelleyelim. Bunu yaparak “Convex Hull” ' ımızın orjini içeridiğini garantilemiş olduk. Yani, “Convex Hull”'ın üzerindeki noktalar x ekseniyle yaptıkları açılara göre artan şekilde kolayca sıralanabilir hale geldi. Böylece, verilen herhangi bir mavi nokta için önce o noktanın x ekseniyle yapmış olduğu açıyı buluruz, sonra da konveksin o noktayla ilgili kenarını bulup sadece o kenarın solunda olup olmadığına bakarak noktanın konveksin içinde mi dışında mı olduğunu anlarız. (x ekseniyle yapmış olduğu açı bulunan nokta ile ilgili olan kenar binary search ile log(N)'de bulunabilir.)

Gelelim soldan sağa tutarsak nasıl yapacağımıza.

Konveks üzerindeki tüm noktaları x eksenlerine göre sıralayarak yamuklara ayırıyoruz. Her bir yamuk x değerlerine göre birbirinden farklı aralıkları kapsıyor. Böylece her bir nokta için ilgili yamuğu bulup içinde olup olmadığını kontrol ediyoruz.

İki durumda da O(log N) 'de herhangi bir noktanın kendisiyle ilgili kenar ya da yamuğa göre konumunu bulabiliyoruz. Bunu da N defa yapacağımızdan O(N log N)' de soruyu çözmüş oluyoruz.

Soruya burdan http://www.usaco.org/index.php?page=viewproblem2&cpid=382

Çözümün ingilizcesine ve çözüm koduna burdan http://www.usaco.org/current/data/sol_curling.html

Girdi-Çıktılara burdan http://www.usaco.org/current/data/curling.zip

ulaşabilirsiniz.

Optimal Milking

Çiftçi Jonh içinde N tane süt sağma makinesı olan yeni bir çiftlik satın aldı (1 <= N <= 40,000), tabi ki makineler 1'den N'e kadar numaralandırılmış ve yan yana dizilmiştir. Makine i'nin günlük süt sağma kapasitesi M(i) birimdir (1 <= M(i) <= 100,000).

Ancak makineler birbirlerine çok yakın kuruldukları için i. makinenin çalıştırıldığı günlerde i-1. ve i+1. makineler kullanılamamaktadır. Çiftçi John az önce belirtilen kurala sadık kalarak her gün istediği makineleri çalıştırabilmektedir.

Çiftçi John önümüzdeki D (1 <= D <= 50,000) gün boyunca her gün maksimum kaç birim süt sağabileceğini merak etmektedir. Her günün başlangıcında Çiftçi John seçtiği bir makineyi onarmakta ve bu makinenin sağabileceği süt miktarını değiştirmektedir.

Size önümüzdeki D gün boyunca Çiftçi John'un onaracağı makinelerin listesi verildiğinde D günün sonunda sağabileceği maksimum süt miktarını çıktıya bastırmanızdır (bu değer INT_MAX değerini aşabilir).

Soru adı: optmilk

Girdi Formatı: 

* Satır 1: Sırasıyla N ve D değerleri 

* Satır 2..1+N: Satır i+1 M(i) nin başlangıç değerini içerir. 

* Lines 2+N..1+N+D: Satır 1+N+d i ve m değerlerini içerir. Çiftçi John'un d. gün değiştireceği makinenin indisi i, i makinesinin yeni süt sağma kapasitesi m'dir. Başka bir deyişle M(i)=m olur. 

Örnek Girdi (dosya optmilk.in): 

5 3

1

2 

3 

4 

5 

5 2 

2 7 

1 10 

Girdi Açıklaması: 

Başlangıçtaki süt sağma değerleri sırasıyla 1,2,3,4,5 olan 5 makine vardır. İlk gün makine 5'in süt sağma değeri 2 birime olmuştur vs.


Çıktı Formatı: 

* Tek bir satırda Çiftçi John'un D günde sağabileceği maksimum süt miktarı 

Örnek Çıktı (dosya optmilk.out): 

32 

Çıktı Açıklaması: 

Birinci gün en iyi yol 2. ve 3. makieneleri kullanmaktır 2+4=6 (1. 3. ve 5. makineler de kullanılabilir 1+3+2=6).

İkinci gün 2. ve 4. makineler kullanılır 7+4 = 11.

Üçüncü gün, 1. 3. ve 5. makineler kullanılır 10+3+2=15.

----------------------------------------------------------------------------------------

Soru linki: http://www.usaco.org/index.php?page=viewproblem2&cpid=365&lang=en

Girdi - Çıktı: http://www.usaco.org/current/data/optmilk.zip

----------------------------------------------------------------------------------


Çözüm

Eğer problemimizde update kısmı olmasaydı Dp[i] = max(Dp[i-1],M[i]+Dp[i-2]) şeklinde basit bir dinamik programlama sorusu olacaktı. Fakat her adımda bu dinamiği tekrar hesaplarsak çözüm O(N^2) ye gideceğinden bu dinamiği çözümde kullanmak mantıklı değil.

Problemimizin updatesiz çözmenin bir diğer yolu ise şudur: Elimizde bir Segment Tree olduğunu ve her elemanın 4 değer tuttuğunu düşünelim ; Segment Tree nin a....b node'u için bu değerler
[a,b] aralığında a. ve b. indisteki sayıyı çözümümde kullanıp kullanmama durumuma göre belirlenecek (ikisini de kullandığım durum, sadece ilkini kullandığım durum vs.). Bu değerlerden herhangi birini altımdaki 2 çocuğa bakarak karar verebilirim. Sonuç olarak her node için 4 değeri de altımdaki çocuklardan belirlediğimde 1.....N node'u için bu 4 değerin maksimumu benim çözümüm olur.


Yukarıdaki Segment Tree çözümünü anladıktan sonra problemin update'li hali görüldüğü üzere çok kolay oluyor. Eğer D gün boyunca değeri değişen makineyi ve Segment Tree'de bu makineyi kapsayan nodeları update edersek soruyu DlogN de çözmüş oluruz.


----------------------------------------------------------------------------------

Çözüm Kodu

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int n, d, a, b;
int bb[1<<17], bp[1<<17], pb[1<<17], pp[1<<17], SIZE=(1<<16);

void update(int node) {
    int l=node*2, r=node*2+1;
    pp[node] = max(pb[l]+pp[r], pp[l]+bp[r]);
    pb[node] = max(pb[l]+pb[r], pp[l]+bb[r]);
    bp[node] = max(bb[l]+pp[r], bp[l]+bp[r]);
    bb[node] = max(bb[l]+pb[r], bp[l]+bb[r]);
}

main() {
    freopen("optmilk.in", "r", stdin);
    freopen("optmilk.out", "w", stdout);
    scanf("%d %d", &n, &d);
    for(int i=0;i<n;i++) scanf("%d\n", &bb[SIZE+i]);
    for(int i=SIZE-1;i>0;i--) update(i);
    long long ans=0;
    for(int i=0;i<d;i++) {
 scanf("%d %d", &a, &b); a--;
 bb[SIZE+a] = b;
 for(int j=(SIZE+a)/2;j>0;j/=2) update(j);
 ans += bb[1];
   }
   printf("%lld\n", ans);
}