نوع سوال: Brute-Force (امتحان تمام حالات)

توضیح راه حل : با توجه به اینکه طول دنباله ای که باید آن را جستجو کنیم حداکثر برابر با 6 است، و اینکه E_i ها بين 0 تا 10 هستند، و با داشتن دنباله ی E_i ها می توان به آسانی بهترين دنباله ای که دارای اين دنباله E_i هست را پيدا کرد، تمام حالت های این دنباله را امتحان می کنیم. بنابراین حداکثر تعداد دنباله هايي که امتحان خواهيم کرد 11^6 است که با توجه به محدودیت زمانی زیاد نیست.

حال فرض کنید دنباله ی E_i ها مشخص است. مثلا فرض کنید این دنباله عبارت باشد از [1,2,3,1,0,1] . می خواهیم بهترین دنباله ای که دارای این دنباله E_i هست را بیابیم. مشاهده می کنید که سه عدد با E_i برابر با 1 باید انتخاب کنیم. با توجه به اینکه ضریب قبل از هر عدد بر روی آن عدد اعمال می شود، بنابراین ضریب هایی که بر روی این سه عدد اعمال خواهند شد عبارت خواهند بود از [0,3,0] (چون بر روی عدد اول در دنباله ضریب افزوده صفر اعمال می شود). اگر دنباله مرتب شده به صورت نزولی اعداد با E_i برابر با 1 عبارت باشد از [a_1, a_2, a_3, ...] ، همانطور که معلوم است، برای داشتن بهترین نتيجه، بزرگترین ضریب باید بر روی بزرگترین عدد اعمال شود. بنابراین، برای ضریب 3، a_1 را انتخاب می کنیم، و برای ضرایب 0 a_2 و a_3 را.

بخشی از کد من که بهترین نتیجه را برای دنباله ای خاص پیدا می کند:

 int64 check() {
    int64 result = 0;
    for( int i = 0; i < 11; i ++ ) 
        if( c[i] ) {
            int pt[10];
            for( int j = 0; j < c[i]; j ++ )
                pt[j] = p[i][j];
            sort( pt, pt + c[i] );
            reverse( pt, pt + c[i] );
            for( int j = 0; j < c[i]; j ++ ) {
                result += (10 + pt[j]) * (v[i][j] / 10);
            }
        }
    return result;
}

در کد بالا c[i] برابر با تعداد اعداد با ضریب i در دنباله ی فعلی است، و p[i][0..c[i]-1] شامل این ضرایب است. آرایه v[i] نیز شامل اعداد با E_i برابر با i بصورت نزولی است.

بخشی از کد که این دنباله را تولید می کند:

void bt( int idx, int enh ) {
    if( idx == 6 || idx == n ) {
        result = max( result, check() );
    } else {
        for( int i = 0; i < 11; i ++ )
            if( c[i] < v[i].size() ) {
                p[i][c[i]] = enh;
                c[i] ++;
                bt( idx + 1, i );
                c[i] --;
            }
    }
}

این سوال تقریبا آسان ترین سوال این مسابقه محسوب می شود.

3675 - Telescope

لینک سوال: http://acm.pku.edu.cn/JudgeOnline/problem?id=3675

نوع سوال: هندسه محاسباتی

توضیح راه حل : برای حل این سوال ابتدا چند ضلعی را به تعدادی مثلث مجزا از هم که چندضلعی را می پوشانند تقسیم می کنیم و سپس اشتراک هر کدام از مثلث ها را با دایره پیدا می کنیم و پاسخ نهایی را بدست می آوریم.

برای آشنایی برای روش های مثلث بندی چندضلعی به ويکيپدیا مراجعه کنید. با توجه به اینکه تعداد رئوس چندضلعی کم بود، من از الگوريتم ساده ای با پيچيدگی O(n^3) برای این بخش استفاده کردم. برای یافتن یک مثلث، هر 3 راس پشت سر هم a و b و c چند ضلعی را امتحان می کردم. اگر راس وسطی به طرف داخل چند ضلعی نبود (یعنی پاره خط a به c داخل چندی ضلعی قرار می گرفت)، و همچنین هيچ راس دیگری از چند ضلعی داخل یا در مرز این مثلث قرار نمی گرفت، این مثلث را به مجموع مثلثات اضافه می کردم و راس b را حذف می کردم. با توجه به اینکه با این روش n - 2 مثلث برای چندضلعی پیدا می شود و یافتن هر مثلث به زمان O(n^2) نیاز دارد، پيچيدگی کل این الگوریتم O(n^3) است.

کد من برای این بخش را در زیر مشاهده می کنید. آرایه v شامل نقاط چند ضلعی است و تابع product ضرب خارجی دو بردار را می یابد.

double triangulate() {
    double result = 0.0;
    for( int it = 0; it < n - 2; it ++ ) {
        for( int a = 0; a < v.size(); a ++ ) {
            int b = (a + 1) % v.size();
            int c = (a + 2) % v.size();
            bool valid = ( product( v[c] - v[a], v[b] - v[a] ) < eps );
            for( int i = 0; i < v.size() && valid; i ++ )
                if( i != a && i != b && i != c && insideTriangle( v[i], v[a], v[b], v[c] ) )
                    valid = false;
            if( valid ) {
                // A new triangle is found
                // Do the calculations here 
                result += intersect( v[a], v[b], v[c] ); // intersects a,b,c with the circle.
                v.erase( v.begin() + b );
                break;
            }
        }
    }
    return result;
}

برای پیدا کردن اشتراک مثلث و دایره حداقل دو راه مختلف وجود دارد. روش اول این است که تمام حالت های دایره و مثلث را در نظر بگيريم. برای آشنایی با این روش به این لینک مراجعه کنید. این روش دقت بسیار زیادی نیاز دارد.

روش دوم ساده تری که من از آن استفاده کردم، این است که ضلع های مثلث را به ترتیب پیمایش کنیم، و رئوس داخل دایره و تقاطع اضلاع با دایره را بدست بیاوريم (که یک چند ضلعی تشکیل می دهد). در این صورت مساحت اشتراک برابر خواهد بود با مساحت این چند ضلعی به اضافه ی مساحت کمان هایی از دایره. این کمان ها هم زمانی ایجاد می شوند که قبلا از دایره خارج شده باشیم و دوباره به دایره برگردیم که در این صورت کمان بین دو نقطه برخورد را به پاسخ اضافه می کنیم.

یک حالت خاص این است که تنها یک ضلع مثلث از دایره بگذرد و هیچ نقطه ای از مثلث داخل دایره نباشد، که در این صورت پاسخ برابر با مساحت یک کمان است. حالت خاص دیگر این است که هیچ ضلعی از مثلث داخل دایره نباشد و مرکز دایره داخل مثلث باشد که در این صورت نیز پاسخ برابر با مساخت کل دایره است.

بخشی از کد من برای این بخش در زیر آمده است:

double intersect( P a, P b, P c ) {
	vector<P> v;
	double result = 0;
	result += add( v, a, b );
	result += add( v, b, c );
	result += add( v, c, a );
	if( v.size() && onBorder(v.back()) && onBorder(v[0]) )
		result += arc( v.back(), v[0] );
	if( v.size() == 0 && insideTriangle( P(0, 0), a, b, c ) )
		result += pi * r * r;
	result += fabs( area( v ) );
	return result;
}

تابع add تقاطع ضلع با دایره را پیدا می کند و نقاط مناسب را به v اضافه می کند. در صورتیکه با محیط دایره تقاطع وجود داشته باشد و آخرین نقطه ای که به v اضافه شده است نیز در محیط دایره قرار داشته باشد، مساحت کمان بین آن نقطه و اولین تقاطع این ضلع را به پاسخ اضافه می کنیم:

double add( vector<P>& v, P a, P b ) {
    ...
    if( t1 > -eps && t1 < 1 + eps ) {
        P p( a.x + ( b.x - a.x ) * t1, a.y + ( b.y - a.y ) * t1 );
        if( v.size() && onBorder( v.back() ) )
            result += arc( v.back(), p );
        ...
    }
    ....
    return result;
}

تابع arc نیز به صورت زیر پیاده سازی شده است:

double arc( P a, P b ) {
	double alpha = getAngle( a ), beta = getAngle( b );
	double delta = ( beta >= alpha ) ? (beta - alpha) : (2 * pi - alpha + beta);
	double result = r * r * delta * 0.5 - fabs( product( a, b ) * 0.5 );
	return result;
}

تنها نکته ی دیگر که ممکن است آموزنده باشد این است که در بخشی از این کد نیاز به محاسبه ی آرک کسینوس داشتم. با توجه به اینکه ممکن است خطای محاسباتی رخ دهد و مقداری کمی بزرگتر از 1 به جای 1 یا مقداری کمی کوچکتر از 1- به 1- ایجاد شود، که در این صورت تابع acos مقدار NaN بر می گرداند، از تابع زیر استفاده کردم:

double acos2( double a ) {
    if( fabs(a - 1.0) < eps )
        return 0;
    if( fabs(a + 1.0) < eps )
        return pi;
    return acos( a );
}

3676 - Tomorrow Genius 2008

لینک سوال: http://acm.pku.edu.cn/JudgeOnline/problem?id=3676

نوع سوال: جستجو (Backtracking)

توضیح راه حل : این سوال تنها سوالی از این مجموعه سوال است که موفق به حل آن نشده ام. ولی به نظر می رسد که این مساله نوعی مساله ی جستجو است که در هر مرحله یک چندضلعی داریم (که در ابتدای کار این چندضلعی برابر با مستطیل اولیه است)، و باید در اولین زاویه ی این چند ضلعی، یکی از مثلث ها را به سمت چپ بچسبانیم، که یک چندضلعی جدید بوجود می آید و به صورت بازگشتی پاسخ را برای چندضلعی جدید پیدا کنیم. اگر یکی از انتخاب های مثلث منجر به جواب YES شود، مقدار YES بر می گردانیم و در غیر این صورت NO برمی گردانیم.

3677 - Chemical Weighing

لینک سوال: http://acm.pku.edu.cn/JudgeOnline/problem?id=3677

نوع سوال: جستجو - نظریه گراف

توضیح راه حل : با توجه به اینکه تعداد تمام حالت های پشته در این مساله کمتر از 27000 است و 500*27000 خیلی زیاد نیست، از BFS برای حل این مساله استفاده کردم.

ابتدا تمام حالت های پشته را با استفاده از تابع زیر پیدا می کنم:

void generate_tree() {
	fill( seen, seen + 31, false );
	tree_size = 1;
	tree_w[0] = 0, tree_l[0] = 0, tree_p[0] = -1;
	for( int i = 0; i < tree_size; i ++ ) {
		tree_f[ i ] = tree_size;
		tree_c[ i ] = 0;
		seen[ tree_w[ i ] ] = true;
		for( int j = tree_l[ i ]; j < n; j ++ )
			if( tree_w[ i ] + w[ j ] <= 30 ) {
				tree_c[ i ] += 1;
				tree_w[ tree_size ] = tree_w[ i ] + w[ j ];
				tree_l[ tree_size ] = j;
				tree_p[ tree_size ] = i;
				tree_size += 1;
			}
	}
}

که tree_w نشان گر وزن های هر گره است، tree_f شماره ی اولین فرزند هر گره است، tree_c تعداد فرزندهای هر گره است، tree_p والد هر گره است، و tree_l شماره ی بالاترین وزنه هر گره است.

رئوس گرافی که در آن به دنبال کوتاهترین مسیر می گردیم با جفت (node, idx) مشخص می شود که node شماره ی گره در این درخت حالات است و idx اندیس اندازه گیری ایست که می خواهیم آن را بسازیم. حالت آغازین برابر است با (0, 0) و حالت پایانی برابر است با (x, m) که در آن x هر عددی می تواند باشد و m تعداد اندازه گیری هاست.

البته پیاده سازی این BFS چندان آسان نیست و بیشتر از 1 ساعت (پس از نوشتن کد اولیه) تولید کشید تا بتوانم BFS را بهینه کنم تا در محدودیت زمانی 1 ثانیه جواب دهد و Accept شود.

3678 - Katu Puzzle

لینک سوال: http://acm.pku.edu.cn/JudgeOnline/problem?id=3678

نوع سوال: ارضای قیود - 2SAT

توضیح راه حل : این مساله را به آسانی می توان به صورت مساله ی 2SAT مدل کرد. بخشی از کد که مساله را تبدیل به 2SAT می کند:

for( int i = 0; i < m; i ++ ) {
    scanf("%d %d %d %s", &a, &b, &c, s);
    if( strcmp(s, "OR") == 0 ) {
        if( c == 0 ) {
            add(NOT(a), NOT(a));
            add(NOT(b), NOT(b));
        } else {
            add(a, b);
        }
    } else if( strcmp(s, "AND") == 0 ) {
        if( c == 1 ) {
            add(a, a);
            add(b, b);
        } else {
            add(NOT(a), NOT(b));
        }
    } else if( c == 0 ) {
        add(NOT(a), b);
        add(a, NOT(b));
    } else {
        add(NOT(a), NOT(b));
        add(a, b);
    }
}

برای آشنایی با مساله 2SAT و چگونگی حل آن به این لینک مراجعه کنید.

3679 - The Delivery of Control

لینک سوال: http://acm.pku.edu.cn/JudgeOnline/problem?id=3679

نوع سوال: Brute-Force (امتحان تمامی حالات)

توضیح راه حل : با توجه به اینکه تعداد مسیرهای بسته ی به طول حداکثر 20 زیاد نیست (حدود 102000 حالت)، می توان این مسیرها را تولید کرد و هر کدام را امتحان کرد. بخشی از کد من که این مسیرها را تولید می کند:

void dfs( tile t ) {
	if( t.len > tt || t.h > n || t.w > m )
		return;
	if( visited[t.w][t.bitmask >> 3] & (1 << (t.bitmask & 7)) )
		return;
	visited[t.w][t.bitmask >> 3] |= (1 << (t.bitmask & 7) );
	check( t );
	for( int x = 0; x < t.h; x ++ )
		for( int y = 0; y < t.w; y ++ )
			if( t.get(x, y) )
				for( int i = 0; i < 4; i ++ ) {
					int nx = x + dx[i], ny = y + dy[i];
					if( !t.get( nx, ny ) ) {
						dfs( t.set( nx, ny ) );
					}
				}
}
 
void generate_tiles() {
	memset(visited, 0, sizeof visited);
	visited[3][3951] = true;
	visited[4][3999] = true;
	cnt = 0;
	dfs( tile(1, 1, 1, 4) );
}

که tile ساختاری است که خودم ساخته ام و پیاده سازی آن سخت نیست. دو حالت 3,3951 و 3,3999 تنها حالت هایی هستند که سوراخی به اندازه ی 1×2 دارند، که در ابتدای کار آن ها را مارک می کنم تا آن ها را بررسی نکنم. وجود سوراخ 1×1 را در تابع check تست می کنم.

البته این روش به حافظه ی زیادی نیاز دارد. می توان از روشی dfs مانند برای یافتن این مسیر استفاده کرد، این گونه که از نقطه ی پائین سمت چپ مسیر شروع می کنیم و مسیر را می سازیم، و در هر مرحله مسیر را به یکی از چهار طرف امتداد می دهیم، و دقت می کنیم که پایین تر از نقطه ی آغاز نرويم، و اگر هم ارتفاع با آن بود به سمت چپ آن نرویم، تا مسیر های تکراری ایجاد نکنیم. همچنین باید جاهایی را که رد می شویم را علامت گذاری می کنیم تا مسیر با خود تقاطع نداشته باشد.

3680 - Intervals

لینک سوال: http://acm.pku.edu.cn/JudgeOnline/problem?id=3680

نوع سوال: نظریه گراف

توضیح راه حل : این سوال را می توان به صورت min cost max flow مدل کرد. مدل سازی این گراف را در کد زیر مشاهده می کنید:

void addEdge( int a, int b, int capacity, int cost );
 
int main() {
    for( scanf("%d", &t); t--; ) {
        scanf("%d %d", &n, &k);
        xc = 0;
        for( int i = 0; i < n; i ++ ) {
            scanf("%d %d %d", &arr[i][0], &arr[i][1], &arr[i][2]);
            xs[xc++] = arr[i][0] ;
            xs[xc++] = arr[i][1] ;
        }
        sort( xs, xs + xc );
        xc = unique(xs, xs + xc) - xs;
        int src = xc, trg = xc + 1;
        ec = 0;
        addEdge( src, 0, k, 0 );
        addEdge( xc - 1, trg, k, 0 );
        for( int i = 1; i < xc; i ++ )
            addEdge( i - 1, i, k, 0 );
        for( int i = 0; i < n; i ++ )
            addEdge( find( arr[i][0] ), find( arr[i][1] ), 1, arr[i][2] );
        printf("%d\n", maxcost( xc + 2, src, trg ));
    }
    return 0;
}

البته من به جای min cost از max cost استفاده کردم، در صورتیکه بخواهیم از min cost استفاده کنیم، هزینه یال ها باید منفی آن چه در این کد است استفاده شود.

با توجه به اینکه یال منفی داریم، برای پیدا کردن min cost max flow، که در هر مرحله کوتاهترین مسیر هزینه ای را پیدا می کنیم، از Bellman-Ford استفاده کردم. اگر بخواهید از Dijkstra استفاده کنید، برای مقداردهی ابتدایی پتانسیل ها باید از Bellman-Ford استفاده کنید. ولی با توجه به اینکه سایز گراف و حداکثر جریان زیاد نمی باشد، Bellman-Ford برای حل این مساله کافی است و کد آن نیز آسان تر است.

برای آشنایی با چگونگی حل مساله min cost max flow، به این لینک یا این لینک مراجعه کنید.

3681 - Finding the Rectangle

لینک سوال: http://acm.pku.edu.cn/JudgeOnline/problem?id=3681