Comentário por Leonardo Paes, Thiago Mota e Lúcio Figueiredo
Para conferir a prova na íntegra, clique aqui.
Irmãos
Conhecimento prévio necessário:
Seja:
- $$n$$ a idade do irmão mais novo;
- $$m$$ a idade do irmão do meio;
- $$v$$ a idade do irmão mais velho.
De acordo com o enunciado, $$v – m = m – n$$, ou seja, a diferença de idade do irmão mais velho pro do meio é a mesma diferença de idade do irmão do meio pro mais novo. Como queremos saber $$v$$, basta isolarmos $$v$$ na equação, obtendo: $$v = m + m – n$$.
Código de exemplo:
Camisetas da Olimpíada
Conhecimento prévio necessário:
Para resolvermos esse problema, basta utilizarmos duas variáveis auxiliares $$qtdp$$ e $$qtdm$$ que guardam, respectivamente, a quantidade de camisetas pequenas e a quantidade de camisetas médias escolhidas pelos premiados. Então, basta checarmos se a quantidade de camisetas pequenas produzidas é maior ou igual a $$qtdp$$ e se a quantidade de camisetas médias produzidas é maior ou igual a $$qtdm$$. Se essa condição for verdadeira, todos os premiados serão atendidos com a camiseta do tamanho que escolheram, então imprimimos $$S$$, caso contrário, imprimimos $$N$$.
Código de exemplo:
Três por Dois
Conhecimento prévio necessário:
Vamos olhar para o seguinte caso: $$[1, 2, 3, 4, 5, 6]$$. Para reduzir o preço total dos chocolates temos que tentar remover da nossa soma o maior elemento possível; para isso, vamos agrupar os três maiores elementos $$(4, 5, 6)$$. Através deles é possível notar que sempre teremos que pagar os dois maiores chocolates (que, nesse caso, são os chocolates $$(5, 6)$$), pois não existe nenhuma maneira de juntar três elementos de tal forma que o menor deles seja ou o $$5$$ ou o $$6$$. Assim, a melhor opção é remover o $$4$$ e pagarmos apenas $$5 + 6 = 11$$ nesse grupo, restando no vetor os chocolates $$[1, 2, 3]$$.
Podemos aplicar esse algoritmo novamente e pegar os três maiores elementos do vetor restante e remover o menor entre eles, pagando nesse grupo o valor de $$2 + 3 = 5$$; somando os dois grupos temos, no total, $$11 + 5 = 16$$.
Caso o restante do nosso vetor tenha apenas um ou dois elementos, a nossa única opção é pagar eles. Isso ocorre pois não existe nenhuma maneira de conseguir descontos com menos de $$3$$ chocolates.
Segue o código:
Ralouim
Conhecimento prévio necessário:
Defina $$dist(i, j)$$ como a distância euclidiana entre as tendas $$i$$ e $$j$$.
Seja $$dp[i][j]$$ o maior número de guloseimas que Pedrinho pode ganhar, assumindo que a tenda atual em que Pedrinho se encontra é $$j$$ e a tenda anterior foi $$i$$. Assim, tem-se que:
$$dp[i][j] = max(1 + dp[j][k])$$ dentre todos os $$k$$ tais que $$1 \leq k \leq N$$ e $$ dist(i, j) > dist(j, k)$$
Assim, é possível calcular $$dp[i][j]$$ em $$O(n^3)$$, já que a programação dinâmica possui $$N^2$$ estados e $$N$$ transições. A resposta final é $$max(dp[0][i])$$ dentre todos os $$1 \leq i \leq N$$. Esta solução é suficiente para conseguir $$60$$ pontos no problema. Para alcançar a pontuação completa, precisamos otimizar o cálculo de $$dp$$.
Perceba que o caminho calculado em $$dp[i][j]$$ utiliza apenas “arestas” (pares de tendas consecutivas) com distâncias estritamente menores que $$dist(i, j)$$. Assim, ordenaremos cada um dos $$O(n^2)$$ possíveis pares de tendas crescentemente pela distância. Podemos fazer isso inserindo cada par em um $$vector$$ de $$pair$$ e em seguida ordenando-o.
Agora, vamos iterar por cada um dos pares de tendas na ordem em que se encontram no vector. Suponha que o par atual é $$(i, j)$$. Note que $$dp[i][j]$$ tem valor igual a $$1$$ mais o maior caminho que começa em $$j$$ e utiliza apenas arestas com distância menor que $$dist(i, j)$$.
Portanto, defina $$mx[x]$$ como o maior caminho que começa na tenda $$x$$ e tem como arestas apenas pares de tendas com índices no vector menores que o atual (e por consequência, com distância menor que $$dist(i, j)$$). Temos então que $$dp[i][j] = 1 + mx[j]$$. Agora que $$dp[i][j]$$ foi calculada, o que resta é atualizar o vetor auxiliar $$mx[]$$ para cálculos futuros; já que encontramos um novo caminho que começa em $$i$$, $$mx[i] = max(mx[i], dp[i][j])$$.
Assim, conseguimos calcular o valor $$dp[i][j]$$ para cada par de tendas $$(i, j)$$. Como há $$O(n^2)$$ pares de tendas e precisamos ordená-las, a complexidade final é $$O(n^2 \log_{} n^2)$$. Confira o código abaixo para melhor entendimento:
OBS: Um detalhe de implementação importante é que precisamos calcular a $$dp$$ de pares de tendas com mesma distância antes de atualizar o vetor $$mx$$, já que caso contrário estaríamos encontrando caminhos com arestas diferentes de mesma distância. Confira este trecho do código com cuidado.