Neste dia 8 de agosto aconteceu a Seletiva UFPR, organizada pelo maratonista Ricardo Oliveira, com 10 exercícios inéditos escritos pelo Ricardo, Bruno Ribas, Rodolfo Rodovalho, Vinícius Ruoso e eu.

Informações adicionais sobre o contest, incluindo a prova, podem ser acessados aqui:
http://www.inf.ufpr.br/maratona/interna/5a-seletiva-2014/

Os exercícios estão disponíveis para serem resolvidos no SPOJ, na secão “seletiva“.

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

A – Encontro Politécnico – [spoj]

Temos as posições iniciais de ambos os professores, e várias instruções de movimentação. Precisamos descobrir se: (1) eles se encontraram, (2) o professor PA saiu da área, (3) o professor PB saiu da área, ou (4) eles não se encontraram.

Para fazer isso, basta realizar uma simulação de movimentos, e constantemente verificar se algumas das situações acima acontece.

[bruno], [cristhian], [ricardo]

B – Shrek – [spoj]

Há dois tipos de resultado: Ou é possível alcançar o cidadão em algum momento, ou não é. Caso seja possível, esse momento está entre 0 e ST inclusive, onde ST significa a soma do tempo necessário para o cidadão sair do ponto 1 e chegar no ponto N.

O insight mais importante para a resolução do exercício é que os pontos em que Shrek pode alcançar o cidadão seguem uma lógica monotômica, graças ao fato de que Vs >= Vc.

Ou seja, se Shrek pode alcançar o cidadão no ponto J, ele concerteza pode alcançar o cidadão no ponto J+1, pois Shrek anda no mínimo na mesma velocidade que ele, não perdendo a “corrida”.

E se Shrek não pode alçancar o cidadão no ponto J, ele concerteza não pode alcançar o cidadão no ponto J-1, caso contrário nossa afirmação acima nos garantiria que ele conseguiria alcançar o cidadão no ponto J.

Esse insight nos permite utilizar o conceito de busca binária para aproximar o tempo mínimo em que Shrek pode alcançar o cidadão.

Inicialmente é possível montar um vetor acumulativo S, indicando quanto tempo leva pro cidadão sair do ponto 1 e chegar no ponto J. Por exemplo, S[1] = 0, pois ele inicia no ponto 1; S[2] = tempo necessário para se viajar até o ponto 2; S[3] = tempo necessário para se viajar até o ponto 3; e assim por diante.

Com esse vetor podemos iniciar nossa busca binária, sendo o limite inferior = 0 e o limite superior = S[N], inicialmente.

Há outro ponto interessante aqui: Shrek não está limitado a alcançar o cidadão em cima de um ponto J. Ele pode interceptar o cidadão em um ponto intermediário entre um ponto J e o ponto J+1. Precisamos considerar isso quando quisermos aproximar o tempo mínimo em que Shrek pode alcançar o cidadão.

Voltando à busca binária, chute um tempo T entre o limite inferior e superior definidos. Em seguida, consulte o vetor S para verificar onde o cidadão estaria nesse tempo T. Na grande maioria dos casos, o cidadão estaria no meio da trajetória entre um ponto J e o ponto J+1.

Usando a famosa regra de três, calcule que porcentagem dessa trajetória o cidadão já teria cumprido, e calcule então o ponto P exato em que ele estaria.

Por fim, calcule o tempo necessário para que Shrek saia de seu ponto inicial e chegue até P, e verifique se esse tempo é menor ou igual a T. Se sim, considere esta uma resposta válida e busque aproximá-la mais. Atualize os limites inferior e superior.

[ricardo], [cristhian]

C – Vigilância – [spoj]

Temos várias câmeras que cobrem determinados segmentos, e o objetivo é escolher um sub-conjunto de câmeras, de tal modo que todos segmentos de rua sejam filmados por ao menos uma câmera.

Podemos visualizar isso como um problema de Programação Dinâmica. Seja dp[i] o menor custo para se escolher um subconjunto de câmeras que cubra todos os segmentos entre a_i e N, inclusive.

O cálculo de dp[i] consiste em escolher uma segunda câmera j tal que a_j <= a_i+1, e de preferência b_j > b_i, e resolver recursivamente o cálculo para dp[j]. O caso baso consiste em uma câmera k, tal que b_k = N.

PS: Para melhor performance na escolha da câmera j diante da câmera i, é recomendado que as câmeras sejam ordenadas de modo não-decrescente de acordo com a variável a_i, ou de acordo com a variável b_i em caso de empate.

[ricardo], [cristhian]

D – Pênalties – [spoj]

Como os limites aqui são baixos, podemos usar uma solução trivial onde após cada chute verificamos se um dos times ganhou ou não.

O segredo está em descobrir a equação certa. Siga a ordem dos chutes mantendo um placar corrente, e verifique o seguinte:

• Se mesmo que o time B acerte todos os chutes restantes ele não alcanCe o placar atual do time A, o time A ganhou a partida.
• Se mesmo que o time A acerte todos os chutes restantes ele não alcanCe o placar atual do time B, o time B ganhou a partida.

[cristhian], [ricardo]

E – Desafio das moedas prateadas – [spoj]

Seja G o grafo dado na entrada, e seja G’ o grafo G sem os arcos que chegam ao vértice de largada. Pelas restrições dadas no enunciado, G’ é um DAG e, logo, seus caminhos podem ser explorados por Programação Dinâmica (PD).

O estado da PD poderia ser [v][u][m], onde v indica a volta atual do jogador (<= 3), u indica o vértice em que ele se encontra (<= N) e m indica o conjunto de moedas já obtidas pelo jogador (<= 2^K). Os estados vizinhos seriam [v’][u’][m’] onde u’ é vizinho de u em G, v’ = v (ou = v+1 se u’=1) e m’ = m (ou = m’ unido à moeda de u’, se existir e ainda não tiver sido coletada). O processamento pára com v=4.

Esta solução, no entanto, ainda não é suficientemente rápida. Para melhorá-la, note que podemos considerar na PD apenas transações de estados que envolvam mudanças de volta ou do conjunto de moedas obtidas. Assim, o estado seria [v][u][m], com u <= K+1, considerando-se em u apenas os vértices que têm moedas, ou a largada. Os estados vizinhos seriam [v’][u’][m’] onde u’ tem moeda, ou é a largada.

Os caminhos mínimos em G’ entre os vértices que têm moedas podem ser preprocessados com outra PD. Para cada moeda ki, o estado [u][ki] responde o caminho mínimo do vértice u (<=N) ao vértice da moeda ki. Seus vizinhos são [u’][ki] onde u’ é vizinho de u em G’.

Por fim, o caminho mínimo em G entre todo vértice que tem moeda e a largada pode ser obtido com uma terceira PD. O estado [u] responde o caminho mínimo do vértice u (u <= N) ao vértice 1. Seus vizinhos são os estados [u’] onde u’ é vizinho de u em G.

[ricardo]

F – Escadas rolantes – [spoj]

Podemos resumir o exercício a: quantas vezes é possível dividir S por D? O desafio, porém, aparece quando notamos que o limite de S é bem alto, onde S <= 10^1000.

Javarianos não se intimidam com esse tipo de exercício, pois é possível resolvê-lo utilizando a biblioteca BigInteger. Os adeptos de C/C++, por outro lado, precisam ser mais meticulosos, pois sabem que 10^1000 não cabe em suas humildes variáveis long long.

A resposta está em implementar as divisões da moda antiga. Lembra aquele algoritmo de divisão que você aprendeu na primeira, ou segunda série? Pois é, vamos usá-lo. Pra quem não se lembra, veja [aqui] um exemplo.

[ricardo]

G – Senha da tia – [spoj]

Mantenha um contador para cada tipo de caractere requirido: minúsculo, maiúsculo e numérico. Incremente os contadores de acordo com a ocorrência deles na string. Ao final basta verificar se todas as condições foram satisfeitas.

Lembre-se de verificar se o tamanho da string dada também atende o número mínimo de caracteres.

[cristhian], [ricardo]

H – Fliperama – [spoj]

Note que temos um conjunto bem amplo de possíveis nomes a serem cadastrados: 26^3, para ser mais exato. Ou seja, todas as possíveis combinações de três letras. O problema aqui é que cada nome tem um conjunto limitado de combinações válidas.

Esse problema pode ser representado em um grafo bipartido. No conjunto esquerdo do grafo, insira um nó para cada nome diferente (e vários nós para o mesmo nome, se for o caso). No conjunto direito do grafo, insira um nó para cada combinação possível de letras (AAA, AAB, etc). Por fim, insira uma aresta entre os nomes do conjunto esquerdo do grafo com as suas possíveis combinações do conjunto direito. Por exemplo, uma aresta entre o nó Pedro e o nó PED, etc.

Com esta modelagem, podemos aplicar um algoritmo de Maximum Bipartite Matching (Emparelhamento Máximo Bipartido), e verificar se é possível que todos os nós do conjunto esquerdo estejam conectados com exatamente um nó distinto do conjunto direito.

[cristhian], [ricardo]

I – Remoção – [spoj]

O maior desafio deste exercício é fazer o que ele pede sem se perder como os alunos do Bruno Breno. Tirando isso, o algoritmo para resolução é bem direto:

1. Atualize os ponteiros do nó anterior ao PTR1 e seguinte ao PTR2 para “pularem” os nós entre PTR1 e PTR2.
(PTR1 -> ant) -> prox = PTR2 -> prox;
(PTR2 -> prox) -> ant = PTR1 -> ant;

2. Encontre o nó mais a esquerda da lista.

3. Imprima os nós entre o nó mais esquerda encontrado e o nó mais a direita da lista.

4. Imprima os nós entre PTR1 e PTR2, inclusive.

[bruno], [cristhian], [ricardo]

J – Seleção – [spoj]

Uma das maneiras de se resolver este exercício baseia-se em um pequeno insight e o conhecimento da biblioteca MultiSet de C++.

Se mantivermos um ponteiro direcionando o elemento E que está no centro da lista atual, não é difícil notar que, após a próxima inserção, o elemento que ficará no centro da lista pode ser: o elemento à esquerda de E; o elemento E; ou o elemento à direita de E.

Se estudarmos um pouco, notaremos que é possível descobrir a resposta acima se soubermos o número de elementos à esquerda e à direita do elemento E antes e após a inserção.

Utilizando a biblioteca MultiSet, podemos adicionar elementos utilizando a função insert, e manter o ponteiro com uma variável iterator.

PS: Notem que deve-se utilizar a biblioteca MultiSet e não Set. A diferença é que a primeira armazena o mesmo valor mais de uma vez se for preciso, e a segunda não. Isso afeta a movimentação dos ponteiros durante o algoritmo.

[vinicius], [ricardo], [cristhian]

 

Postem um comentário abaixo em caso de dúvidas, sugestões, soluções alternativas e críticas.