🤢 🙏 🎊 Algoritmos para o exame no SHAD 👭 🛀🏻 👈🏻

Olá! Meu nome é Alexander Kurilkin e estou ministrando um curso sobre algoritmos no ShAD Helper. Neste post, analisarei várias tarefas dos exames de admissão dos últimos anos, para que você possa ver o que o espera e entender o que podemos ensinar em nosso curso. Espero que você compartilhe meu amor por tarefas interessantes sobre algoritmos e tenha prazer sincero ao ler este post! Então vamos começar ...

28/05/2016, nº 4

São dados $n$ segmentos $[a_i; b_i]$ . Chamamos o índice de aninhamento de segmento $[a_i; b_i]$ o número de segmentos que o contêm. Sugira um algoritmo que determine se existe um segmento no conjunto com um índice de aninhamento superior a 1000. O limite de tempo é $O(n \log n)$ , para memória adicional - $O(n)$ .

Decisão

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

Uma matriz de números reais é dada $A$ . Sugira um algoritmo que encontre para cada elemento $A$ índice do elemento mais próximo à direita, pelo menos duas vezes seu tamanho. Se não houver esse elemento, o valor deverá ser retornado. $None$ . Prazo $O(n \log n)$ , para memória adicional - $O(n)$ .

Decisão

$(, )$ . ( $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, No. 5
No conjunto de $n$ cada pessoa pode ou não conhecer a outra (se $A$ sabe $B$ , não segue isso $B$ sabe $A$ ) Todos os conhecidos são dados por uma 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 espaços ou quebras de linha - o peso da árvore de abrangência mínima após cada solicitação.

Decisão

, , 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 o exame no SHAD

More articles: