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

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.

Caravana

Escrito por Caique Paiva

Conhecimento Prévio Necessário:

• Vetores

Veja que, como queremos deixar todos os camelos com a mesma quantidade de carga, significa que todos os camelos terão carga de peso $\frac{a_1 + a_2 + \cdots + a_n}{n}$. Logo, a resposta pra cada $a_i$ é $a_i - \frac{a_1+a_2+\cdots+a_n}{n}$.

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

Conhecimento Prévio Necessário:

• Programação Dinâmica
• Soma de Prefixos
• Ordenação

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, nval) =$ 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.

Dona Minhoca

Escrito por Arthur Lobo

Conhecimento prévio necessário:

• Diâmetro de Uma Árvore
• Algoritmo Guloso
• Busca Binária

Veremos as salas como vértices e os túneis como as arestas de um grafo.

Parcial 1 (K = 1)

Para esta parcial, podemos posicionar apenas 1 radar, então ele deve ser posicionado em um vértice que minimiza a distância para o vértice mais distante. Esse vértice é o diâmetro da árvore, portanto o alcance do radar deve ser $\lceil \dfrac{diametro}{2} \rceil$.

Parcial 2 (A aresta $i$ liga os vértices $i$ e $i+1$)

Nessa parcial, o grafo é uma linha, então, para um $R$ fixo, vamos posicionar os radares nas posições $R+1, 3*R+2, 5*R+3,...,(2*K-1)*R+K$. Basta que o último radar proteja até a última sala , portanto $(2*K-1)*R+K+R \geq N \Rightarrow 2*K*R \geq N \Rightarrow R = \lceil \dfrac{N}{2*K} \rceil$.

Parcial 3 ($N,K \leq 100$)

Para essa parcial, iremos passar por cada $R$ de 1 até $N$ e ver qual é o primeiro que permite posicionarmos no máximo $K$ radares.

Agora para um $R$ fixo, temos que saber qual a menor quantidade de radares que precisamos posicionar. Podemos provar que o seguinte algoritmo guloso funciona: Primeiro enraizaremos a árvore no vértice 1. Agora vamos colocar um radar em um vértice $u$ apenas se for impossível continuarmos sem colocar. Ou seja, existe algum vértice na sua sub-árvore de $u$ a uma distância $R$ de $u$que não está protegido, então se não colocarmos nenhum novo radar em $u$ e continuarmos subindo em direção à raiz, esse vértice estaria desprotegido.

• Seja $rad_u$ a menor distância de $u$ para um vértice na sua sub-árvore que possui um radar.
• Seja $des_u$ a maior distância de um vértice da sub-árvore de u que está desprotegido, ou seja, o vértice mais fundo que não é protegido por nenhum radar. Caso não exista nenhum vértice desprotegido, $des_u = 0$.

Quando estamos vendo um vértice $u$, primeiro resolvemos esse problema para todos os vértices na sua sub-árvore, ou seja, sendo $F_u$ o conjunto dos filhos de $u$ (vértices que tem uma aresta com u e não são seu ancestral), chamamos $dfs(v)$ para todo $v \in F_u$, e então $rad_u = \min_{\forall v \in F_u} (rad_v) +1$ e $des_u = \max_{\forall v \in F_u} (des_v) +1$ (ou $des_u = 0$ se v é uma folha).

Se o radar mais próximo de $u$ consegue proteger o vértice mais longe de $u$ desprotegido, ou seja, se $red_u + des_u \leq R$, então podemos falar que $des_u := -1$, pois agora esse vértice que estava desprotegido (e todos os outros na sub-árvore, já que este é o mais longe) está protegido.

Se agora a distância do mais longe desprotegido for $R$, precisamos colocar um radar no vértice $u$, pois se continuarmos subindo em direção a raiz não podemos mais protegê-lo. Então fazemos $des_u := -1$, $red_u :=0$ e aumentamos a quantidade de radares usados.

Por fim, se ao chegarmos na raiz existir algum vértice desprotegido, então aumentamos a quantidade de radares novamente. A complexidade fica $O(N^2)$. Segue o código para melhor entendimento:

Clique aqui para conferir o código

Parcial 4 (Sem restrições adicionais)

É fácil ver que se podemos posicionar no máximo $K$ radares com raio $R$, então também podemos posicionar no máximo $K$ com raio $R+1$. Portanto, podemos fazer uma busca binária para encontrarmos qual o menor $R$ viável, a complexidade final fica $O(N \log N)$.

Construção de Rodovia

Escrito por Arthur Lobo

Conhecimento prévio necessário:

