USACO : Packing Rectangles


প্রায় এক বছর পর এই প্রবলেমটা সলভ করতে পারলাম। অবশ্য এক বছর ধরেই যে চেষ্টা করতেছি এমন না, তবে প্রায়ই প্রবলেমটার দিকে হতাশ চোখে চেয়ে থাকতাম । ফোরাম এ বিভিন্ন পোষ্ট পড়তাম, কিছু আইডিয়া আসত মাথায়, তবে সলভ করার জন্য সেগুলা যথেষ্ট ছিল না ।

আমার এনএসইউর বন্ধু পল্লব তখন চ্যাপ্টার : ২ তে, কাজেই সে এই প্রবলেম সলভ করেছে এটা নিশ্চিত । তাকে একদিন সামনে পেয়ে ভালমত ধরলাম । সে বলল, ভাই রে ভাই, এই প্রবলেমটার কথা আমি কিভাবে ভুলি, এটা আমার নাকের জল চোখের জল সব একাকার করে দিয়েছে, প্রবলেমটা আমি ভালমত বুঝিও নাই । যাইহোক, পল্লব বলল, এই সেকশনের বাকী প্রবলেমগুলা সলভ হয়ে যাবার পরও এই একটা প্রবলেমের জন্য সে বহুদিন আটকে ছিল, তাই বিরক্ত হয়ে সে অন্যকারও কোড কপি করে দিয়েছিল 😛

কাব্যের ভাষায় বলতে গেলে বলতে হয়, তারপর কেটে গেছে আরো কিছু সময় …

ততদিনে শান্ত ভাই আমাদের নতুন কিছু শেখানোর চেষ্টা শুরু করছিলেন । আর আমিও মহা উদ্যমে ফাকিবাজির ১০১ টি উপায়বইয়ের কৌশলগুলো প্রয়োগ করে দেখছিলাম, সেগুলা আসলে কাজ করে কিনা
এতদিন তো ভালই কাজ করছিল .. তারপর একদিন হঠাৎ করে শান্ত ভাই অশান্ত হয়ে একখানা বেশ ভালো সাইজের ..

যাক সেসব পুরোনো কথা, তো আমি শান্ত ভাইকে জিজ্ঞেস করলাম, ভাই এই প্রবলেমটা কিভাবে করা যায় ?
তিনি বললেন, তুমি প্রবলেমটার সোর্স IOI 95 সার্চ করে দেখো
সার্চ করলাম, একটা অ্যানালাইসিস পেলাম, সেটা মন দিয়ে পড়লাম, পড়ে খুব ভাল লাগল, কিছু বুঝতে পারলে হয়তো আরো ভাল লাগত । শান্ত ভাইকে আবার ধরলাম । তিনি বললেন, আসলে প্রবলেমটা খুব সহজ । তবে প্রথমে আমিও এটা করতে পারি নাই । তারপর অ্যনালাইসিস দেখার পর মনে হইছে খুবই ফালতু প্রবলেম ।
আমি মনে মনে বললাম, তা তো বটেই, সলভ করে ফেলার পর সবাই এইকথাই বলে

তো এখন আমি প্রবলেমটার একটা বাংলা সলিউশন দিতে যাচ্ছি । খুব একটা সহজ হয়তো মনে হবে না তবে কাজে লাগতে পারে ।

মূল ব্যাপারটা হচ্ছে, কতগুলা চতুর্ভূজকে এমনভাবে রাখতে হবে যেন তাদের ক্ষেত্রফর সর্বনিম্ন হয়। উপরে ৬ টা ছবি দেয়া আছে এবং এগুলোর বাইরে আর কোনভাবে চারটা চতুর্ভূজ রাখা সম্ভব নয় । এখন আমাদের যেটা করতে হবে সেটা হচ্ছে, উপরের ৬ টা ছবি দেখে যত রকমভাবে ৪ টা চতুর্ভূজ রাখা যায় সবগুলা চেষ্টা করে দেখা।

১ম ছবিতে ৪টাই পাশাপাশি দাড়ানো
২য় ছবিতে ১টা নীচে এবং বাকীগুলা তার উপরে
এখানে কথা হল, যেটা নীচে সেটা আসলে কোনটা ?
আমাদের কাছে তো ৪টা চতুর্ভূজ আছে তাই না ? এগুলাকে যদি নাম্বার দিই যেমন : , , ,
তাহলে যেটা নীচে আছে সেটা কোনটা ? ১ নাকি ২ নাকি ৩ নাকি ৪ ??
আসলে সবগুলাই একটা একটা করে চেক করে দেখতে হবে
যেমন : প্রথমে ১ নাম্বারটা নীচে এবং ২, , ৪ উপরে
তারপর, ২ নাম্বারটা নীচে এবং ১, , ৪ উপরে
তারপর, ৩ নাম্বারটা নীচে এবং
তারপর, ৪ নাম্বারটা …….

এইভাবে কতগুলা কম্বিনেশন সম্ভব ?
৪ টা চতুর্ভূজ দিয়ে ৪! = ২৪ টা কম্বিনেশন সম্ভব, সবগুলাই চেক করে দেখতে হবে

মজা এইখানেই শেষ হয় নাই, আরও আছে …….
১ম ছবিতে ৪ টা পাশাপাশি দাড় করিয়ে রাখা, কিন্তু এদের কে শোয়াই দিলে কেমন হয় ?
তারমানে দাড়াল, ওই ২৪ টা কম্বিনেশনের সবগুলাকে একবার দাড় করায়ে আবার শোয়ায়ে চেক করতে হবে

একটা চতুর্ভূজ হয় দাড়ানো থাকবে, নাহয় শোয়ানো। মানে, = ১৬ রকম
মোট, ২৪ * ১৬ = ৩৮৪ রকমভাবে সাজানো যায়
মানে একটা ছবিকেই ৩৮৪ রকমভাবে সাজানো যায়, এমন ছবি আছে ৬ টা ।
অর্থ্যাৎ, ৩৮৪ * = ২৩০৪ রকমভাবে সাজানো যায়
এবং সবগুলাই একটা একটা করে চেক করে দেখতে হবে

৪ এবং ৫ নাম্বার ছবিটা আসলে একইরকম । কাজেই, ৩৮৪ * = ১৯২০ রকম চেক করলেই হবে ।

তাহলে তুমি সবগুলা চেক করার একটা জোশ কোড লিখে ফেলো, ঠিক আছে ? বেস্ট অফ লাক 🙂

ওহো, বাংলা সলিউশনটা তো দিলাম না !

আচ্ছা, প্রথমে আমরা সেই ২৪ টা কম্বিনেশন (আসলে এগুলা পারমিউটেশন) দেখি,
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

এখন ওই ১৬ রকমভাবে সাজানোর ব্যাপারটা দেখা যাক ।
একটা চতুর্ভূজকে দাড়ানো থেকে শোয়ানো করতে হলে, সেটার দৈর্ঘ্য আর প্রস্থ swap করে দিতে হবে ।
একইভাবে শোয়ানো থেকে দাড়ানো করতে হলে, সেটার দৈর্ঘ্য আর প্রস্থ swap করে দিতে হবে ।
মনে করি ০ মানে চতুর্ভূজটি দাড়ানো আর ১ মানে শোয়ানো

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

আমরা ৪ নাম্বার ছবিটার দিকে তাকাই । ৩ টা চতুর্ভূজ পাশাপাশি থাকবে এবং একটার উপরে ৪র্থ চতুর্ভূজটা থাকবে । যেকোন একটা ছবির জন্য মোট কতভাবে সাজানো যায় ? ২৪ * ১৬ = ৩৮৪ রকম ।
১ম পারমিউটেশনটা হল, , , ,
ধরা যাক, , , ৩ পাশাপাশি আছে এবং ৪ নাম্বারটা উপরে আছে
দাড়ানো/শোয়ানো ১মটা নিলাম, ০০০০ : মানে ৪ টাই দাড়ানো আছে
এই অবস্থায়, এই ৪ টা চতুর্ভূজেরর উত্তর বের করতে হবে ।

.

.

অন্য একটা পারমিউটেশন নিলাম, , , ,
মানে, , , ৪ পাশাপাশি আছে এবং ১ নাম্বারটা উপরে আছে
দাড়ানো/শোয়ানো নিলাম, ১০০১
মানে ৩ এবং ১ নাম্বর চতুভূর্জ শোয়ানো বাকী ২ টা দাড়ানো
দাড়ানো/শোয়ানো যদি ০১১১ নিতাম ?
তার মানে, ৩ দাড়ানো বাকীগুলো শোয়ানো

বুঝা যাচ্ছে ব্যাপারটা ?

আমরা এখন ১ম ছবিটার জন্য কাজ করছি,
ধরে নিলাম আমি পারমিউটেশন এবং দাড়ানো/শোয়ানো ব্যাপরটা ঠিক করে ফেলেছো
তাহলে, ১ম ছবিতে কিভাবে চতুর্ভূজগুলো আছে ?
৪ টা চতুর্ভূজ পাশাপাশি আছে । এখন আমাদের ক্ষেত্রফল বের করতে হবে
ক্ষেত্রের উচ্চতা = কি হবে ?
এই ৪টা চতুর্ভূজের মধ্যে যেটা সবচেয়ে লম্বা সেটাই হবে ক্ষেত্রের উচ্চতা
height = max (h1, h2, h3, h4)
ক্ষেত্রের প্রস্থ = ?
৪ টা চতুর্ভূজের প্রস্থের যোগফল
width = w1 + w2 + w3 + w4

আজকে আর লিখতে ইচ্ছে করছে না .. অন্যদিন নাহয় বাকী অংশটা শেষ করব

/*
ID: tausiq11
PROG: packrec
LANG: C++
*/

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#define INT_MAX 2147483647
#define INT_MIN -2147483648
#define pi acos(-1.0)
#define N 1000000
#define long long LL
using namespace std;

struct rectangle {
    int index;
    int h;
    int w;
    bool ori;
} r [4];

struct area {
    int h;
    int w;
    int h_w;
} a [24 * 16 * 5 + 10];

int index_a;

void convert_binary (int b, char *p)
{
    if ( b == 0 ) {
        p [0] = '0';
        p [1] = 0;
        return;
    }

    for ( int i = 3; i >= 0; i-- ) {
        p [i] = (b & 1) + '0';
        b >>= 1;
    }
}

void iterate (int b)
{
    char bin [4 + 3];
    convert_binary (b, bin);

    for ( int i = 0; i < 4; i++ ) {
        if ( bin [i] == '0' && r [i].ori == true ) {
            r [i].ori = false;
            swap (r [i].h, r [i].w);
        }
        else if ( bin [i] == '1' && r [i].ori == false ) {
            r [i].ori = true;
            swap (r [i].h, r [i].w);
        }
    }
}

bool cmp (rectangle x, rectangle y)
{
    if ( x.index < y.index ) return true;
    return false;
}

bool cmp1 (area x, area y)
{
    if ( x.w < y.w ) return true;
    return false;
}

int max4 (int p, int q, int r, int s)
{
    return max (p, max (q, max (r, s)));
}

int max3 (int p, int q, int r)
{
    return max (p, max (q, r));
}

void pic1 ()
{
    a [index_a].h  = max4 (r [0].h, r [1].h, r [2].h, r [3].h);
    a [index_a].w  = r [0].w + r [1].w + r [2].w + r [3].w;
    a [index_a].h_w = a [index_a].h * a [index_a].w ;
    index_a++;
}

void pic2 ()
{
    a [index_a].h  = r [0].w + max3 (r [1].h, r [2].h, r [3].h);
    a [index_a].w  = max (r [0].h, r [1].w + r [2].w + r [3].w);
    a [index_a].h_w = a [index_a].h * a [index_a].w ;
    index_a++;
}

void pic3 ()
{
    a [index_a].h  = max (r [3].h, max (r [1].h, r [2].h) + r [0].w);
    a [index_a].w  = r [3].w + max (r [0].h, r [1].w + r [2].w);
    a [index_a].h_w = a [index_a].h * a [index_a].w ;
    index_a++;
}

void pic4 ()
{
    a [index_a].h  = max3 (r [1].h + r [2].h, r [0].h, r [3].h);
    a [index_a].w  = r [0].w + r [3].w + max (r [1].w, r [2].w);
    a [index_a].h_w = a [index_a].h * a [index_a].w ;
    index_a++;
}

void pic5 ()
{
    a [index_a].h  = max (r [0].h + r [2].h, r [1].h + r [3].h );
    if ( r [0].h == r [1].h )
        a [index_a].w = max (r [0].w + r [1].w, r [2].w + r [3].w);
    else if ( r [0].h < r [1].h ) {
        if ( r [1].w >= r [3].w )
            a [index_a].w = max (r [0].w + r [1].w, r [2].w + r [1].w);
        else {
            if ( r [0].h + r [2].h <= r [1].h )
                a [index_a].w = max3 (r [0].w + r [1].w, r [2].w + r [1].w, r [3].w);
            else
                a [index_a].w = max (r [0].w + r [1].w, r [2].w + r [3].w);
        }

    }
    else {
        if ( r [0].w >= r [2].w )
            a [index_a].w = max (r [0].w + r [1].w, r [0].w + r [3].w);
        else {
            if ( r [1].h + r [3].h <= r [0].h )
                a [index_a].w = max3 (r [0].w + r [1].w, r [0].w + r [3].w, r [2].w);
            else
                a [index_a].w = max (r [0].w + r [1].w, r [2].w + r [3].w);
        }
    }
    a [index_a].h_w = a [index_a].h * a [index_a].w ;
    index_a++;
}

int main ()
{
    freopen ("packrec.in", "r", stdin);
    freopen ("packrec.out", "w", stdout);

    for ( int i = 0; i < 4; i++ ) {
        scanf ("%d %d", &r [i].h, &r [i].w);
        r [i].index = i;
        r [i].ori = false;
    }

    index_a = 0;

    do {
        for ( int i = 0; i < 16; i++ ) {
            iterate (i);

            pic1 ();
            pic2 ();
            pic3 ();
            pic4 ();
            pic5 ();
        }
    } while ( next_permutation (r, r + 4, cmp));

    int min_area = INT_MAX;

    for ( int i = 0; i < index_a; i++ ) {
        if ( a [i].h_w < min_area ) min_area = a [i].h_w;
    }

    printf ("%d\n", min_area);

    for ( int i = 0; i < index_a; i++ ) {
        int maximum = max (a [i].w, a [i].h);
        int minimum = min (a [i].w, a [i].h);
        a [i].w = minimum;
        a [i].h = maximum;
    }

    sort (a, a + index_a, cmp1);
    int p = 0, q = 0;

    for ( int i = 0; i < index_a; i++ ) {
        if ( a [i].h_w == min_area ) {
            if ( a [i].w != p && a [i].h != q ) {
                printf ("%d %d\n", a [i].w, a [i].h);
                p = a [i].w;
                q = a [i].h;
            }
        }
    }

	return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

2 thoughts on “USACO : Packing Rectangles

  1. not like that its not possible! .. currently i am going through a busy time but i will surely keep your suggestion in mind .. thank you 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s