OBI 2022 - Fase 3 - Programação Nível 1

Para se preparar para a OBI, confira o nosso Roteiro de Estudos, nele você vai encontrar um direcionamento completo de como estudar!

Para conferir a prova na íntegra, clique aqui.

Carro Elétrico

Escrito por Enzo Dantas

Conhecimento prévio necessário:

Flood Fill (busca em grafos)

Parcial 1 (37 pontos):

$N=2$

Para essa subtask, devemos apenas calcular se é possível ir de uma cidade à outra usando o carro, ou seja, se a autonomia dos carros é maior ou igual à distância entre as duas cidades. A distância entre dois pontos é $dist=100*(|x_1-x_2| + |y_1-y_2|)$ km, e devemos checar se $A \geq dist$ . Para facilitar a compreensão, vamos nos referir a $A$ como se fosse $\frac{A}{100}$ e a $dist$ como se fosse $|x_1-x_2| + |y_1-y_2|$ .

Parcial 2 (32 pontos):

$Y=1$ (todas as cidades estão na mesma linha), e é garantido que as cidades são dadas em ordem crescente de $X$ (isto é, $x_1<x_2<...<x_n$ ).

Perceba que, ao simular imaginariamente um caso qualquer, vão se formar algumas "regiões" conectadas por carro.

Vamos chamar essas "regiões" de "componentes".

Perceba que, se a distância entre $x_i$ e $x_{i+1}$ é maior que A, eles fazem parte de componentes diferentes e é preciso usar o avião para conectá-las. Assim, para contar quantos aviões precisamos usar, vamos contar quantas vezes $|x_i-x_{i+1}| > A$ .

Parcial 3 (31 pontos):

Nenhuma restrição adicional

Nota: esse é um problema conhecido, no qual se deve contar o número de componentes conexas em um grafo.

Similarmente a subtask anterior, algumas componentes conectadas por carro vão se formar ao simular um caso qualquer.

Se temos N componentes, qual o número mínimo de aviões necessários para conectar todas elas?

Lema: o número mínimo de arestas necessárias para conectar N componentes = N-1

Imagine que temos uma componente só. Nesse caso, não precisamos de nenhuma nova aresta para conectar todas as componentes (1 componente, 0 arestas). Se adicionarmos mais uma componente, precisaremos adicionar uma aresta (2 componentes, 1 aresta), mais outra componente, mais outra aresta (3 componentes, 2 arestas), e assim em diante. Ou seja, para cada nova componente adicionada, precisaremos de mais uma aresta, então a subtração $Componentes-Arestas$ é constante. Como no caso inicial (componentes = 1) o número de arestas é $Componentes-1$ , para qualquer número de componentes usaremos $Componentes-1$ arestas.

Sendo assim, para construir o grafo e achar as componentes, vamos criar uma aresta entre todos os pares de pontos tal que a distância entre eles é menor ou igual a A. Feito isso, vamos realizar várias DFS's: vamos iterar pelos vértices e, se o vértice $v_i$ não tiver sido visitado, vamos adicionar 1 ao contador de componentes, vamos rodar uma DFS e vamos marcar todos os vértices da componente como visitado. Ao fim, devemos printar (quantidade de componentes - 1).

Complexidade:

Complexidade de memória: para cada vértice criaremos no máximo $N$ arestas. Como temos $N$ vértices, teremos $N*N$ arestas no total $\Rightarrow O(N^2)$ .

Complexidade de tempo: a complexidade de criar as $N^2$ arestas é $O(N^2)$ , enquanto a complexidade da DFS é $O(V+E) = O(N+N^2)$ . A complexidade final é $O(N^2)$ .

Clique aqui para conferir o código

Restaurante de Pizza

Escrito por Enzo Dantas

Conhecimento prévio necessário:

Estruturas Condicionais

Para que a pizza caiba inteiramente na caixa, seu diametro deve ser menor ou igual a cada um dos lados da caixa. Além disso, para que todas as fatias sejam do mesmo tamanho, a soma de vários ângulos internos deve formar um círculo completo (uma pizza), ou seja, 360 deve ser um múltiplo do ângulo interno das fatias.

Clique aqui para conferir o código

Dígitos

Escrito por Vitor Veiga

Conhecimento prévio necessário:

Strings e Vetores

Dada uma sequência de todos os dígitos presentes entre dois números quaisquer $A$ e $B$ , queremos encontrar o menor $A$ que satisfaz a sequência. A ideia para o problema será checar todos os possíveis $A's$ , de $1$ até $N$ algarismos, até achar um termo inicial que satisfaz as restrições da sequência.

Para isso, utilizaremos as strings para nos auxiliar, pela maior facilidade em adicionar e remover algarismos. Começamos com duas strings $ini$ e $busca$ , que armazenam o número inicial e o próximo número que temos que achar para haver uma sequência válida, ou seja, $ini + 1$ , $ini + 2$ , $ini + 3$ , e assim por diante. Sempre que acharmos o $busca$ , adicionamos uma unidade no número contido nele e continuamos nosso loop.

Para melhor entendimento da ideia, o passo a passo do primeiro caso teste:

$N = 6$ e $S = {1, 2, 3, 1, 2, 4}$

O primeiro número inicial que testaremos será o $1$ :
$1$ (ok)
$1, 2$ (ok)
$1, 2, 3$ (ok)
$1, 2, 3, 1$ (absurdo)

Depois, testaremos $12$ :
$12$ (ok)
$12, 31$ (absurdo)

Finalmente, testaremos $123$ :
$123$ (ok)
$123, 124$ (ok)
fim da sequência

Note que caso continuássemos, também seria válida a sequência que inicia com o número $123124$ , que só teria ele mesmo.

Segue o código:

Clique aqui para conferir o código

Pilha de Moedas

Escrito por Caique Paiva

Conteúdo Prévio Necessário:

Primeiro, vamos ordenar as pilhas por quantidade de moedas na ordem crescente. Por exemplo, a sequência de pilhas $(3,5,8,4,5,8)$ vai virar $(3,4,5,5,8,8)$ . Obviamente isso não vai mudar a resposta final, porém vai nos ajudar a achar a resposta.

Como foi spoilado nos conteúdos, vamos fazer programação dinâmica!! A ideia principal do problema é que os valores mais altos nunca vão ser alterados, pois isso é obviamente não optimal (Por exemplo, no exemplo $(3, 4, 5, 5, 8, 8)$ , não faz sentido colocarmos uma moeda em um dos oitos, por que isso vai sempre deixar a quantidade de moedas diferente maior).

Com isso, podemos fazer a operação ser: Pegar um intervalo $[l, r]$ e fazer com que todos os valores sejam iguais a $v[r]$ , e isso diminui a quantidade de valores distintos. Tal operação tem um custo de $v[r] - v[l] + v[r] - v[l+1] + \cdots v[r]-v[r] = (r-l+1)*v[r]- (v[l]+v[l+1]+\cdots v[r])$ .

Certo, mas por que fizemos essa mudança de operação? A primeira vista parece ser inútil, mas o ponto todo é que nunca vamos fazer essa operação duas vezes no mesmo índice, o que nos ajuda muito a fazer a $dp$ .

Com isso, seja $dp(pos, nvsl) =$ a quantidade de operações que precisamos para o intervalo $[1, pos]$ ter no máximo $nval$ valores distintos. Então

$dp(pos, nval) = \min_{1 \le i \le pos}(dp(pos-i, nval-1) + i*v[pos] - (v[pos]+v[pos-1]+\cdots + v[pos-i+1])$

E os casos bases vão ser $dp(0, nval) = 0$ e se $pos < nval \longrightarrow dp(pos, nval) = INF$ .

Usando uma soma de prefixo para manter o valor de $v[pos] + v[pos-1] + \cdots v[pos-i+1]$ , o código vai rodar em $O(n^2 k)$ , pois para calcular toda a dp leva $O(nk)$ de tempo, e a transição da dp é $O(n)$ . Tal complexidade passa, pois $n, k \le 500$ .

Clique aqui para conferir o código

Fica de exercício para o leitor codar o problema com uma dp iterativa ao invés de recursiva.