لأنه في هذا النموذج ، قاتل المشاركون في المؤتمر معهم ولأن اللغة الإنجليزية هي اللغة الرسمية لهيدرا. المهام تبدو مثل هذا:

تبدأ الساعة 5:53 ، فقط 4 دقائق:

وهنا كيف أن هؤلاء الرجال الذين لديهم لوحة فليب شورت قرارهم:

على السطح ، يوجد مثل هذا الحل: جمع أوزان جميع النسخ المتماثلة ، وإنشاء رقم عشوائي من 0 إلى مجموع جميع الأوزان ، ثم اختيار نسخة متماثلة بحيث يكون مجموع أوزان النسخة المتماثلة من 0 إلى (i-1) th أقل من الرقم العشوائي ، ومجموع أوزان النسخ المتماثلة من 0 إلى ال - أكثر من ذلك. سوف يتحول إلى اختيار نسخة متماثلة واحدة ، ولتحديد النسخة التالية ، ستحتاج إلى تكرار الإجراء بأكمله دون مراعاة النسخة المتماثلة المحددة. باستخدام مثل هذه الخوارزمية ، يكون تعقيد اختيار نسخة متماثلة واحدة هو O (N) ، وتعقيد اختيار النسخ المتماثلة K هو O (N · K) ~ O (N ² ).

التعقيد التربيعي سيء ، لكن يمكن تحسينه. للقيام بذلك ، قم ببناء شجرة شرائح لمجموع الأوزان. سيؤدي ذلك إلى إنتاج شجرة بعمق من السجل N ، في أوراقها ستكون هناك أوزان متماثلة ، وفي العقد المتبقية ، مبالغ جزئية ، تصل إلى مجموع جميع الأوزان في جذر الشجرة. بعد ذلك ، نقوم بإنشاء رقم عشوائي من 0 إلى مجموع جميع الأوزان ، والعثور على النسخة المتماثلة ith ، وحذفها من الشجرة ، وكرر الإجراء للبحث عن النسخ المتماثلة المتبقية. باستخدام مثل هذه الخوارزمية ، يكون تعقيد إنشاء شجرة هو O (N) ، وتعقيد العثور على النسخة المتماثلة ith وإزالتها من الشجرة هو O (log N) ، وتعقيد اختيار النسخ المتماثلة K هو O (N + K log N) ~ O (N log N) .

التعقيد الخطي اللوغاريتمي أجمل من التعقيد التربيعي ، خاصة بالنسبة للـ K.

يتم تطبيق هذه الخوارزمية في رمز مكتبة ClusterClient من مشروع Vostok .

ابدأ في 34:50 ، 6 دقائق فقط:

الحل موجود على السطح: فرز جميع المستندات (على سبيل المثال ، استخدام فرز سريع ) ، ثم أخذ مستندات N + S. في هذه الحالة ، يكون تعقيد الفرز في المتوسط ​​هو O (M lg M) ، في أسوأ الأحوال - O (M ² ).

من الواضح أن فرز جميع مستندات M حتى تأخذ جزءًا صغيرًا منها غير فعال. حتى لا يتم فرز جميع المستندات ، تكون خوارزمية quickselect مناسبة ، والتي تحدد N + S من المستندات الضرورية (يمكن فرزها حسب أي خوارزمية). في هذه الحالة ، ينخفض ​​التعقيد في المتوسط ​​إلى O (M) ، وتظل الحالة الأسوأ كما هي.

ومع ذلك ، يمكنك القيام بذلك بشكل أكثر كفاءة - استخدم خوارزمية دفق كومة الذاكرة المؤقتة الثنائية . في هذه الحالة ، تتم إضافة مستندات N + S الأولى إلى الحد الأدنى أو الحد الأقصى للكتف (اعتمادًا على اتجاه الفرز) ، ثم تتم مقارنة كل مستند لاحق بجذر الشجرة ، والذي يحتوي على الحد الأدنى أو الأقصى للمستند في الوقت الحالي ، وتتم إضافته إلى الشجرة إذا لزم الأمر . في هذه الحالة ، يكون التعقيد في أسوأ الحالات هو عندما تضطر إلى إعادة إنشاء الشجرة باستمرار - O (M lg (N + S)) ، ومتوسط ​​التعقيد هو O (M) ، كما هو الحال مع تحديد سريع.

ومع ذلك ، فإن دفق الكومة أكثر فعالية نظرًا لحقيقة أنه يمكن في الواقع التخلص من معظم المستندات دون إعادة بناء الكومة ، بعد مقارنة واحدة مع عنصر الجذر الخاص بها. يتم تنفيذ هذا الفرز في قاعدة بيانات وثيقة Zebra بالذاكرة المطورة والمستخدمة في الدائرة.

حل على السطح: تبادل حالات العنصر الأول والثاني ، ثم الأول والثالث ، ثم الأول والرابع ، وهلم جرا. بعد كل عملية تبادل ، ستكون حالة عنصر واحد في الموضع المطلوب. ما عليك القيام به التباديل O (N) وقضاء O (N · M) الوقت.

الوقت الخطي هو وقت طويل ، لذلك يمكنك تبادل حالات العناصر في أزواج: الأولى مع الثانية ، والثالثة مع الرابعة ، وهلم جرا. بعد كل عملية تبادل ، ستكون حالة كل عنصر ثانٍ في الموضع المطلوب. سيتعين علينا القيام بالتمرير O (log N) وقضاء O (M log N N) الوقت.

ومع ذلك ، يمكنك جعل التحول أكثر فعالية - ليس في الخطي ، ولكن في وقت ثابت. للقيام بذلك ، في الخطوة الأولى ، تحتاج إلى تبادل حالة العنصر الأول مع الأخير ، والثاني مع ما قبل الأخير ، وهكذا. ستكون حالة العنصر الأخير في الموضع المطلوب. والآن أنت بحاجة إلى تبادل حالة العنصر الثاني مع العنصر الأخير والثالث قبل الأخير وما إلى ذلك. بعد هذه الجولة من التبادلات ، ستكون حالات جميع العناصر في المكان المناسب. في المجموع ، سيتم تنفيذ التباديل O (2M) ~ O (1).

مثل هذا الحل لن يفاجئ عالم الرياضيات الذي ما زال يتذكر أن الدوران عبارة عن تركيبة من تماثلين محوريين. بالمناسبة ، يتم تعميمها بشكل تافه على التحول ليس من جانب واحد ، ولكن من خلال المواقف K <N. (اكتب التعليقات بالضبط كيف.)