Treino de 10 de julho de 2015

De DCC UFMG - Maratona de Programação
Ir para: navegação, pesquisa

Este é o sétimo treino no novo formato. Esperamos que gostem. Abaixo, seguem os links para os problemas desse treino e uma descrição de uma solução possível para cada um deles. Recomenda-se não olhar os problemas antes do dia do treino (embora ninguém vá te impedir). Até lá, você pode ir treinando com outros problemas do Codeforces e de regionais passadas.

Conteúdo

Problemas

Nível Problema
1 Acima da média
2 Coral perfeito
3 Triângulos
4 Tobogan de bolinhas
5 Babel

Soluções

Acima da média

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.
Apenas faça o que o problema pede: primeiro, calcule a soma das notas de todos os alunos; depois, calcule a média dividindo a soma obtida pelo número de alunos. Por fim, veja quantos alunos tiraram nota acima da média e imprima este número dividido pelo número de alunos, com a formatação correta.

Coral Perfeito

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.

Vamos analisar o que o problema pede com cuidado. É dado um vetor $v$ de $n$ inteiros, e a esse vetor pode ser aplicada uma operação: simultaneamente incrementar um de seus elementos e decrementar um outro. Deseja-se saber quantas operações são necessárias para que todos os elementos do vetor, ao final, sejam iguais.

Primeiro, podemos observar que a operação não muda a soma dos elementos do vetor: a soma é incrementada de um e decrementada de um; permanecendo a mesma. Isto significa que, ao final, se for possível fazer o que o problema pede, cada elemento deverá valer exatamente $\frac{1}{n} \sum_{i=1}^n v_i$. Logo, se a soma dos elementos não for divisível por $n$, sabemos de antemão que é impossível fazer o que é pedido.

Por outro lado, se a soma dos elementos de $v$ for divisível por $n$, podemos ver que sempre é possível igualar todos os elementos. Provamos isto da seguinte forma: pela observação feita acima, concluímos que:

$$\sum_{i=1}^n v_i = kn$$

Para algum $k$ inteiro. $k$ será o valor de todos os elementos do vetor após o processo. Logo,

$$\sum_{i=1}^n v_i = \sum_{i=1}^n k$$ $$\sum_{i=1}^n v_i - \sum_{i=1}^n k = 0$$ $$\sum_{i=1}^n (v_i - k) = 0$$

Ou seja, a soma das diferenças entre o valor final e o valor inicial de cada elemento é zero. O que significa que para cada vez em que um elemento precisa ser incrementado, existe um elemento que deve ser decrementado. Logo, a situação em que há um elemento que precisa ser alterado mas não há outro elemento que precisa da operação contrária é impossível.

Ok, sabemos que é possível, mas de quantas operações precisaremos? Basta observar que precisamos de uma operação para cada vez em que alguém será incrementado (ou decrementado: você pode calcular das duas formas. A última equação acima nos garante que o resultado será o mesmo). Ou seja: calcule $k$, depois some a diferença entre $k$ e todos os elementos maiores que $k$: esta será a resposta, que assim é obtida em $O(n)$.

Triângulos

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.

Pelo enunciado do problema, todos os $N$ pontos estão inscritos em uma mesma circunferência $C$. Em um primeiro momento, podemos achar que existe uma quantidade de triângulos muito grande inscritos em um círculo. Pensemos, então, na seguinte questão: a quantos triângulos equiláteros inscritos em $C$ um ponto $p$ pode pertencer?

A resposta é exatamente 1. É fácil de ver que, para que duas arestas do triângulo $T$ tenham o mesmo comprimento, os arcos de $C$ também precisam de ter comprimentos iguais. Como precisamos de 3 arestas para a formação do triângulo, o comprimento de cada uma é exatamente $\frac{1}{3}$ do perímetro de $C$.

Podemos então transformar a entrada do problema para conter o comprimento dos arcos entre cada ponto $p_i$ e um ponto fixo qualquer $p_0$, gerando o vetor de arcos $A$. Agora, para cada arco, precisamos de determinar se os outros dois arcos necessários para a formação do triângulo existem no vetor de arcos.

Note que esse vetor já está ordenado e, com isso, podemos pesquisar valores no mesmo em $O(\log N)$ usando Busca Binária. Os valores a serem pesquisados são, simplesmente, $(a_i + \frac{1}{3}|C|)$ e $(a_i + \frac{2}{3}|C|)$. A complexidade dessa solução é, utilizando busca binária, $O(N \log N)$.

