👐 🌗 🏬 Algoritmos para el examen en el SHAD 🎌 🚙 😧

¡Hola! Mi nombre es Alexander Kurilkin, y estoy impartiendo un curso sobre algoritmos en ShAD Helper. En esta publicación analizaré varias tareas de los exámenes de ingreso de años anteriores, para que pueda ver lo que le espera y comprender lo que podemos enseñarle en nuestro curso. ¡Espero que compartas mi amor por las tareas interesantes sobre algoritmos y que recibas un sincero placer al leer esta publicación! Entonces empecemos ...

28/05/2016, N ° 4

Son dados $n$ segmentos $[a_i; b_i]$ . Llamamos al índice de anidación de segmento $[a_i; b_i]$ El número de segmentos que lo contienen. Sugiera un algoritmo que determine si hay un segmento en el conjunto con un índice de anidación superior a 1000. El límite de tiempo es $O(n \log n)$ , para memoria adicional - $O(n)$ .

Decisió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)$ .

25/05/2019, No.4

Se da una serie de números reales $A$ . Sugerir un algoritmo que encuentre para cada elemento $A$ índice del elemento más cercano a la derecha, al menos el doble de su tamaño. Si no existe tal elemento, entonces se debe devolver el valor. $None$ . Límite de tiempo $O(n \log n)$ , para memoria adicional - $O(n)$ .

Decisión

$(, )$ . ( $None$ ), $(A[n - 1], n - 1)$ vamos a la izquierda Supongamos que queremos procesar el siguiente número con un índice $i$ . , , , ? , . , , , ? . , . , $(A[i], i)$ . , , ? , ( ) $i$ . (, , std::vector) , $A[i] \cdot 2$ . , ( ), , $None$ .

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

06/10/12, No. 5
en el conjunto de $n$ cada persona puede o no conocer a la otra (si $A$ sabe $B$ , no se sigue que $B$ sabe $A$ ) Todos los conocidos están dados por una matriz booleana $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$ números separados por espacios o saltos de línea: el peso del árbol de expansión mínimo después de cada solicitud.

Decisión

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

Algoritmos para el examen en el SHAD

More articles: