📅 🤾🏼 🌹 الخروج من عجلة سانسارا والتطرف والأشياء الخضراء الصغيرة - تحليل المهام من كتيب GridGain في مؤتمر جوكر 2018 🤾🏿 👛 🆕

عُقد مؤتمر جوكر في 19 و 20 أكتوبر في سانت بطرسبرغ - أفضل حدث لأولئك الذين يحبون نفس الأشياء التي نحبها: التقارير الرائعة ، والتواصل مع خبراء جافا المتقدمين والمهام. لن نثني على الإصدار الثالث من المهام من GridGain ( 1 ، 2 ) ، ونحن نقتبس بشكل أفضل تعليقات المشاركين:

"مهامهم بدت غبية وغير مرتبطة بتكنولوجيا المعلومات"
"مهام ممتازة ، كما هو الحال دائمًا (على الرغم من أنني لم أتقن واحدة)"
"الإدمان في المهام"
"أفضل المهام ، كما هو الحال دائمًا"

ننشر ، كما وعدت ، حلول مفصلة. أخرجوها تحت المفسد حتى يتمكن أولئك الذين فاتهم المؤتمر من تجربة أيديهم.

المهمة 1

قبل ثلاثة أشهر ، كتبنا هذه المهمة ، ولكن في أكتوبر 2018 ، جاء الرئيس بمبادرة لإلغاء تجريم 282 مقالة ، ونحن سعداء للغاية بها ، لكننا كنا قلقين لإعادة صياغة النصوص. لذا دع كل شيء يبقى في هذه المهمة كما كان. *

يراقب المركز على حرف وضع الميمات المسيئة ، وكذلك أمثالهم وإعادة النشر على الشبكات الاجتماعية. كجزء من التحول الرقمي ، تم استبدال مكتب قسم المراقبة بأكمله بالذكاء الاصطناعي. ساعد الابتكار على حساب احتمالية تحول المستخدمين من الإعجابات إلى عمليات إعادة النشر بسرعة من أجل عرض القضية على المحكمة بنجاح. سابقًا ، صدر حكم إدانة من حرف واحد باحتمال 90٪ في 192 يومًا. جلبت أتمتة العملية المؤشرات إلى 12 يومًا باحتمال 99.9٪.

سؤال: كم مرة أدى النهج المبتكر إلى زيادة تحويل المذكرات إلى إدانات بمقدار 282 ، إذا كان لتواتر الجمل توزيع أسي؟

حل المشكلة 1

* بعد تسمية عروض الأسعار والعمل في كشك المؤلف ، يمكنك الحصول على هدية على الفور. طبعا هذا يوري خوي (كلينسكي) و "قطاع الغاز" و مضمار "بلا مأوى"

حسب الحالة الأولية منذ ذلك الحين تواتر الجمل له توزيع أسي ، ثم قبل إدخال الروبوت وبعد أن يكون لدينا العبارات التالية لتقييم احتمالية النطق بالحكم في الوقت المناسب:

$F_1 (t) = 1 - e ^ {- \ lambda_1 * t} \\ F_2 (t) = 1 - e ^ {- \ lambda_2 * t}$

أين

$\ lambda_1 ، \ lambda_2$ - هذه معلمات غير معروفة تحدد تواتر الجمل ، t هي معلمة الوقت ، وفقًا للشرط الذي يتضح أنه:

$F_1 (192) = 0.9 \\ F_2 (12) = 0.999 دولارًا$

من هذه المعادلات يتم التعبير عن المعلمات بسهولة كبيرة

$\ lambda_1 ، \ lambda_2$

$\ lambda_1 = - \ ln (1 - 0.9) / 192 \ sim = 0.012 \\ \ lambda_2 = - \ ln (1 - 0.999) / 12 \ sim = 0.576$

من الافتراض أن عدد الجمل وعدد المذكرات مرتبطان خطياً ، يمكننا أن نستنتج أن النسبة

