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