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

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;

}