İkinci Aşama İçin Öneri Sorular 3

Bunlar önceki önerilere göre daha zor sorular kolay gelsin.

USACO Nov07
                           GOLD PROBLEMS
Problem 1: Telephone Wire [Jeffrey Wang, 2007]
Problem 2: Cow Relays [Erik Bernhardsson, 2003]
Problem 3: Sunscreen [Russ Cox, 2001]


USACO Dec07
                           GOLD PROBLEMS
Problem 2: Gourmet Grazers [Alex Schwendner, 2007]


USACO Jan08
                           GOLD PROBLEMS
Problem 3: Cell Phone Network [Jeffrey Wang, 2007]


USACO Feb08
                           GOLD PROBLEMS
Problem 1: Making the Grade [Brian Dean, 2008]


USACO Mar08
                           GOLD PROBLEMS
Problem 2: Cow Jogging [Alex Schwendner & Eric Price, 2006]
Problem 3: Pearl Pairing [Catalin Tiseanu, 2007]


USACO Nov08
                           GOLD PROBLEMS
Problem 1: Mixed Up Cows [Don Piele, 2007]
Problem 2: Cheering up the Cows [David Benjamin and Jacob Steinhardt, 2008]


Part of USACO Dec08
                           GOLD PROBLEMS
Problem 1: Trick or Treat on the Farm [Jacob Steinhardt, 2008]


Part of USACO Jan09
                           GOLD PROBLEMS
Problem 1: Earthquake Damage [Hal Burch, 2004]
Problem 2: The Baric Bovine [Jeffrey Wang, 2007]


Part of USACO Feb09
                           GOLD PROBLEMS
Problem 1: Fair Shuttle [Russ Cox and Hal Burch, 2006]
Problem 2: Stock Market [Rob Kolstad(?), 2008]
Problem 3: Revamping Trails [Percy Liang, 2008]

Soruların ingilizce metinlerine : http://tjsct.wikidot.com/usaco
Soruların ingilizce çözümlerine : http://dl-reserve.gsu.by/NForum/forum/list/21.dl
Linklerinden ulaşabilirsiniz.

Sabotage

Soru için Enes Öncü'ye teşekkür ederiz.

Soru Metni:
Size N elemanlı bir dizi veriliyor. Bu diziden öyle bir altdizi siliniz ki sildiğiniz altdizi 1 ve N numaralı
indisleri içermesin ve geriye kalan elamanların ortalaması minimum olsun.
Cevabı noktadan sonra 3 basamağa kadar yazdırın.

3 <= N <= 100,000
1 <= dizinin herbir elemanı <= 10,000

Örnek Girdi

5
5 1 7 8 2

Örnek Çıktı

2.667

Açıklama:

3. ve 4. indisleri silersek ortalama 8/3 = 2.667 olur


Çözüm Metni:

Soru binary search sorusu. Cevabı binary search ile arayacağız.
Bir değeri denerken bu değerden küçük veya eşit bir ortalama olup olamayacağını kontrol edeceğiz.

Mesela cevabımız l ve r arasında olsun. Eğer (l+r)/2 den küçük eşit bir ortalama
bulabiliyorsak cevabımızın l ve (l+r)/2 arasında olduğunu biliriz. Aksi takdirde
cevabımız (l+r)/2 ve r aralığında olur.

Şimdi sorunun önemli kısmı olan bu kontrolün nasıl yapıldığını anlatacağım.

Ortalamanın bir K sayısından küçük eşit olabileceğini veya olamayacağını kontrol edelim. Dizideki
tüm elemalardan K çıkarttığımızda soruyu şuna dönüştürebiliriz: Dizimizden öyle bir altdizi
silelim ki 1. ve N. indisleri içermesin ve kalan elemanların toplamı 0 dan küçük eşit olsun.
Peki neden? Çünkü geriye a tane eleman kaldıgını varsayalım ve toplamları sum olsun. O zaman
dizinin elemanlarından K çıkartmadığımız durumda bu sayıların ortalaması (sum+a*K)/a<=K olurdu.
Eger sum<=0 şartı sağlanırsa (sum+a*K)/a<=K olur.
O zaman eğer sum'ın olabileceği en küçük değer 0 dan küçük eşitse ortalama K dan küçük eşit olabilir.
sum'ı en küçük yapmak için de dizide en büyük toplama sahip aralığı diziden sileriz. Bunu yapmak içinde
tüm elemanlarından K sayısı çıkarılmış dizideki 2 ve n-1 aralığında maximum toplama sahip altdiziyi buluruz.
Bunu Kadane yötemi gibi basit yöntemlerle yapabiliriz.



Çözüm Kodu:

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

#define FP( ii,aa,bb ) for( int ii=aa;ii<=bb;ii++ )

using namespace std;

int n,arr[100005];

bool kontrol( double K ){

double sum=arr[1]+arr[n]-2*K;
double maxsubarray=-1999999999,now=0;

FP( i,2,n-1 ){
sum += arr[i]-K;
now += arr[i]-K;
maxsubarray = max( maxsubarray,now );
if( now<0 ) now = 0;
}

sum -= maxsubarray;

return sum<=0;

}

int main(){

freopen("sabotage.in","r",stdin);
freopen("sabotage.out","w",stdout);

cin >> n;
FP( i,1,n )
cin >> arr[i];

double l=0.0,r=1e9,mid;

for( int iteration=1;iteration<=100;iteration++ ){
mid = (l+r)/2;
if( kontrol( mid ) ) r = mid;
else l = mid;
}

printf("%.3lf\n",l);


}

Soruyu Göndermek için : http://usaco.org/index.php?page=viewproblem2&cpid=419

Balkan 2014 Day 1

Balkan sorularının ulaşılabilir olmasının faydalı olacağını düşündük. Şuanda elimizde sadece İngilizce metinleri ve girdi çıktı dosyaları var en kısa süre içerisinde Türkçe metinleri ve Türkçe çözümlerini paylaşmaya çalışacağız.

Day1 Link: https://www.dropbox.com/s/brlzf1o493awpdo/Boi2014-Day1.zip?dl=0

Password Service

Bize L uzunluğunda <,>,= işaretlerinden oluşan S stringi veriliyor. Bizden istenen alfabenin ilk N harfini kullanarak L+1 uzunluğunda bir string oluşturmamız.

Oluşturmamız gereken str stringi şöyle olmalıdır...
S[i] = '<' ise str[i]<str[i+1]
S[i] = '>' ise str[i]>str[i+1]
S[i] = '=' ise str[i]=str[i+1]

Eğer bu koşulları sağlayan bir string yoksa -1 yazdırınız.

Input Format
İlk satırda N: Alfabenin ilk N harfini(küçük harf) kullanabiliyoruz.
2. satırda S: Oluşturmamız istenen str için gerekli koşulları içerir.

Output Format
Koşulları sağlayan stringi yazdırınız. Yoksa -1 yazdırın.

Constraints
1 <= N <= 26
1 <= L <= 5000

Input
5
=<>

Output
bbdc

_____________________________

Link

Soru: http://codeforces.com/gym/100253 (H sorusu)
pdf: http://codeforces.com/gym/100253/attachments/download/1971/20132014-acmicpc-neerc-southern-subregional-contest-en.pdf
_____________________________

Çözüm

Bu soru ilkin greedy gibi gözükse de aslında DP sorusudur.

DP[curr][c] : Şu anki pozisyonumuz curr, son karakterimiz c olsun. Bundan sonra yapmamız gereken S stringindeki kurallara göre yeni karakter eklemek.

Her mümkün (curr,c) durumu için eklenmesi gereken karakteri tutarız. Stringi yazdırırken bunu kullanacağız.
_____________________________

Kodum

#include <algorithm>
#include <string.h>
#include <stdio.h>
#define  maxc      26
#define  maxn      5004
using    namespace std;

int n,len;
char s[maxn];
int dp[maxn][maxc];
int best[maxn][maxc];

int f(int curr , int c)
{
  if(curr==len+1)  return 1;
  if(dp[curr][c])  return dp[curr][c];
  if(s[curr]=='=')
  {
    if(f(curr+1,c)==1)
    {
      best[curr][c]=c;
      return dp[curr][c]=1;
    }
  }
  if(s[curr]=='<')
  {
    for(int i=c+1 ; i<n ; i++)
      if(f(curr+1,i)==1)
      {
        best[curr][c]=i;
       return dp[curr][c]=1;
      }
  }
  if(s[curr]=='>')
  {
    for(int i=0 ; i<c ; i++)
      if(f(curr+1,i)==1)
      {
        best[curr][c]=i;
       return dp[curr][c]=1;
      }
  }
  return dp[curr][c]=2;
}

void Write(int x)
{
  printf("%c",x+'a');
  for(int i=1 ; i<=len ; i++)
  {
    x=best[i][x];
    printf("%c",x+'a');
  }
  printf("\n");
}

int main()
{
  scanf("%d%s",&n,s+1);
  len=strlen(s+1);
  bool ok=false;
  for(int i=0 ; i<n ; i++)
    if(f(1,i)==1)
    {
      Write(i);
      ok=true;
      break;
    }
  if(!ok) printf("-1\n");
  return 0;

}

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

The Child and Zoo

Enes Öncü'ye teşekkür ederiz.

Soru Metni

Size n düğüm ve m kenar içeren bir çizge veriliyor. Her düğümün bir değeri vardır.

İki düğüm arasındaki bir yolun değeri bu yol üzerindeki tüm düğümlerin değerlerinin en küçüğüne eşit oluyor.

f( p,q ) ise p den q ya giden yollardan değeri en büyük olan yolun değeri olarak tanımlanıyor.

 

Sizden istenen değerini bulmanız.

Yani tüm farklı p,q ikilileri için f(p,q) ların aritmetik ortalaması isteniyor.

İlk satırda n ve m (2 ≤ n ≤ 100000; 0 ≤ m ≤ 100000).

İkinci satırda düğümlerin değerleri a1, a2, ..., an (0 ≤ ai ≤ 100000).

Sonraki n satırda m adet kenar xi ve yi (1 ≤ xi, yi ≤ n; xi ≠ yi).

Örnek Girdiler

Girdi

4 3

10 20 30 40

1 3

2 3

4 3

Çıktı

16.666667

Girdi

3 3

10 20 30

1 2

2 3

3 1

Çıktı

13.333333

Girdi

7 8

40 20 10 30 20 50 40

1 2

2 3

3 4

4 5

5 6

6 7

1 4

5 7

Çıktı

18.571429

Not:

İlk örnek girdiyi düşünelim. 12 tane durum var:

•      p = 1, q = 3, f(p, q) = 10.

•      p = 2, q = 3, f(p, q) = 20.

•      p = 4, q = 3, f(p, q) = 30.

•      p = 1, q = 2, f(p, q) = 10.

•      p = 2, q = 4, f(p, q) = 20.

•      p = 4, q = 1, f(p, q) = 10.

Diğer 6 durum bunlara simetrik. Ortalamaları .

İkinci örnek girdiyi düşünelim. 6 tane durum var:

•      p = 1, q = 2, f(p, q) = 10.

•      p = 2, q = 3, f(p, q) = 20.

•      p = 1, q = 3, f(p, q) = 10.

Diğer 3 durum bunlara simetrik. Ortalamaları.

Linkler:http://codeforces.com/contest/438/problem/B

Çözüm Metni:

Öncelikle kenarlara belli bir değer verebiliriz. Eğer p düğümünden q düğümüne bir kenar varsa bu kenarı kullanırken hem p hem q düğümünden geçeceğiz. O zaman bu kenarın değerine min( a[p],a[q] ) diyebiliriz.

Elimizdeki kenarları değerlerine göre büyükten küçüğe sıralıyoruz. Ve elimize kenarları sıra sıra alıp bu kenarın daha önceden birbirine yol gelmeyen hangi düğümleri bağladığına bakıyoruz.

Mesela bu kenarın daha önce bağlı olmayıp şimdi bağladığı iki çizge grubundaki eleman sayıları s1 ve s2 olsun ve ekleyeceğimiz kenarın değeri b olsun. Bu s1 ve s2 elemanlı gruplardan birbirlerine b değerinde yollar olduğu bariz. Çünkü bundan önce gelen kenarların değerleri hep b den büyüktü ve bu iki grup arasında yol oluşuyorsa bu yolun maliyeti b olabilir. Peki niye daha büyük bir şey olamaz çünkü daha önce bu çizge parçalarından birbirine yol yoktu. O zaman s1*s2 tane p,q ikilisinin f(p,q) değeri b olur. Bu da toplamımızı s1*s2*b artırır. Eğer Simetriklerini de sayarsak 2*s1*s2*b artırır.

Sonuç olarak toplamımız ans ise ortalamamız ans/( n*(n-1) ) olur.

Algoritma:

Ayrık küme işlemlerini kullanacağız. Her kümede kaç tane eleman olduğunu kümenin atasında tutacağız. Yeni bir kenar geldiğinde eğer bu yolun birleştirdiği iki parça daha önceden birleştiyse bu kenar hiçbir f( p,q ) ' u en büyük yapamaz. Bu kenarı atlarız. Aksi taktirde cevabı yukarıda anlatıldığı şekilde güncelleriz ve bu iki ayrık kümeyi birleştiririz ve yeni kümenin eleman sayısı bu iki kümenin eleman sayısının toplamına eşit olur.

Çö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( lli  ii=aa;ii<=bb;ii++ )

#define FM( ii,aa,bb )           for( lli  ii=aa;ii>=bb;ii-- )

#define maxn        200000

using namespace std;

lli n,m,res,arr[maxn],ata[maxn],size[maxn];

pair< lli,pair<lli,lli> >        w[maxn];

int atabul( int nod ){

             return nod==ata[nod] ? nod : ata[nod] = atabul( ata[nod] );

}

void birlestir( int x,int y,lli c ){

             int a,b;

             a = atabul( x );

             b = atabul( y );

             res += size[a]*size[b]*c;

             size[a] += size[b];

             ata[b] = ata[a];

}

int main(){

             ios_base::sync_with_stdio( false );

       

             cin >> n >> m;

       

             FP( i,1,n )     cin >> arr[i],ata[i]=i,size[i]=1;

       

             FP( i,1,m ){

                    cin >> w[i].nd.st >> w[i].nd.nd;

                    w[i].st = min( arr[w[i].nd.st],arr[w[i].nd.nd] );

             }

       

             sort( w+1,w+m+1 );

       

             FM( i,m,1 ){

                    lli x,y,c;

                    x = w[i].nd.st;

                    y = w[i].nd.nd;

                    c = w[i].st;

                    if( atabul(x)!=atabul(y) )      birlestir( x,y,c );

             }

       

             cout << 2.0*res/(n*(n-1)) << endl;

}

Çorbada Tuzu Olmasını İsteyen

Burada elimizden geldiğince soru paylaşımına devam ediyoruz. Gelecek nesillere hem Türkçe kaynak oluşturmak açısından hem de o kaynakların çözüm alanı ve çözüm metinleriyle kendilerini geliştirmelerine ortam hazırlamaya çalışıyoruz. Bilmiyorum farkında mısınız ama blog bizim hayalimizdekinden yavaş ilerliyor ve biz de buna çare olarak blog takipçilerini de bu işe dahil etmeye karar verdik.

Sizden istediğimiz bu işin kalıcı olması ve daha büyük yerlere gelebilmesi için blogun formatına uygun bir dille yazılmış sorularınızı bize ulaştırmanız. Umarım bu iş için gönüllü olanlarınız çıkacaktır. Eğer blog formatına uygun olarak Türkçe soru metnini, çözüm metnini ve çözüm kodunu bize ulaştırırsanız gelecek nesillere faydalı bir iş yapmamıza katkıda bulunmuş olursunuz. Hepinizden bekliyorum. İyi çalışmalar.

Hack it!

Emin Ayar'a teşekkür ederiz.

Soru Metni

İkbal codeforceste sınav olurken şöyle bir soru karşısına çıktı.
f(x) x sayısının rakamları toplamını ifade etsin. ( örneğin , f(1234) = 1 + 2 + 3 + 4 )
Diğer bir deyişle :

ikbal problemi hemen çözdü ve hack aramaya başladı. önüne şöyle bir c++ kodu çıktı
 
ans = solve(l, r) % a;
if (ans <= 0)
    ans += a;
kod sadece l ile r arasının f değerleri toplamı a modunda 0 ise çalışmıyor.
Diğer bir deyişle:


GİRDİ
tek satırda bir integer a(1<=a<=10^18)
ÇIKTI
iki sayı l ve r (1 ≤ l ≤ r < 10^200) -- l ve r sayıları 0 ile başlayamaz ve her zaman bir çözümün var olduğu garanti edilmekte. birden fazla çözüm varsa herhangi birini yazabilirsiniz

Sample test(s)

input

46

output

1 10

input

126444381000032

output

2333333 2333333333333

Soru Linki: codeforces.com/contest/468/problem/C

Çözüm Metni:

1 ile (10^k)-1 arasındaki sayıların f değerleri toplamını bulması kolay.
şöyle ki k basamaktan birini k nın 1 lisi ile seçip ona 0..9 aralığındaki sayılardan birini koyarım. geriye kalan k-1 basamak 10^(k-1) farklı değer alır.
o halde 1....(10^k)-1 aralığındaki sayıların f değerleri toplamı 45*k*10^(k-1).

başlangıç olarak l yi 1 r yi ise 10^18 seçiyoruz.
şu anki toplamın moddaki değeri şuna eşittir;
ans=45*18*(10^17)+1 % a

eğer biz l ve r yi 1 er arttırırsak ans da bir artacaktır.

çünkü toplamdan eksilen sayı f(l) ve toplama eklenen sayı f(l+10^18) olur.
f(l+10^18)-f(l)=1 dir çünkü l+10^18 l nin soluna bir tane 1 konulmuş halidir.

eğer ans ı a ya ulaşıncaya kadar artırırsak mod a da sıfır olan bi aralık bulmuş oluruz.

Çözüm Kodu:

#include <bits/stdc++.h>
using namespace std;

typedef long long int Lint;
Lint a;

int main(){
    cin >> a;
    Lint l=1,r=1e18;
    Lint ans=(((9*(5*(9*(2*(Lint)1e17)%a)%a)%a)%a)+1)%a;
    cout << l+(a-ans) << ' ' << r+(a-ans) << endl;
    return 0;
}

Powerful Array

Enes Öncü' ye teşekkür ederiz.

Soru Metni

Size n elemandan oluşan bir dizi ve t adet l ve r ikilisi veriliyor.
Sizden her sorgu için dizinin l ve r aralığındaki altdizisinin Kuvvet Değeri isteniliyor.
Bir altdizideki Kuvvet Değeri şöyle tanımlanıyor:
Bir altdizideki s sayısının geçme sayısı Ks olsun. Tüm farklı s sayıları için Ks*Ks*s toplamı bize altdizinin Kuvvet degerini veriyor.

Size verilen t tane altdizinin Kuvvet Değerlerini ayrı ayrı bulmaniz.

1<=n,t<=200000
Tüm sayılar 1000000'den küçük.

Örnek 1:
3 2
1 2 1
1 2
1 3
Çıktı 1:
3
6

Örnek 2:
8 3
1 1 2 2 1 3 1 1
2 7
1 6
2 7
Çıktı 2:
20
20
20

İkinci örnek ilk sorgu için açıklama:

2. ve 7. indisleri arasında s = 1,2,3 olabiliyor.
Bu aralıkta:
K1 = 3
K2 = 2
K3 = 1 olur.
K1*K1*1+K2*K2*2+K3*K3*3 = 20 olur.

Soru Linki: http://codeforces.com/problemset/problem/86/D

Çözüm metni:

Soruyu çözmeye başlamadan önce tüm sorguları okuyoruz.

Başta tüm sorguları şu şarta göre sıralıyoruz:
a sorgusuyla b sorgusu elimizde olsun.
a -> l1,r1
b -> l2,r2
Eğer diziyi K'lik gruplara ayırdığımızda l1 ve l2 aynı gruptaysa: r1 ve r2 den hangisi küçükse onu daha önce cevaplıyoruz.
Eğer diziyi K'lik gruplara ayırdığımızda l1 ve l2 farklı gruptaysa: l1 ve l2 den küçük olanını önce cevaplıyoruz.

Aslında bundan sonrası amele bir çözüm olacak.

Elimizde sol,sag aralığı ve bu aralıgın cevabı olsun.
Sıradaki sorgu l,r aralığı olsun.

Eğer sağ imleci r den gerideyse sağ imlecini ilerletip cevabı güncelleriz.
Eğer sag imleci r den ilerideyse sağ imlecini geriye çekip cevabı güncelleriz.
Eğer sol imleci l den gerideyse sol imlecini ilerletip cevabı güncelleriz.
Eğer sol imleci l den ilerideyse sol imlecini geriye çekip cevabı güncelleriz.

Peki cevabı nasıl güncelleriz?

Bir dizide şu anda elimizde bulunan sayıların bu aralıkta geçme sayılarını tutarız. Yani her s için bi tane dizide Ks'i tutarız.
Bu diziye P[] diyelim.
Yeni bir eleman x ekleneceğinde cevaptan P[x]*P[x]*x çıkartır P[x]'i 1 artırır son olarak cevaba P[x]*P[x]*x ekleriz.
Altdizideki bir eleman x çıkartılacağında cevaptan P[x]*P[x]*x çıkartır P[x]'i 1 azaltır son olarak cevaba P[x]*P[x]*x ekleriz.

Peki ya maliyet ne oluyor?

Tum K'lık grupları ayrı ayrı inceleyelim.
Bir gurptaki r ler küçükten büyüğe sıralıdır.
Yani sağ imlecini bir grupta toplamda en fazla n kere ilerletebiliriz. Bu da n/K grup için n*n/K olur.
Bir gruptaki herhangi bir l den diğerine geçerken en fazla K işlem yaparız. Bu da t adet sorgu için t*K olur.

Bir gruptan diğer gruba geçerken l imleci en fazla 2*K kadar ilerleyebilir. n/K grup için 2*n maliyet gelir.
Bir gruptan diğer gruba geçerken r imleci en fazla n kadar geriye gelebilir. n/K grup için n*n/K maliyet gelir.

Peki K'yı kaç seçmeliyiz?

n*n/K+t*K yı en küçük yapabilmek için K'yı sqrt(n) seçmeliyiz.

Yani toplamda maliye O( (n+t)*sqrt(n) ) olur.


Çözüm Kodu:

#include <bits/stdc++.h>

#define st first
#define nd second
#define mp make_pair
#define lli long long int
#define FP( ii,aa,bb ) for( int ii=aa;ii<=bb;ii++ )

#define sqrtn 450

using namespace std;

int n,t,s[2000000],a[300000];
lli res,ans[300000],sqr[3000000];
pair< pair< int,pair<int,int> >,int > arr[300000];

int main(){

ios_base::sync_with_stdio( false );

cin >> n >> t;
FP( i,1,n ) cin >> a[i],sqr[i]=(lli)i*i;

FP( i,1,t ){
cin >> arr[i].st.nd.nd >> arr[i].st.nd.st,arr[i].nd = i;
arr[i].st.st = (arr[i].st.nd.nd-1)/sqrtn;
}

sort( arr+1,arr+t+1 );

int l=0,r=0;

FP( i,1,t ){
while( r<arr[i].st.nd.st ){
r++;
res -= a[r]*sqr[s[a[r]]];
s[a[r]]++;
res += a[r]*sqr[s[a[r]]];
}
while( r>arr[i].st.nd.st ){
res -= a[r]*sqr[s[a[r]]];
s[a[r]]--;
res += a[r]*sqr[s[a[r]]];
r--;
}
while( l<arr[i].st.nd.nd ){
res -= a[l]*sqr[s[a[l]]];
s[a[l]]--;
res += a[l]*sqr[s[a[l]]];
l++;
}
while( l>arr[i].st.nd.nd ){
l--;
res -= a[l]*sqr[s[a[l]]];
s[a[l]]++;
res += a[l]*sqr[s[a[l]]];
}
ans[arr[i].nd] = res;
}

FP( i,1,t )
cout << ans[i] << endl;

}

Pinball

Soru Metni

Alice pinball Oynamayı Çok sevmektedir pinball M+2 Satır N stundan oluşan bir grid üzerinde Oynanılmaktadır ilk satırdaki sutunların herhangi birinden düşmeye başlayan top en alt satıra ulaşıncaya kadar düşmeye devam eder. Alice bir gün grid Üzerine bazı aletler koyarak Oyunu kendisi için kolaylaştırabileceğini farkeder . Bu aletler sayesinde top hangi stundan düşmeye başlarsa başlasın son satıra hangi stunda ulaşacağı belli olsun istemektedir.M adet alet vardır.i numaralı alet yalnızca i+1 numaralı satıra konulabilir. Her alet 4 adet Sayı ile belirtilir.

abcd → bu alet satırın a ile b arasındaki stunlarını kapsamaktadır ve top bu aletin üzerine düşerse c numaralı stundan bir aşağıdaki satıra geçer .

Bu aleti koymanın maliyeti ise d kadardır .

Sizden istenen N M ve aletlerin özellikleri verildiğinde alicenin istediği şartı sağlıyacak şekilde aletleri minimum maliyette yerleştirmeniz.

Örnek girdilere bakarsanız soruyu daha rahat anlarsınız.

1<=M<=100000
2<=N<=1000000000
1<=a<=c<=b<=N
d<=1000000000

subtask 1(11 puan)
M<=10
N<=1000

subtask 2(18 puan)
M<=200

subtask 3(22 puan)
M<=1000

subtask 4(49 puan)
ek bir kisitlama belirtilmemiş

Örnek Girdi 1
5 6
2 4 3 5
1 2 2 8
3 6 5 2
4 6 4 7
2 4 3 10
Örnek Çıktı 1
25

Örnek girdinin şekli:

Örnek çıktının şekli:

Örnek Girdi 2
3 5
2 4 3 10
1 3 1 20
2 5 4 30
Örnek Çıktı 2
-1

Hiç bir türlü istenilen durum oluşmuyorsa cevaba -1 yazdırınız.

Test Data linki: cms.ioi-jp.org/open-2014/data/pinball-data.zip

Çözüm Metni

öncelikli olarak şunu farketmemiz gerekmekte;
1 numaralı stuna düşen topun da N numaralı stuna düşen topun da aynı stundan son satıra ulaşması için koyacağımız aletler v ye benzer bir şekil oluşturmalıdır.
diyelim ki son satıra düşeceği stun k numaralı stun olsun. k dan daha düşük numaraya sahip stunlara düşen topların sağa doğru; k dan büyük numaralı stuna düşen topların da sola ilerlemesi gerekmektedir. bi alet k numaralı stunun sağında bulunuyorsa ve üzerine düşen topları sağa taşıyorsa bu aleti kullanmak tamamen gereksizdir.

bu soruyu çözmek için 2 tane dinamik tutmamız gerekir.
1. dinamiğin a sı şunu belirmekte;
1. stun ile a numaralı stun arasına top düşerse topun  a numaralı stuna ulaşması şartını sağlayan minimum maliyet.

2. dinamiğin b si ise şunu belirmekte;
N numaralı stun ile b numaralı stun arasına top düşerse topun  b numaralı stuna ulaşması şartını sağlayan minimum maliyet.

bu iki dinamiği kullanarak satır satır aletleri elimize alıp bu aletin bütün topların düşeceği yeri belirleme durumundaki çözümü hesaplayalım. sonra da 2 dinamiği bu aleti kullanarak update edelim.

diyelim şu an incelediğim alet tüm topların  düşeceği yeri belirlesin ve l ile r arasındaki stunları kaplasın ve k numaralı yerden topu düşürsün ve  maliyeti de m olsun.
o halde çözüm 1. dinamiğin l ile r arasındaki minimum değer+2.dinamiğin l ile r arasındaki minimum değer+m olur.

bir sonraki satıra geçerken bu iki dinamiği de güncellememiz gerekmekte.
1. dinamiğin k sını,  1. dinamiğin l ile r arasındaki minimum +m ile güncellerim.
dn1[k]=min(dn1[k],dn1 de l ile r arası minimum+m);
2. dinamiğin k sını,  2. dinamiğin l ile r arasındaki minimum +m ile güncellerim.
dn2[k]=min(dn2[k],dn2 l ile r arası minimum+m);

çözüm bu haliyle tam puan almamaktadır.
çünkü farkediceğiniz üzere l ile r arasını tek tek gezmek M*N işleme kadar gidebilir.

girdide bize M adet alet verebilir ve aletler 3 farklı stunla ifade edilir.
biz sadece girdide verilen stunları kullanırsak maksimum 3*N tane stun olur.
yani diğer bir deyişle verilen sayıları sıkıştırmamız lazım.

Fakat bu haliyle de tam puan almıaycaktır çünkü karmaşıklığı 3*M*M e indirdik.
farkettiyseniz dinamiklerden bi aralığın minimum değerini alarak faydalanıyoruz.
o halde dinamikleri arrayde tutmaktansa segment tree yapısında tutarsak yapmamız gerek şey nokta updatesi ve aralık minimumu sorgulama olacaktır.

Çözüm Kodu

murat akburak in kodu:

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define fill(x,y) memset((x),(y) ,sizeof(x))
#define type(x) __typeof(x.begin())
#define sz(x) x.size()
#define o ((f+l)/2)
#define dg(x) #x << ": " << x << " " 
#define umax(x,y) (x)=max((x),(y))
#define NEW(x) (x *)calloc(1,sizeof(x))
#define umin(x,y) (x)=min((x),(y))
#define tmax(x,y,z) max((x),max((y),(z))) 
#define tmin(x,y,z) min((x),min((y),(z))) 
#define PI (M_PI)

using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef long long int Lint;
const int maxn = 100010;
const Lint inf = 1e15;

int N,M,f[maxn],p[maxn];
Lint seg[2][maxn*12];
ii er[maxn];
vector<ii> v;

Lint init( int k , int f , int l ){
if( f == l ) return seg[0][k] = seg[1][k] = inf ;
init( 2*k , f , o ) ;
init( 2*k+1 , o+1 , l ) ;
return seg[0][k] = seg[1][k] = inf ;
}

Lint upd( const int t , int k , int f , int l , int a , Lint val ){
if( a < f || l < a ) return seg[t][k];
if( f == l ) {
umin( seg[t][k] , val ) ;
return seg[t][k] ;
}
return seg[t][k] = min( upd( t , 2*k , f , o , a , val ) , upd( t , 2*k+1 , o+1 , l , a , val ) ) ; 
}

Lint find( const int t , int k , int f , int l , int a , int b ){
if( b < f || l < a ) return inf ;
if( a<=f && l <= b ) return seg[t][k] ;

return min( find( t , 2*k , f , o , a , b ) , find( t , 2*k+1 , o+1 , l , a , b ) );
}

Lint solve( ){
Lint ans = inf ;

for( int i=1 ; i<=N ; i++ ){
Lint left = find( 0 , 1 , 1 , M , er[i].fi , er[i].se ) ;
Lint right = find( 1 , 1 , 1 , M , er[i].fi , er[i].se ) ;
if( left != inf && right != inf ) umin( ans , left+right+p[i] ) ;
if( left != inf ) upd( 0 , 1 , 1 , M , f[i] , left+p[i] ) ;
if( right != inf ) upd( 1 , 1 , 1 , M , f[i] , right+p[i] ) ;
}

if( ans == inf ) ans = -1 ;

return ans ;
}

int main(){

scanf("%d %d",&N,&M);
v.pb( ii(1 , 0) ) , v.pb( ii( M , 0 ) ) ; M = 0 ;
for( int i=1 ; i<=N ; i++ ){
int a , b , c ;
scanf("%d %d %d %d",&a,&b,&c,&p[i]);
v.pb( ii( a , i ) );
v.pb( ii( b , i ) );
v.pb( ii( c , i ) );
}sort( all( v ) ) ;

for( int i=0 ; i<sz(v) ; i++ ){
if( !i || v[i].fi != v[i-1].fi ) M++;
if( ! er[v[i].se].fi ) er[v[i].se].fi = M ;
else if( ! f[v[i].se] ) f[v[i].se] = M ;
else if( ! er[v[i].se].se ) er[v[i].se].se = M ;
}

init( 1 , 1 , M );

upd( 0 , 1 , 1 , M , 1 , 0 ) ;
upd( 1 , 1 , 1 , M , M , 0 ) ;

cout << solve( ) << endl ;

return 0;
}