Não se esqueça de que se C não for divisível por 3, o número de triângulos que podem ser formados é 0.

Tobogã de Bolinhas

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.

O brinquedo que foi construído é composto por um conjunto de segmentos de retas no plano, com um de seus pontos na reta $x = 0$ ou $x = L$. Na especificação do brinquedo, é garantido que todas as retas tem declividade favorável e que toda reta começa ($Y_i$), no máximo, na altura de término ($Y_f$) da anterior.

Essas restrições permitem que, para cada uma das primeiras $N-1$ retas, precisemos de computar a menor distância entre o ponto final $(X_{f_i}, Y_{f_i})$ e a próxima reta $r_{i+1}$, e entre o mesmo e a haste oposta. Ou seja:

\begin{equation} S_i = \text{min}(D(r_i, r_{i+1}), D(r_i, H_i)) \end{equation}

A função $D(r_i, r_{i+1})$ é o principal desafio do problema. Se tivéssemos retas (e não segmentos), poderíamos simplesmente calcular a distância ponto reta, e o resultado seria esse. Porém, a projeção ortogonal de $f_i = (X_{f_i}, Y_{f_i})$ em $r_{i+1}$, que podemos chamar de $p = (X_p, Y_p)$, pode não estar no segmento. Para determinar isso, precisamos conhecer $p$. Relembrando geometria analítica, uma reta $r$ pode ser descrita como:

\begin{array} xY &= mX + b \\ m &= (Y_f - Y_i)\ /\ (X_f - X_i) \\ b &= Y_i - mX_i \\ \end{array}

Como estamos interessados na projeção ortogonal de $f_i$ em $r_{i+1}$, vamos traçar a reta $t_i$, ortogonal a $r_{i+1}$ e que passa por $f_i$, com as seguintes propriedades:

\begin{array} Xm_t &= -1\ /\ (m_{r_{i+1}}) \\ b_t &= Y_{f_i} - mX_{f_i} \\ \end{array}

Agora, $p$ é simplesmente o ponto de interseção entre $t_i$ e $r_{i+1}$, ou seja:

\begin{array} .X_p &= (b_{r_{i+1}} - b_t)\ /\ (m_t - m_{r_{i+1}}) \\ Y_p &= m_tX_p + b_t \end{array}

Se $p$ estiver entre $(X_{i_{i+i}}, Y_{i_{i+1}})$ e $(X_{f_{i+i}}, Y_{f_{i+1}})$, $D(r_i, r_{i+1}) = (X_{f_i} - X_p)^2 + (Y_{f_i} - Y_p)^2$, caso contrário, o ponto mais próximo será $f_{i+1}$.

A solução do problema é, então, $\min(S_i)$.

Babel

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.

O enunciado do problema nos leva a pensar em gratos. Tentemos montar um grafo em que a resposta seja o peso de um caminho mínimo entre dois vértices. Fazendo isto, a resposta pode ser obtida pelo Algoritmo de Dijkstra.

Vamos criar um grafo direcionado com pesos com um vértice para cada palavra, um vértice para a língua de origem e um para a de destino. Criamos também um vetor para cada língua (mesmo as que não são de origem nem de destino) contendo todas as palavras daquela língua. Para cada par de palavras $(p_1, p_2)$ de uma mesma língua, se elas não tiverem uma mesma criamos duas arestas: uma de $p_1$ para $p_2$ com peso $|p_2|$ e uma de $p_2$ para $p_1$ com peso $|p_1|$ ($|p|$ é o número de caracteres da palavra $p$). Além disso, para cada palavra $p_o$ da língua de origem, criamos uma aresta do vértice especial da língua de origem para $p_o$ com peso $|p_o|$. De forma similar, para cada palavra $p_d$ da língua de destino, criamos uma aresta que sai do vértice especial da língua destino para $p_d$ com peso $0$.

Vejamos as propriedades do grafo que acabamos de montar. Todas as arestas conectam palavras que pertencem a uma mesma língua e não têm a mesma letra inicial, por construção. Além disso, todo caminho que sai do vértice da língua de origem tem o peso igual à soma do comprimento das palavras usadas, pois sempre que entramos em um vértice de uma palavra estamos pagando um custo igual ao comprimento daquela palavra. Por último, não há custo adicional para um caminho que termina no vértice da língua de destino. Essas propriedades garantem que a resposta desejada é igual ao caminho mínimo entre o vértice da língua de origem e o vértice da língua de destino. Usando o Dijkstra, isto pode ser obtido com complexidade $O(N^2 \lg N)$.


Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas