8o Contest Noturno – Editorial

Entre os dias 6 e 7 de junho aconteceu a oitava edição do Contest Noturno, organizada pelo maratonista Bruno Ribas, com exercícios inéditos escritos pelo Bruno, Ricardo Oliveira, Mateus Dantas e eu.

Pra quem ainda não tem, aqui está o link da prova – [link].
Os exercícios desta e das competições anteriores estão disponíveis nesta página do spoj – [link].

Abaixo segue um editorial escrito por mim. Clique no link abaixo para vê-lo.

A – Gravando CDs[spoj]

Para minimizarmos o tempo que todos os N cd’s serão gravados precisamos dar o primeiro cd para aquele com o maior estoque. Assim, nos próximos Si tempos uma nova cópia estará disponível, e estas por sua vez daremos aos que ainda não tem cópia e que tem o maior estoque, e assim por diante.

Quanto maior o estoque das primeiras pessoas que recebem o cd for, maior será o número de pessoas gravando o cd paralelamente, diminuindo então o tempo necessário para que todos recebam uma cópia.

O terceiro exemplo deixa isso bem claro:

4
0 2 1 2

Se seguíssemos a ordem [1, 2, 2, 0], a resposta seria 4, porém se seguirmos a ordem [2, 2, 1, 0], a resposta seria 3.

É importante notar que a pessoa que não tem estoque deve ficar preferivelmente por último. Note também que as vezes não há estoque o suficiente para todas as pessoas, onde a resposta é -1.

[cristhian], [ricardo]

B – Processamento de Imagem[spoj]

Com a palavra, Mateus -> [link]

 C – Número Proibido[spoj]

Temos um conjunto S de números, e desejamos saber se um determinado elemento está lá ou não. Há algumas formas de se resolver esse problema.

A mais simples, ao meu ver, é ordenar os números (visto que a ordem não importa, apenas a presença ou não de cada número), e em seguida aplicar uma busca binária para buscar cada elemento.

[cristhian], [bruno]

D – Sanidade[spoj]

Pra relembrar as aulas de Estrutura de Dados, esse exercício traz uma tarefa bem interessante: verificar se a lista está encadeada como devia.

Parece uma tarefa trabalhosa, mas existe uma maneira bem inteligente de se verificar essa propriedade:
Imagine um nó arbitrário da lista, P. Seja P->prox o nó à direita de P, e P->ant o nó à esquerda de P.
Para descobrirmos se P está corretamente encadeado com seu nó vizinho, basta verificarmos se P->prox->ant == P.

Se isso for verdade, significa que o nó P aponta para um vizinho, e esse vizinho aponta para P, tornando a lista sana.
Repetimos esse processo, iniciando em P, até chegarmos ao nó objetivo Q, e descobriremos se a lista é sana ou não.

[bruno]

E – Soma simples[spoj]

O exercício da soma e de verificação de paridade são clássicos de competição de programação. Temos aqui uma pequena variação.
De cara notamos que o valor a ser lido é muito maior do que as nossas humildes variáveis suportam (me refiro à linguagem C/C++ e afins).

O truque está em perceber duas coisas:
1. É fácil prever a paridade de uma soma se soubermos a paridade de cada número a ser somado. Por exemplo, a soma de par com par é par; a soma de par com ímpar é ímpar; e a soma de ímpar com ímpar é par.
2. O único digito que importa para descobrirmos a paridade de um número é o último.

Logo, uma solução seria lermos o valor, não como inteiro, mas sim como uma string, checarmos a paridade do último digito, e então descobrirmos a resposta.

[cristhian]

 F – Torcidas de Satebol[spoj]

Se colocarmos no papel uma torcida que atende as propriedades dadas no problema, poderemos notar que estamos lidando com conjuntos de grafos completos, isto é, um conjunto de vértices, onde todos os vértices tem uma aresta com todos os outros vértices.

Isso levanta uma maneira bem criativa de se resolver o problema: começamos com um vértice qualquer, e começamos a contar quantos vértices são alcançáveis por ele, e quantas arestas saem de cada vértice alcançado por ele, incluindo ele mesmo.

Ao final, se este for um grafo completo (uma torcida válida), teremos a seguinte propriedade: cont_arestas = cont_vert*(cont_vert-1). Esta é uma propriedade bem famosa da teoria de grafos, que descreve a relação entre vértices-arestas de um grafo completo.

Há também outras maneiras de se resolver, mas esta foi a solução do Ricardo, que eu achei bem interessante:

[ricardo], [cristhian]

G – Último a Saber[spoj]

Para espalhar a notícia no ritmo descrito no enunciado, o conceito de busca em largura em grafos cai muito bem.

Basta adicionarmos as K pessoas numa fila, e marcá-las como visitadas. Retiramos então a primeira pessoa A, e adicionamos ao final da fila todas as pessoas que são amigas de A que ainda não foram visitadas, marcando-as agora como visitadas. Esse processo se repete até que a última pessoa seja removida e todas as suas amigas já tenham sido visitadas.

Junto com o processo de remover/adicionar à fila, adicionamos um valor t para cada pessoa, denotando o tempo em que tal pessoa foi adicionada à fila pela primeira vez.
Por exemplo, as K primeiras pessoas teriam seus valores t igual a 1, pois foram adicionadas no tempo 1. Todas as pessoas amigas de ao menos uma das K pessoas que ainda não foram adicionadas vão receber um valor t igual 2, e assim por diante.

Ao final, imprimimos todas as pessoas que tiverem o maior tempo t.

[cristhian]

H – Onde está Zelda? – [spoj]

Os limites baixos deste exercício permitem que uma solução bem direta seja suficiente.

Basta verificar se o segmento da reta do Link, que é a direção da sua espada, intersecta com ao menos um dos quatro lados de cada retângulo. Se sim, então adicionamos este castelo ao resultado.

Para mais detalhes, pesquisem Intersecção de Segmentos de Reta.

[ricardo]

I – Julgamento por Combate – [spoj]

Temos aqui um problema bem interessante de se resolver com programação dinâmica.

Vamos começar ordenando os guerreiros de acordo com a sua força, do maior para o menor.

Após ter feito isso, seja G um guerreiro arbitrário, para calcularmos o quanto ele vai contribuir para a batalha basta apenas saber ‘quantos’ guerreiros à esquerda dele foram escolhidos (não necessariamente ‘quais’).

A partir daí, basta escolhermos se o adicionamos ou não. Para não utilizar nenhuma estratégia gulosa, vamos testar todas as possibilidades.

Esteja o vetor F e M ordenados de acordo com valor F de cada guerreiro, seja G o indice de um guerreiro qualquer, e seja C o número de guerreiros à esquerda de G escolhidos, temos a seguinte recursão:

f(G, C) = max( 
       f(G+1, C),                // não adicionar o guerreiro G
       f(G+1, C+1)+F[G]+M[G]*C   // adicionar o guerreiro G
)

[cristhian], [ricardo]

 

Espero que tenham gostado, tanto do contest quanto do editorial.
Qualquer dúvida, sugestão ou crítica, usem a caixa de comentários abaixo.

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *