OBI 2023 - Fase 2 - Programação Nível 2

Se você quiser se preparar para a OBI, não deixe de conferir o Roteiro de estudos de informática, e também a página de informática do NOIC, com todos nossos materiais

Para conferir a prova na integra:

Código de Compressão

Comentário por Murilo Maeda

Para esse problema basta manter em uma variável auxiliar $k$ qual é o número de caracteres na sequência de caracteres iguais atual. Se um caractere é igual ao anterior, fazemos $k++$ . Se um caractere é diferente do anterior, imprimimos $k$ e depois o caractere anterior. Lembre-se de no final do código imprimir $k$ e o último caractere da string.

Clique aqui para conferir o código

Grupos de Trabalho

Comentário por Henrique Vianna

Para resolver esse problema, basta marcarmos em qual grupo cada um dos alunos está e depois passar pelas $M + D$ condições, checando se elas estão satisfeitas. Para cada condição do primeiro tipo, se os dois alunos estiverem em grupos diferentes, aumentamos a resposta em um. Da mesma forma, para cada condição do tipo dois, se os dois alunos estiverem no mesmo grupo, devemos adicionar um à resposta.

Clique aqui para conferir o código

Distintos

Comentário por Murilo Maeda

Conhecimento prévio necessário:

Two pointers

Para esse problema, vamos utilizar a técnica de two pointers. A variável $l$ representa o índice mais à esquerda do segmento atualmente considerado e a variável $r$ representa o índice mais à direita do intervalo atualmente considerado. Como os valores têm um limite, basta manter um vetor que guarda a frequência dos valores para saber se há valores repetidos. Se quando tentamos expandir o segmento para a direita encontrarmos um número que já está no nosso segmento, calculamos o tamanho do segmento atual e checamos se ele é a melhor resposta até agora. Depois disso, movemos o limite esquerdo para a direita até que o valor que tentamos adicionar só apareça uma vez. A resposta vai ser o maior tamanho obtido durante todo o processo.

Complexidade: Passamos por cada índice uma vez com cada ponteiro, então a complexidade é $O(N)$

Clique aqui para conferir o código

Barcos da Nlogônia

Comentário por Fernando Gonçalves

Conhecimento prévio necessário:

MST, especificamente a ideia usada no problema Tourist Guide
LCA
Sparse Table

Para maximizar o mínimo peso no caminho entre quaisquer dois vértices, usamos uma maximum spanning tree, pois (como foi provado aqui) a árvore geradora máxima tem essa propriedade.

Agora que temos a MST, podemos fazer todas as operações nessa árvore. Para tanto, usamos uma sparse table: teremos uma $dp_{v,k}$ , que guarda o antecessor de $v$ que está $2^k$ arestas acima, e uma $dpMin_{v,k}$ , que guarda o mínimo dos pesos no caminho até $dp_{v,k}$ . Mantendo essas duas estruturas, conseguimos usar o algoritmo de achar lca para calcular o mínimo peso no caminho entre os pares de vértices dados em complexidade de $O(logN)$ .

No total, teremos complexidade: $O(B*logB)$ para achar a MST, $O(N*logN)$ para construir a sparse table e $O(C*logN)$ para responder às consultas.

Clique aqui para conferir o código