• Flood Fill (busca em grafos)
• Complexidade
• Princípio da casa dos pombos (PCP)

Observação: Para melhor entendimento, diremos que um par $(x,y)$ é conexo se existe um caminho de $x$ para $y$.

O problema diz que precisamos encontrar algum par de vertices $(u,v)$ tal que não existe aresta de $u$ para $v$ e não exista nenhum par $(x,y)$ tal que $(x,y)$ não é conexo, mas se tornaria conexo caso a aresta $u \rightarrow v$ fosse criada. Para chegarmos na solução completa, precisamos fazer uma série de observações e reduções.

Primeiramente, podemos reduzir as condições do problema para:

• Devemos encontrar um par $(u,v)$ tal que $(u,v)$ seja conexo e não existe a aresta $u \rightarrow v$.

Isso é verdade pois se $(u,v)$ não é conexo, então, criando essa aresta, o par $(u,v)$ se tornaria conexo, contradizendo o enunciado; e se $(u,v)$ é conexo, então criando essa aresta nenhum novo par se torna conexo, pois qualquer par que fosse usar essa aresta para ir de $u$ até $v$, poderia usar o caminho que já existia.

Parcial 1 (Existe um caminho entre todo par de vértices)

Nessa parcial, temos que todo par de vértices é conexo, então só precisamos encontrar um par de vértices $(u,v)$ que não possui aresta de $u$ para $v$, já que sabemos que existe um caminho de $u$ para $v$.
Para fazermos isso, primeiramente precisamos encontrar algum vértice $u$ que tem menos de $n-1$ arestas saindo dele, ou seja, que não liga para todo os outros vértices. Depois passamos por todos os outros vértices para descobrirmos algum vértice $v$ tal que não existe a aresta $u \rightarrow v$. Se não existir nenhum vértice $u$ satisfazendo com menos de $n-1$ arestas saindo dele, então a resposta é $-1$.

Parcial 2 (se existe uma rodovia de $x$ para $y$, então também existe uma rodovia de $y$ para $x$)

Nessa Parcial, temos que as arestas são bidirecionais, então todos os pares de vértice dentro de uma componente conexa são conexos. Portanto, apenas precisamos encontrar um par de vértices $(u,v)$ tal que $u$ e $v$ estão na mesma componente conexa e a resta $u \rightarrow v$ não existe.

Podemos usar uma ideia parecida com a da parcial anterior: precisamos encontrar algum vértice $u$ tal que existam menos de (tamanho da componente conexa de $u$) $-1$ arestas saindo dele, ou seja, não liga para todos os outros vértices da componente conexa dele. Depois passamos por todos os outros vértices para descobrirmos algum vértice $v$ que está na mesma componente de $u$ e não exista a aresta $u\rightarrow v$. Assim como na parcial anterior, se não existir $u$ que satizfaz a condição, a resposta é $-1$.

Parcial 3 (Sem restrições adicionais)

Podemos reduzir a condição ainda mais:

• Devemos encontrar uma tripla $(u,w,v)$ tal que as arestas $u \rightarrow w$ e $w \rightarrow v$ existem e a aresta $u \rightarrow v$ não existe.

Conseguimos provar isso por indução: digamos que agora estamos vendo o par $(u,v)$ e ele seja válido (é uma resposta), e o último vértice no caminho de $u$ para $v$ antes de $v$ é $w$. Se a aresta $u \rightarrow w$ existe, então chegamos na nossa condição. Se a aresta $u \rightarrow w$ não existe, então o par $(u,w)$ também é uma resposta. Portanto, podemos mudar o par que estamos vendo agora para $(u,w)$ e continuar fazendo isso até que cheguemos na nossa condição.

Até agora nossa solução é: primeiramente vamos fixar o $w$ da nossa tripla $(u,w,v)$ (vamos ver todos os $1 \leq w \leq N$). Agora, para cada $u$ tal que existe a aresta $u \rightarrow w$, veremos todos os $v$ tal que existe a aresta $w \rightarrow v$ (ou seja, veremos todas as triplas $(u,w,v)$ que existe a aresta $u \rightarrow w$ e $w \rightarrow v$). Podemos verificar em $O(1)$ se a tripla $(u,w,v)$ é válida, ou seja, se a aresta $u \rightarrow v$ não existe, utilizando um vetor de frequência ou um $unordered$ $set$.

A complexidade dessa solução é $O(M^2)$ e podemos vizualizá-la da seguinte forma: seja $G_{in}(x)$ o grau de entrada de $x$, $G_{out}(x)$ o grau de saída de $x$, e $T(M)$ a quantidade de operações do algoritmo com $M$ arestas. Note que $T(M)$ é igual ao somatório de $G_{in}(w)*G_{out}(w)$, para todo $1 \leq w \leq N$, pois para cada $w$ nós verificamos todos os pares $(u,v)$ em que $u$ chega em $w$ ($G_{in}(w)$ opções) e $v$ sai de $w$ ($G_{out}(w)$ opções), portanto teremos:

\begin{equation*} T(M) = \sum_{1 \leq w \leq N} (G_{in}(w)*G_{out}(w)) \leq \sum_{1 \leq w \leq N}(G_{in}(w)*M) \Rightarrow T(M) = M* \sum_{1 \leq w \leq N}(G_{in}(w)) \Rightarrow T(M) \leq M^2 \end{equation*}

Portando, a complexidade do nosso algoritmo é $O(M^2)$. Mas será que podemos deixar a complexidade ainda melhor que isso?

E se terminássemos o código assim que encontramos uma resposta? Ou seja, assim que encontramos $(u,v)$ que satisfaz nossas condições, instantaneamente retornamos esse par e terminamos o código. Podemos provar que a complexidade do algoritmo com essa otimização é $O(M*\sqrt{M})$, para isso vamos usar uma técnica chamada sqrt decomposition, que consiste em separar elementos (nesse caso, vértices) entre pesados e leves.

• Pertencerão ao conjunto $L$ os vértices leves, que serão todos os vértices $x$ tal que $G_{in}(x) < \sqrt M$.
• Pertencerão ao conjunto $P$ os vértices pesados, que serão todos os vértices $x$ tal que $G_{in}(x) \geq \sqrt M$. Sabemos que $|P| \leq \sqrt M$, pois, tendo em vista que a quantidade total de arestas é M, temos que:

\begin{equation*} |P|*\sqrt M \leq \sum_{x \in P} G_{in}(x) <= M \Rightarrow |P|*\sqrt M <= M \Rightarrow |P| <= \sqrt M \end{equation*}

Agora vamos analisar a complexidade de quando o vértice fixado $w$ (ou seja, o vértice a partir do qual vamos ver os pares $(u,v)$) é do conjunto $L$ e quando é do conjunto $P$:

Seja $T_L(M)$ a quantidade total de operações feitas quando o $w$ é do conjunto $L$ e temos $M$ arestas:

\begin{equation*} T_L(M) = \sum_{x \in L}(G_{in}(x)*G_{out}(x)) \leq \sum_{x \in L}(\sqrt M*G_{out}(x)) \Rightarrow T_L(M) \leq \sqrt M*\sum_{x \in L}(G_{out}(x)) \Rightarrow T_L(M) <= \sqrt M*M \end{equation*}

Para qualquer $w$, sempre verificaremos no máximo $M+1$ pares, pois se nos $M$ primeiros pares $(u,v)$ existia uma aresta de $u$ para $v$, então o $M+1-$ésimo par $(u,v)$ será a resposta. Já que todos os pares $(u,v)$ que vemos são diferentes, nas primeiras $M$ iterações vemos todos os pares que correspondem à arestas do grafo, então o $M+1-$ésimo par não pode corresponder à uma aresta pelo Princípio da Casa dos Pombos. Portanto, cada $w$ fará o mínimo entre $G_{in}(w)*G_{out}(w)$ e $M+1$ operações.

Seja $T_P(M)$ a quantidade de operações feitas quando o $w$ é do conjunto $P$ e temos $M$ arestas:

\begin{equation*} T_P(M) = \sum_{x \in P}min(G_{in}(w)*G_{out}(w),M+1) <= |P|*(M+1) \Rightarrow T_P(M) <= \sqrt M*M + \sqrt M \end{equation*}

Agora somamos a quantidade de operações de quando $w$ faz parte do conjunto $L$ e quando faz parte do conjunto $P$ para encontrarmos a quantidade total de operações $T(M)$:

\begin{equation*} T(M) = T_L(M) + T_P(M) \leq \sqrt M*M + \sqrt M*M + \sqrt M \Rightarrow T(M) \leq 2*\sqrt M*M +\sqrt M \end{equation*}

Portanto, a quantidade total de operações com M arestas é no máximo $2*\sqrt M*M +\sqrt M$, então a complexidade da nossa solução é $O(M*\sqrt M)$.

Para que o código fique mais simples e possamos verificar se existe a aresta $u \rightarrow v$, vamos fixar o $u$ da tripla $(u,w,v)$, e não o $w$, mas isso não muda a analise de complexidade. Segue o código para melhor entendimento:

Clique aqui para conferir o código