🤾 🧑🏿‍🤝‍🧑🏾 ⛹🏻 Algorithmen für die Prüfung im SHAD ㊗️ 🕺🏼 🔳

Hallo! Mein Name ist Alexander Kurilkin und ich unterrichte einen Kurs über Algorithmen bei ShAD Helper. In diesem Beitrag werde ich einige Aufgaben aus den Aufnahmeprüfungen der letzten Jahre analysieren, damit Sie sehen können, was Sie erwartet, und verstehen, was wir Ihnen in unserem Kurs beibringen können. Ich hoffe, dass Sie meine Liebe zu interessanten Aufgaben zu Algorithmen teilen und sich aufrichtig über das Lesen dieses Beitrags freuen werden! Also lasst uns anfangen ...

28.05.2016, Nr. 4

Sind gegeben $n$ Segmente $[a_i; b_i]$ . Wir nennen den Segmentverschachtelungsindex $[a_i; b_i]$ die Anzahl der Segmente, die es enthalten. Schlagen Sie einen Algorithmus vor, der bestimmt, ob sich ein Segment in der Gruppe befindet, dessen Verschachtelungsindex 1000 überschreitet. Das Zeitlimit beträgt $O(n \log n)$ , für zusätzlichen Speicher - $O(n)$ .

Entscheidung

, "". , - , , - , . " ", $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)$ .

25.05.2019, Nr. 4

Ein Array von reellen Zahlen wird angegeben $A$ . Schlagen Sie einen Algorithmus vor, der für jedes Element findet $A$ Index des Elements am nächsten rechts, mindestens doppelt so groß. Wenn es kein solches Element gibt, sollte der Wert zurückgegeben werden. $None$ . Zeitlimit $O(n \log n)$ , für zusätzlichen Speicher - $O(n)$ .

Entscheidung

$(, )$ . ( $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, Nr. 5
Im Set von $n$ Jede Person kann die andere kennen oder nicht (wenn $A$ weiß $B$ Daraus folgt nicht $B$ weiß $A$ ) Alle Bekanntschaften werden durch eine Boolesche Matrix gegeben $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$ Zahlen, die durch Leerzeichen oder Zeilenumbrüche getrennt sind - das Gewicht des minimalen Spannbaums nach jeder Anforderung.

Entscheidung

, , 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 :)

Algorithmen für die Prüfung im SHAD

More articles: