👨🏻‍⚕️ 👨‍👩‍👦 🤷🏽 خوارزميات الامتحان في SHAD 📲 ♿️ 🐻

مرحبا! اسمي ألكسندر كوريلكين ، وأنا أقوم بتدريس دورة عن الخوارزميات في ShAD Helper. في هذا المنشور ، سأقوم بتحليل العديد من المهام من امتحانات القبول في السنوات الماضية ، حتى تتمكن من رؤية ما ينتظرك وفهم ما يمكننا تعليمك إياه في دورتنا. آمل أن تشارك حبي لمهام مثيرة للاهتمام على الخوارزميات وستستمتع بسرور صادق من قراءة هذه المشاركة! لذلك دعونا نبدأ ...

05/28/2016 ، رقم 4

أعطي $n$ شرائح $[a_i; b_i]$ . نسمي مؤشر تداخل المقطع $[a_i; b_i]$ عدد الأجزاء التي تحتوي عليها. اقتراح خوارزمية تحدد ما إذا كان هناك مقطع في المجموعة مع مؤشر تداخل يتجاوز 1000. الحد الزمني هو $O(n \log n)$ ، لذاكرة إضافية - $O(n)$ .

القرار

, "". , - , , - , . " ", $a_i$ , " ", $b_i$ . . , 1. , 1000, , — 1000 . — - , , . , (std::multiset C++), . , — 1000 . , , , , *set.begin(), ( 1000 ) . , ! , , . , . , , !

: 1000 ? , - 1000 , 1000 , - , ? , - 1000 , , , , , .

, . $O(n \log n)$ , $O(n \log 1000) = O(n)$ O(n) . , : $O(n \log n)$ . $O(n)$ .

05/25/2019 ، رقم 4

يتم إعطاء مجموعة من الأرقام الحقيقية $A$ . اقترح خوارزمية تجد لكل عنصر $A$ فهرس العنصر الأقرب إلى اليمين ، على الأقل ضعف حجمه. إذا لم يكن هناك مثل هذا العنصر ، فيجب إرجاع القيمة. $None$ . المهلة $O(n \log n)$ ، لذاكرة إضافية - $O(n)$ .

القرار

$(, )$ . ( $None$ ), $(A[n - 1], n - 1)$ , . $i$ . , , , ? , . , , , ? . , . , $(A[i], i)$ . , , ? , ( ) $i$ . (, , std::vector) , $A[i] \cdot 2$ . , ( ), , $None$ .

, , ? , O(n), $n$ , $O(n \log n)$ , . , , , $O(n)$ .

06/10/12 ، رقم 5
في مجموعة $n$ كل شخص قد يعرف أو لا يعرف الآخر (إذا $A$ يعرف $B$ ، لا يتبع ذلك $B$ يعرف $A$ ) يتم إعطاء جميع المعارف من خلال مصفوفة منطقية $n×n$ . — , , . , , . — $O(n)$ , — $O(1)$ .

$K_{ij} = 1$ , $i$ - $j$ - , 0 .

, $K_{ij} = 1 ~ (i \neq j)$ , $i$ - , - , $j$ - , $K_{ij} = 0$ , $j$ - , $i$ - .

: — . , 1, , $l$ . , ( 0), , , , , - ( , , $l$ ). $l$ - — , $(l, l + 1)$ . 1, , , . , . , , , ( ), , , , . , , , $O(n)$ , , $O(n)$ . : $O(n)$ . , , (, ), $O(1)$ . !

, , !

2019, -, D

, 2
: 2
: 256Mb

$n$ $m$ . $q$ « $i$ 1». .

— , . , .

. , , .

$n$ $m$ — ( $1 \le n, m \le 10^5, 2 \le n)$ . $m$ $u$ , $v$ , $w$ . , $w$ , $u$ $v$ ( $1 \le u, v \le n, 1 \le w \le 10$ ).

$q$ — ( $1 \le q \le 10^5$ ). $q$ $id$ ( $1 \le id \le m$ ). , $id$ . .

$q$ أرقام مفصولة بمسافات أو فواصل أسطر - وزن الحد الأدنى للشجرة الممتدة بعد كل طلب.

القرار

, , 99% . .

" $u$ $v$ ", $k$ . $u$ $v$ $k$ ( . $k+1$ , , $u$ $v$ $> k + 1$ , $k + 1$ , , ́ ), , 1. . , , . $O(n)$ , , , $O(\log n)$ link-cut tree, , ( ). .

1 10, 10 ( , ). $k$ - $\le k$ . . : , ( ) , , . , , , , .

$(u, v)$ 1 $k$ . $k$ - . , $k$ - $u$ $v$ . , $k+1$ , , . , $u$ $v$ $k$ - , 1. $u$ $v$ $k$ - , $\le k$ , .

, , ? $O(\alpha(n))$ , $O(10 \cdot m \log n) = O(m \log n)$ . , Accepted :)

خوارزميات الامتحان في SHAD

More articles: