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:
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.