Problema A

O problema consiste em, dado um vetor ordenado, encontrar o número de ocorrências do elemento que ocorre mais vezes no vetor.

Há várias maneiras de se resolver este problema. Uma delas é varrer a entrada mantendo o maior número de ocorrências (R) e o número de ocorrências do elemento atual (N). N deve ser incrementado em 1 sempre que o valor atual é idêntico ao anterior, e N deve receber o valor 1 sempre que o valor atual é diferente do anterior. R deve ser atualizado com o valor de N sempre que N > R.

Ao fim do algoritmo, basta imprimir R. Esta solução tem complexidade O(n).

Problema B

O problema consiste em, dada uma string de dígitos s, encontrar o menor número lucky que ocorre o maior número de vezes como substring de s.

Note que a reposta sempre consiste em um número de apenas um dígito. Suponha que um número de 2 ou mais dígitos (por exemplo, 47) ocorre o maior número de vezes em s. Como 4 e 7 são substrings de 47, 4 e 7 ocorrem, no mínimo ou mais, a quantidade de ocorrências de 47. Além disso, 4 e 7 são menores que 47. Assim, sempre é possível encontrar um número de apenas um digito que ocorre o maior número de vezes em s.

Logo, basta imprimir 7 se o número 7 ocorre mais vezes que o número 4, 4 caso contrário e -1 caso não há nenhum 4 ou 7 na string.

O número de ocorrências de 4 e 7 na string pode ser encontrado em O(n), sendo n o tamanho da string s.

Problema C

O problema consiste em encontrar o menor número de operações de shift necessárias para que alguma coluna da matriz não contenha zeros.

Para se calcular a resposta, pode-se encontrar o custo da realização da tarefa em cada uma das M colunas, e imprimir o menor deles.

Para cada coluna, o custo é dado pela soma das distâncias do elemento 1 mais próximo da posição desejada, em cada uma das N linhas.

Se uma busca linear for utilizada para o cálculo destas distâncias, a resposta será calculada em O(N*M²) e a solução estourará o tempo limite.

Entretanto, pode-se gerar, para cada linha, um vetor ordenado com as posições de todos os 1 dela, além de duas posições falsas extras, para facilitar o tratamento de casos especiais. A primeira posição falsa é dada por 0 - M + L, onde L é a posição do último 1 da linha. A segunda é dada por M + P, onde P é posição do primeiro 1 do vetor.

Com este vetor, é possível fazer uma busca binária pelo primeiro elemento estritamente maior que a posição desejada. Desta forma, a distância do 1 mais próximo é dada pelo mínimo entre a distância do valor encontrado e a do valor anterior ao encontrado no vetor.

Assim a complexidade total do algoritmo é O(N*M*logM), rápida o bastante.

Deve-se apenas tratar o caso especial que ocorre quando uma das linhas contém apenas zeros. Neste caso, a resposta é -1.

Problema D

O problema consiste em calcular a soma dos números das faces do cubo que podem ser enxergados a partir de um dado ponto. Este problema pode ser resolvido verificando-se, para cada um das 6 faces, se seu número pode ser enxergado. Se puder, o número é somado na resposta.

Considere o número a1, escrito na face do "chão" do cubo (plano ZOX). Esta face pode ser visualizada por qualquer ponto no espaço abaixo do cubo, isto é, por qualquer ponto em que y < 0. De forma análoga, o número a2, escrito na face do "teto" do cubo, pode ser visto de qualquer ponto em que y > y1.

Desta forma, basta verificar se y < 0, y > y1, x < 0, x > x1, z < 0 e z > z1 e somar os números em que tal verificação é verdadeira. Essa solução tem complexidade constante, O(1).

Problema E

O problema consiste em calcular o maior comprimento possível obtido da concatenação das aranhas dadas.

Para atingir o maior comprimento o possível, pode-se gulosamente colocar as aranhas em sequência, presas pelas miçangas mais distantes de cada brinquedo.

Cada aranha é um grafo conexo de k_i vértices e k_i - 1 arestas. Logo, cada aranha é uma árvore. O problema pode então ser enunciado de outra forma:

Dadas N árvores, qual a soma dos tamanhos dos maiores caminhos de cada uma?

O comprimento do maior caminho (diâmetro) em uma árvore pode ser calculado em tempo linear com o seguinte algoritmo:

1. Enraizar um vértice V qualquer;
2. Medir a distância de V para todos os outros vértices, com uma busca em largura ou profundidade;
3. Encontrar o vértice M cuja distância de V é máxima;
4. Enraizar M;
5. Medir a distância de M para todos os outros vértices;
6. Encontrar o vértice U cuja distância de M é máxima.

A distância de M a U é o valor desejado, para cada árvore. Executando-se este algoritmo para cada aranha e somando-se seus resultados, obtemos o número que deve ser impresso em tempo O(N*K).

Problema F

Este problema consiste em, dado um número natural n, verificar se n pode ser escrito como a soma de dois números pares positivos.

Como a soma de dois números pares é par, n deve ser par para poder ser escrito na forma pedida. Assim, se n é impar, imprime-se "NO".

Considere agora que n é par. n pode ser escrito, por exemplo, na forma n = 2 + (n-2), válida quando (n-2) é positivo. (n-2) não é positivo apenas quando n-2=0, isto é, quando n=2.

Dessa forma, 2 é o único numero par que não pode ser escrito na forma pedida. Logo, basta imprimir "NO" se n=2, e "YES" em todos os demais casos em que n é par.

Essa solução tem complexidade O(1).