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:
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:
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:
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.