👩🏾‍🤝‍👩🏽 👩‍👩‍👦 🐏 Algorithmes pour l'examen dans le SHAD 👩🏿‍🚀 🏦 🐯

salut! Je m'appelle Alexander Kurilkin et j'enseigne un cours d'algorithmes à ShAD Helper. Dans cet article, j'analyserai plusieurs tâches des examens d'entrée des dernières années, afin que vous puissiez voir ce qui vous attend et comprendre ce que nous pouvons vous enseigner dans notre cours. J'espère que vous partagerez mon amour pour les tâches intéressantes sur les algorithmes et que je recevrai un plaisir sincère à lire cet article! Alors, commençons ...

28/05/2016, n ° 4

Sont donnés $n$ segments $[a_i; b_i]$ . Nous appelons l'indice d'imbrication des segments $[a_i; b_i]$ le nombre de segments qui le contiennent. Suggérer un algorithme qui détermine s'il existe un segment dans l'ensemble avec un indice d'imbrication supérieur à 1000. La limite de temps est $O(n \log n)$ , pour plus de mémoire - $O(n)$ .

Décision

, "". , - , , - , . " ", $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, n ° 4

Un tableau de nombres réels est donné $A$ . Suggérer un algorithme qui trouve pour chaque élément $A$ indice de l'élément le plus proche à droite, au moins deux fois sa taille. S'il n'y a pas un tel élément, alors la valeur doit être retournée. $None$ . Limite de temps $O(n \log n)$ , pour plus de mémoire - $O(n)$ .

Décision

$(, )$ . ( $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, n ° 5
Dans l'ensemble des $n$ chaque personne peut ou non connaître l'autre (si $A$ sait $B$ , il ne s'ensuit pas que $B$ sait $A$ ) Toutes les connaissances sont données par une matrice booléenne $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$ nombres séparés par des espaces ou des sauts de ligne - le poids de l'arbre couvrant minimum après chaque demande.

Décision

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

Algorithmes pour l'examen dans le SHAD

More articles: