بررسی سوالات مسابقه Topcoder Single Round Match 443

بررسی سوالات مسابقه Topcoder Single Round Match 443

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

فرض کنید کشور دایره ها صفحه ای نامحدود است. شما آرایه های X و Y و R را به عنوان ورودی می گیرید، بطوریکه (X[i], Y[i]) مختصات مرکز بخش i ام است، و R[i] شعاع آن بخش است. مختصات مکان فعلی قطام (x1, y1) و مختصات مقصد او (x2, y2) است، که هیچ کدام از این دو نقطه در مرز هیچ بخشی قرار ندارند. کمترین تعداد مرز بخشی که قطام باید از آن عبور کند تا به مقصد برسد را پیدا کنید.

تعریف تابع و کلاس

class CirclesCountry {
public:
   int leastBorders(vector <int> X, vector <int> Y, vector <int> R, int x1, int y1, int x2, int y2);
};

محدودیت ها

X دارای بین 1 تا 50 عنصر است.
تعداد عناصر X و Y و R برابر است.
هرکدام از عناصر X و Y بین 1000- تا 1000 است.
هرکدام از عناصر R بین 1 تا 1000 است.
x1 و x2 و y1 و y2 بین 1000- تا 1000 هستند.
محیط هیچ دو دایره ای نقطه ی مشترک ندارند.

توضیح راه حل

دایره ها نسبت به نقطه شروع و پایان دارای سه حالت هستند:

هیچ کدام از این نقاط داخل این دایره نیستند. در این صورت نیازی نداریم از مرز این دایره رد بشویم. چون می توان بین دو نقطه ی خارج از این دایره بدون رد شدن از این دایره مسافرت کرد.
هر دوی این نقاط داخل این دایره هستند. باز هم می توانیم از مرز این دایره رد نشویم.
یکی از نقاط داخل این دایره است. در این صورت باید از مرز این دایره حتما رد بشویم.

بنابراین تنها باید تعداد دایره هایی را بشماریم که یکی از نقاط داخل آن است و دیگری داخل آن نیست.

البته می توانستیم درختی از دایره ها بسازیم، بطوریکه ریشه صفحه باشد، و دایره هایی داخل هیچ دایره دیگری نیستند فرزند ریشه باشند، و دایره a فرزند دایره b باشد اگر دایره b کوچکترین دایره ایست که دایره a درون آن قرار دارد. و سپس با استفاده از این درخت کوتاهترین مسیر این دو نقطه را پیدا کنیم، که این روش سخت تر و بدتر از روش قبلی است.

کد حل مساله

class CirclesCountry {
public:
   int leastBorders(vector <int> X, vector <int> Y, vector <int> R, int x1, int y1, int x2, int y2) {
      int result = 0;
      for( int i = 0; i < X.size(); i ++ )
         if( (hypot(X[i] - x1, Y[i] - y1) < R[i]) != (hypot(X[i] - x2, Y[i] - y2) < R[i]) )
            result += 1;
      return result;
   }
};

سوال متوسط - BinaryFlips

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

صورت مساله

شما در حال انجام بازی ای هستید که در ابتدا A تا صفر و B تا یک دارید. هدف بازی این است که تمام این اعداد به یک تبدیل شوند. در هر حرکت، باید دقیقا K تا از این اعداد را انتخاب کنید و مقادیر آن ها را معکوس کنید (یعنی 1 را به 0 و 0 را به 1 تبدیل کنید). در هر مرحله می توانید هر K عددی را، صرف نظر از مقدار فعلی آن ها و اینکه آیا قبلا آن را معکوس کرده ایم، انتخاب کنید. کمترین تعداد حرکت برای بردن بازی را برگردانید، و در صورتیکه نتوان بازی را برد، مقدار 1- برگردانید.

تعریف تابع و کلاس

class BinaryFlips {
public:
   int minimalMoves(int A, int B, int k);
};

محدودیت ها

A و B بین 0 تا 100000 هستند.
K بین 1 تا 100000 است.

توضیح راه حل

فرض کنید تعداد صفرهای فعلی برابر با z باشد. کمترین تعداد صفری که می توانیم در یک حرکت از این حالت بدست بیاوریم، برابر است با |z-k| (یعنی هنگامی که تمامی صفرها را به یک تبدیل کرده ایم، و در صورتیکه تعداد صفرها از k کمتر بود، بقیه تبدیل ها را بر روی یک ها انجام داده ایم):

int min_zero = z - k;
if( min_zero < 0 ) min_zero = - min_zero;

و بیشترین تعداد صفری که می توانیم به دست بیاوریم (با روش مشابه با آنچه در بالا ذکر شد)، عبارت است از:

int max_zero = z + k;
if( max_zero > n ) max_zero = 2 * n - max_zero;

و به آسانی می توان فهمید که تعداد صفرهایی که در یک مرحله از حالت با تعداد صفرهای z بدست آورد، عبارت است از [minzero, minzero + 2, minzero + 4, ..., maxzero] .

برای بدست آوردن طول کوتاهترین مسیر بین حالت اولیه و حالتی که در آن تعداد صفر ها برابر با 0 است، می توان از الگوریتم BFS استفاده کرد، که در آن هر حالت با تعداد صفرهای آن مشخص می شود. ولی اگر بدون هیچ تغییر از آن استفاده کنیم، پیچیدگی زمانی آن از مرتبه O(n^2) خواهد بود که نامطلوب است.

برای بهتر کردن پیچیدگی زمانی الگوريتم، می توان از ساختار داده ی set استفاده کرد:

set<int> st[2];

که [st[0 حالت هایی را نگه می دارد تعداد صفرهای آن زوج است و هنوز به آن حالت مسیری پیدا نشده است، و به همین ترتیب [st[1 حالت هایی با تعداد صفرهای فرد را نگه می دارد که هنوز مسیری به آن پیدا نشده است. مقدار دهی اولیه این آرایه به شکل زیر است:

int n = A + B;
for( int i = 0; i <= n; i ++ ) st[i%2].insert( i );

حال برای پیدا کردن حالت هایی که از حالت با تعداد صفر z که کمترین تعداد صفرهای قابل دسترسی در یک حرکت min_zero و بیشترین تعداد صفر برابر با max_zero است، و قبلا به آن حالت نرسیده ایم، می توان از تابع lower_bound استفاده کرد:

set<int>::iterator it;
while( (it = st[min_zero%2].lower_bound( min_zero )) != st[min_zero%2].end() && *it <= max_zero ) {
	q.push( *it );
	qd.push( d + 1 );
	st[min_zero%2].erase( *it );
}

از آنجایی که هر عنصر حداکثر یکبار به صف افزوده می شود، و پیدا کردن هر عنصر نیاز به زمان O(log n) دارد، و هیچ عنصری دوبار ملاقات نمی کنیم، زمان این الگوریتم از مرتبه O(n log n) خواهد بود.

کد حل مساله

class BinaryFlips {
public:
   int minimalMoves(int A, int B, int k) {
      int n = A + B;
      set<int> st[2];
      for( int i = 0; i <= n; i ++ ) st[i%2].insert( i );
      queue<int> q, qd; 
      q.push( A ); qd.push( 0 ); st[A%2].erase( A );
      while( !q.empty() ) {
         int z = q.front(); q.pop();
         int d = qd.front(); qd.pop();
         if( z == 0 ) return d;
         int min_zero = z - k;
         if( min_zero < 0 ) min_zero = - min_zero;
         int max_zero = z + k;
         if( max_zero > n ) max_zero = 2 * n - max_zero;
         set<int>::iterator it;
         while( (it = st[min_zero%2].lower_bound( min_zero )) != st[min_zero%2].end() && *it <= max_zero ) {
            q.push( *it );
            qd.push( d + 1 );
            st[min_zero%2].erase( *it );
         }
      }
      return -1;
   }
};

سوال سخت - ShuffledPlaylist

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

صورت مساله

من عاشق موسیقی هستم و همواره به موسیقی گوش می دهم. من دارای تعداد زیادی ترانه هستم، معمولا آسان تر است که به ترتیبی درهم از آن ها گوش دهم تا این که هر دفعه ترانه ای را انتخاب کنم. ولی من به سبک های مختلف موسیقی گوش می دهم و برخی از آن ها ناسازگار هستند. بنابراین برنامه ای نوشتم که ترتیب درهم را طبق تعدادی قوانین انتخاب می کند.

اگر بخواهم دقیق تر بگویم، تعدادی سبک تعریف کرده ام و هر کدام از آهنگ ها به سبک خاصی تعلق دارند. همچنین سبک های سازگار را مشخص کرده ام، یعنی اینکه آیا می توان به سبک خاصی بلافاصله پس از سبک خاص دیگری گوش داد یا نه را مشخص کرده ام. اگر کاراکتر j سطر i آرایه transitions برابر با Y باشد، در این صورت ترانه ای از سبک j می تواند پس از ترانه ای از سبک i بیابد. برنامه من به این صورت کار می کند: بصورت تصادفی اولین ترانه را انتخاب می کند. هنگامی که ترانه پایان می یابد، ترانه بعدی را از بین ترانه هایی با سبک های سازگار انتخاب می کند، و به همین ترتیب کار را ادامه می دهد. یک ترانه ممکن است چندین بار اجرا شود، و حتی ممکن است ترانه ای چندین بار پشت سرهم اجرا شود.

شما آرایه songs را به عنوان ورودی دریافت می کنید، که باید عناصر آن را به هم متصل کنید تا رشته ای بزرگ بدست بیاورید که لیست ترانه هاست. این لیست لیستی جدا شده با کاما از جفت عددهای جدا شده با کاراکتر فاصله است، که عدد اول هر جفت سبک آن ترانه را مشخص می کند، و عدد دوم طول آن را به دقیقه مشخص می کند. شما باید تعداد دنباله هایی که برنامه من ممکن است اجرا کند و طول آن به دقیقی بین minLength تا maxLength است را پیدا کنید و باقیمانده آن بر 600921647 را برگردانید.

تعریف تابع و کلاس

class ShuffledPlaylist {
public:
   int count(vector <string> songs, vector <string> transitions, int minLength, int maxLength);
};

محدودیت ها

transitions دارای دقیقا n عنصر خواهد بود که n بین 1 تا 9 است.
هر کدام از عناصر transitions دارای دقیقا n کاراکتر خواهد بود.
کاراکترهای transitions یا Y خواهند بود یا N.
به ازای i بین 0 تا 1-n، کاراکتر i سطر i جدول transitions برابر با Y خواهد بود.
songs دارای 1 تا 50 عنصر خواهد بود.
هر عنصری از songs دارای طول 1 تا 50 خواهد بود.
الحاق عناصر songs لیستی با کام جدا شده از جفت عددهای صحیح جدا شده با فاصله خواهد بود.
عدد اول هر جفت بین 0 تا 1-n خواهد بود.
عدد دوم هر جفت بین 1 تا 9 خواهد بود.
minLength بین 1 تا 1,000,000,000 خواهد بود.
maxLength بین minLength تا 1,000,000,000 خواهد بود.

توضیح راه حل

گرافی را به صورت زیر می سازیم.

رئوس گراف عبارتند از:

راس مبدا: source
راس مقصد: target
راس هایی که با جفت مشخص می شوند، بطوریکه هر یال خارج شوند از نشانگر اجرا شده دقیقه L به آخر ترانه ای از سبک G است. مثلا یال های خارج شونده از بیانگر اجرای دقیقه آخر ترانه ای از سبک 0. در این جفت ها و است.

یال های این گراف عبارتند از:

به به ازای تمام مقادیر G و مقادیر بزرگتر از 1 برای L.
source به به ازای تمام ترانه ها.
به target به ازای تمامی سبک ها.
به به ازای تمامی سبک های G و ترانه های سازگار با آن سبک.

اگر دقت کنید، متوجه خواهید شد که هر ترتیب برای اجرای ترانه ها را می توان به صورت مسیری در این گراف از source به target مشخص کرد، که طول مسیر برابر با مدت زمانی است که این ترتیب اجرا طول می کشد. بنابراین، برای بدست آوردن تعداد ترتیب های اجرای با زمان دقیقا L+1، باید تعداد مسیرهایی را در این گراف از مبدا به مقصد پیدا کنیم که طولشان برابر با L است.

می توان نشان داد که اگر mat ماتریس مجاورت گراف باشد و mat^k توان k ام این ماتریس، آنگاه mat^k[i][j] برابر با تعداد مسیرهای به طول k از i به j است.

حال با استفاده از این روش، می توان تعداد مسیرهای به طول دقیقا L را از مبدا به مقصد پیدا کنیم. برای اینکه بتوانیم تعداد مسیرهای به طول حداکثر L را پیدا کنیم، یالی به طول 1 از مقصد به مقصد متصل می کنیم.

بنابراین جواب مساله برابر خواهد بود با تعداد مسیرهای از مبدا تا مقصد به طول maxLength+1 منهای تعداد مسیرهای از مبدا تا مقصد به طول minLength.

کد حل مساله

const int X = 600921647;
const int SIZE = 92;
 
class ShuffledPlaylist {
public:
   vector<int> genre, length;
   int mat[SIZE][SIZE];
 
   int node( int G, int L ) {
      return G * 10 + L;
   }
 
   int source( ) { return 90; }
   int target( ) { return 91; }
 
   void extractSongs( vector<string> songs ) {
      string s;
      for( int i = 0; i < songs.size(); i ++ )
         s += songs[i];
      for( int i = 0; i < s.length(); i ++ )
         if( s[i] == ',' )
            s[i] = ' ';
      genre.clear(), length.clear();
      int G, L;
      istringstream hin( s );
      while( hin >> G >> L ) {
         genre.push_back( G ), length.push_back( L );
      }
   }
 
   void buildMatrix( vector<string> v ) {
      memset(mat, 0, sizeof mat);
      for( int G = 0; G < 9; G ++ )
         for( int L = 2; L <= 9; L ++ )
            mat[node(G, L)][node(G, L-1)] += 1;
      for( int i = 0; i < genre.size(); i ++ )
         mat[source()][node(genre[i], length[i])] += 1;
      for( int G = 0; G < v.size(); G ++ )
         for( int i = 0; i < genre.size(); i ++ )
            if( v[G][genre[i]] == 'Y' )
               mat[node(G, 1)][node(genre[i], length[i])] += 1;
      for( int G = 0; G < 9; G ++ )
         mat[node(G, 1)][target()] += 1;
      mat[target()][target()] = 1;
   }
 
   int mul_result[SIZE][SIZE];
   void multiply( int a[SIZE][SIZE], int b[SIZE][SIZE] ) {
      memset(mul_result, 0, sizeof result);
      for( int i = 0; i < SIZE; i ++ )
         for( int j = 0; j < SIZE; j ++ )
            for( int k = 0; k < SIZE; k ++ ) {
               long long t = (long long)a[i][k] * b[k][j];
               if( t >= X ) t %= X;
               mul_result[i][j] += t;
               if( mul_result[i][j] >= X ) mul_result[i][j] -= X;
            }
      memcpy(a, mul_result, sizeof mul_result);
   }
 
   int result[SIZE][SIZE], tmat[SIZE][SIZE];
   int solve( int L ) {
      memset( result, 0, sizeof result );
      memcpy( tmat, mat, sizeof tmat );
      for( int i = 0; i < SIZE; i ++ )
         result[i][i] = 1;
      while( L ) {
         if( L % 2 )
            multiply( result, tmat );
         multiply( tmat, tmat );
         L /= 2;
      }
      return result[source()][target()];
   }
 
   int count(vector <string> songs, vector <string> transitions, int minLength, int maxLength) {
      extractSongs( songs );
      buildMatrix( transitions );
      return (solve( maxLength + 1 ) - solve( minLength ) + X ) % X;
   }
};