23 Eylül 2014 Salı

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

Hiç yorum yok:

Yorum Gönder