$\ lambda_1 ، \ lambda_2$ فقط يعطي القيمة المطلوبة:

$\ lambda_2 / \ lambda_1 \ sim = 48$

المهمة 2

من وجهة نظر البوذي فاسيلي ، يعد الرمز مثاليًا ليس عندما لا يوجد شيء يمكن إضافته إليه ، ولكن عندما لا يمكن إزالة أي شيء. بدافع من هذه الفكرة ، قرر Vasily تحسين EpsilonGC وكشف للعالم Dzen-GC - منتج من الفكر المثالي الذي لا يمكن فقط مسح ذاكرة كومة الذاكرة المؤقتة ، ولكن حتى لا يسمح بتخصيصها. من الواضح أن التخصيص في JVM مع هذا GC المبتكر ممكن فقط على المكدس وفقط للأنواع البدائية.

لاختبار الوظيفة الجديدة ، قرر Vasily كتابة دالة في Java تعثر على وضع لـ 6 قيم (الوضع هو القيمة في مجموعة الملاحظات التي تحدث في أغلب الأحيان) ، أي أنه يحتوي على التوقيع التالي:

public static int mode(int n0, int n1, int n2, int n3, int n4, int n5)

للاقتراب من التنوير ، لم يعلن Vasily عن متغيرات وأساليب محلية إضافية في رمزه ، كما تمت برمجته فقط بإصبع قدمه اليسرى الصغيرة.

المهمة: مساعدة فاسيلي في تنفيذ هذه الوظيفة (يُسمح باستخدام جميع الأصابع).

حل المشكلة 2

دعونا نحاول معرفة كيف يمكن حل هذه المشكلة إذا لم تكن هناك مثل هذه القيود الصارمة. فقط قل أن القيم تم نقلها في مصفوفة ، ومن المستحسن عدم استخدام الذاكرة الإضافية (ولكن القليل ممكن).

ثم سنلاحظ الخيارات التي تستخدم Map <Integer، Integer> ، وسنلاحظ أن الوضع هو الأكثر ملاءمة للبحث عنه في مصفوفة مرتبة: إذا تكررت القيمة ، فستكون جميع التكرارات قريبة. نقوم بفرز الصفيف وبمرور واحد (ومتغيرين) نجد القيمة مع الحد الأقصى لعدد التكرار.

لاحظ الآن أن:

1) يمكنك فرز القيم بشكل متكرر.

 // Expectation: if there are more than one mode, we are free to return any of them. // 2,2,3,3,4,4 has 3 modes : 2,3,4. I expect that 3 is correct answer. public static int mode (int a, int b, int c, int d, int e, int f){ // If arguments are not sorted, let's sort them with bubble sort :) if (a > b) return mode(b,a,c,d,e,f); if (b > c) return mode(a,c,b,d,e,f); if (c > d) return mode(a,b,d,c,e,f); if (d > e) return mode(a,b,c,e,d,f); if (e > f) return mode(a,b,c,d,f,e);

2) لدينا 6 قيم فقط.
3) إذا تم تكرار القيمة 3 مرات (نصف جميع القيم) - فهذا بالفعل تعديل!
3.1) إذا لم يكن كذلك ، ولكن هناك تكراران - فهذا هو التعديل!
3.2) إذا لم تكن هناك قيم مكررة ، فإن أي قيمة هي وضع.

 // Check for mode with 3+ repeats. 3 repeats is enough to say value is a mode (3 is half of 6). // Since args are sorted, a == b && b == c is the same as a == c; if (a == c) return a; if (b == d) return b; if (c == e) return c; if (d == f) return d; // Check for 2 repeats. if (a == b) return a; if (b == c) return b; if (c == d) return c; if (d == e) return d; if (e == f) return e; return f; }

بالمعنى الدقيق للكلمة ، يمكن أن يكون للمشكلة العديد من الحلول ، لكننا أحببناها كأبسط الحلول وأكثرها انسجامًا.

المهمة 3

قرر اثنان من مدمني المخدرات الخروج من المصفوفة وفهم أي منهم كان المختار. للقيام بذلك ، حصلوا على عبوة واحدة زرقاء و 4 عبوات حبوب حمراء (عبوات بنفس الحجم) ، ولتحسين التأثير ، قرروا شربها باللون الأخضر.

فجأة ، اتضح أنه بسبب خلل ماتريكس (كما اعتقد مدمني المخدرات) ، فإن وجوههم ، التي كانت تحتوي في البداية على ألوان RGB # 2D241D و # F4E3E1 ، بدأت تتغير اعتمادًا على عدد الأجهزة اللوحية والشاي الأخضر المستخدم: كل قرص (أو 1 مل من الشاي الأخضر) زاد خطياً من كمية المطابقة الألوان على وجه المدمن.

في الوقت نفسه ، لا يمكن أن تتجاوز قيمة كل مكون RGB #FF ، أي أن الاستخدام الإضافي للأجهزة اللوحية أو اللون الأخضر اللامع لن يكون له أي تأثير. كان لدى Zelenka في البداية عدة قوارير كاملة من 20 مل لكل منها ، مرتين في المجموع أقل من العدد الإجمالي للأقراص في القطع. بعد حدث الخروج من المصفوفة ، حيث أكل المدمن الثاني
54 حبة حمراء أكثر من المدمنين الأزرق الأول ، لم يبق لديهم أي شيء.

السؤال: كم عدد الحبوب والعملة الخضراء التي استخدمها كل مدمن ، إذا كانت وجوههم نتيجة لذلك # F0FF6B و #FFFEFF ، على التوالي ، ومن المعروف أن الدولار أقوى 3 مرات من الحبوب الحمراء ، والتي بدورها ، مرتين
أضعف من الأزرق؟

حل المشكلة 3

بادئ ذي بدء ، سنختار من بين القيم النهائية للألوان فقط تلك التي تكون أقل من 0xFF تمامًا ، لأنه ، حسب الشرط ، للقيمة 0xFF يمكننا فقط إعطاء الحد السفلي لمحسن اللون المستخدم. هذه هي القيم 0xF0 و 0x6B و 0xFE. نحصل على المعادلات التالية:

$r_1 * k = (0xF0 - 0x2D) = 195 \\ b_1 * 2k = (0x6B - 0x1D) = 78 \\ g_2 * 3k = (0xFE - 0xE3) = 27 \\$

أو

$r_1 * k = 195 \\ b_1 * k = 39 \\ g_2 * k = 9 \\$

هنا ك هو معامل عمل الحبوب الحمراء ،

$col_i ، col \ in \ {r ، g ، b \} ، i \ in \ {1 ، 2 \}$ - - عدد المكبرات المستخدمة (يتم قياس الأجهزة اللوحية بالقطع ، الأخضر - بالملليترات) من اللون المقابل من قبل المستهلك المقابل. علاوة على ذلك ، نعلم أن الثانية تناولت 54 حبة حمراء أكثر من اللون الأزرق الأول ، كل شيء بسيط:

$r_2 = 54 + b_1$

يتم الحصول على معادلة أخرى من الشرط على النسبة بين عدد الأقراص والمليلتر من اللون الأخضر:

$2 * (g_1 + g_2) = (r_1 + b_1 + r_2 + b_2)$

لدينا أيضًا من النسبة بين الأجهزة اللوحية الحمراء والزرقاء:

$(r_1 + r_2) = 4 (b_1 + b_2)$

بالإضافة إلى ذلك ، نعلم أنه كان هناك عدة مرات 20 مل من العملة الأمريكية:

$(g_1 + g_2) = 20 z$ حيث z عدد صحيح غير سالب.

من افتراض أن k كاملة وأن الحبوب تؤكل كاملة (يمكنك شرب الدولار كما تريد) ، فإن الإجابة الوحيدة التي تتناسب مع ما يلي:

$r_1 = 195 \\ g_1 = 171 \\ b_1 = 39 \\$

$r_2 = 93 \\ g_2 = 9 \\ b_2 = 33 \\$

يمكن الحصول عليه ببساطة شديدة ، على سبيل المثال ، من خلال الطريقة الموضحة أدناه.
لدينا نسبة

$b_1 * k = 39$ . التطلعات الوحيدة لـ 39 هي {1 ، 39} ، {3 ، 13}. وبالتالي ، يمكن أن تأخذ k قيمًا فقط من المجموعة {1 ، 3 ، 13 ، 39}. لنجرب القيمة "3".

$r_1 = 195/3 = 65، \\ b_1 = 39/3 = 13، \\ g_2 = 9/3 = 3، \\ r_2 = 54 + b1 = 54 + 13 = 67، \\ b_2 = ((r1 + r2) - 4 * b1) / 4 = (65 + 67 - 4 * 13) / 4 = 20، \\ g_1 = ((r1 + b1 + r2 + b2) - 2 * g2) / 2 = (65 + 13 + 67 + 20 - 2 * 3) / 2 = 79 / 2.$

لكن في نفس الوقت

$g_1 + g_2$ يجب أن يكون مضاعفًا لـ 20 ، وهذا ليس صحيحًا للقيمة (79.5 + 3).

بنفس الطريقة تمامًا يتم حذف القيم "13" و "39". القيمة الوحيدة المتبقية لـ k هي واحدة. وبدلاً من ذلك ، لا نأتي إلى تناقضات ونحصل على إجابة.

في الواقع ، نظرًا لأنه لا يوجد أي مكان في المشكلة يقال أن معامل الزيادة الخطية k لمكون RGB الأحمر هو عدد صحيح ، فإن الحلول هي عائلة كاملة ، * حتى * إذا افترضنا أن اللون الأخضر يستهلك فقط بمضاعفات 1 مل ، ويتم استهلاك الأجهزة اللوحية بالكامل (والتي أيضًا غير محدد بشكل منفصل):

$r_1 = 1040n + 195 \\ g_1 = 732n + 171 \\ b_1 = 208n + 39 \\$

$r_2 = 208n + 93 \\ g_2 = 48n + 9 \\ b_2 = 104n + 33 \\$
n عدد صحيح غير سالب.

للحصول على هذه العائلة ، تحتاج إلى التخلص من k في المعادلات الثلاثة الأولى عن طريق إعادة كتابتها ، على سبيل المثال ، على النحو التالي:

$3 r_1 - 15 b_1 = 0 ، \\ 3 r_1 - 65 g_2 = 0 ، \\ 15b_1 - 65g_2 = 0 ، \\$

ثم حل نظام معادلات ديوفانتين الخطية (وبطبيعة الحال ، بما في ذلك بقية المعادلات اختزلت إلى الشكل الصحيح). إذا لم نفترض أن اللون الأخضر لا يستهلك إلا بأحجام مضاعفة من المليلتر ، فإننا نحصل على نظام غير خطي من معادلات ديوفانتين ، مع أخذ g1 و g2 (والذي من الواضح أنه يجب أن يكون عقلانيًا) لكل البسط والمقام غير المعروفين. إذا قمنا بحل المشكلة بشكلها الأعم (كل القيم مستمرة) ، فهناك المزيد من الحلول.

الفائزون

صحيح ، تم حل جميع المهام من قبل أليكسي ريجيكوف وفالنتين شيبيلوف. كما تم استلام الجوائز من قبل أليكسي جالكين وأنطون بلينوف وإيليا بريفوزتشيكوف والعديد من المشاركين الآخرين. مبروك!

الخروج من عجلة سانسارا والتطرف والأشياء الخضراء الصغيرة - تحليل المهام من كتيب GridGain في مؤتمر جوكر 2018

المهمة 1

المهمة 2

المهمة 3

الفائزون

More articles: