Comentário Noic OBI 2020 - Fase 1 Turno B - Programação Nível 2

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:

• Entrada e Saída

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:

• Entrada e Saída
• Estruturas Condicionais
• Loops

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:

• Ordenação
• Algoritmos Gulosos

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:

• Ordenação
• Programação Dinâmica

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.