Simulado - Segunda Fase OBI 2021 - Comentário P2

Comentário por Luca Dantas, Leonardo Paes, Lúcio Figueiredo e Pedro Racchetti

Para conferir a prova na íntegra, clique aqui.

Binário

Conhecimento Prévio Necessário:

Estrutura de Dados Set

Para resolver este problema, vamos utilizar a seguinte observação:

Observação: Em um vetor binário $V$ , defina $ultimo_0$ como maior índice $i$ tal que $V[i] = 0$ ; de forma similar, defina $primeiro_1$ como o menor índice $i$ tal que $V[i] = 1$ . O vetor $V$ será um vetor ordenado crescentemente se e somente se $ultimo_0 < primeiro_1$ .

Para resolvermos o problema, precisamos de uma estrutura de dados que consiga armazenar dinamicamente (ou seja, com operações de update) os índices $ultimo_0$ e $primeiro_1$ . Uma estrutura que satisfaz esta condição é o Set; podemos utilizar dois sets, $set[0]$ e $set[1]$ , que guardam todos os índices do vetor que contém $0$ e $1$ , respectivamente. Assim, é facil manter os dois sets após uma operação de update: se o índice $i$ teve seu valor modificado, basta remover $i$ de $set[V[i]]$ e inserir $i$ no outro set. Para responder se o vetor está ou não ordenado, utilizaremos a observação acima, conferindo se o maior elemento de $set[0]$ (ou seja, $ultimo_0$ ) é ou não menor que o menor elemento de $set[1]$ (ou seja, $ultimo_1$ ).

Como utilizamos um set em cada operação de update, a complexidade final da solução é $O(N + M \cdot \log_{} N)$ . Segue o código, com comentários, para melhor compreensão do problema:

Problemas Explosivos

Conhecimento Prévio Necessário:

Para esse problema, podemos usar um laço $while$ , para repetirmos o algoritmo do problema, verificando com a estrutura $If/Else$ se $n$ é par ou ímpar com a operação de modularidade, já que com um número ímpar $k$ , a operação $k\ \%\ 2$ sempre resultará $1$ , e para um número par $k$ , a operação $k\ \% \ 2$ sempre resultará $0$ . Então, aplicamos com operadores básicos o algoritmo do problema, até que $n$ se-torne $1$ . Usaremos uma variável contadora, incrementando-a por um a cada iteração, sendo então o primeiro número da resposta, e uma variável que irá manter o valor máximo atingido usando a função $max$ do C++, o segundo número da resposta.

Segue o código, com comentários, para melhor compreensão do problema:

Lâmpadas

Conhecimento prévio necessário:

Subtarefa 1

Inicialmente esse problema pode parecer bastante com o problema da mochila, porém nesse caso os itens não têm valores para maximizarmos. Além disso os itens têm pesos variados e o que queremos saber é de quantas maneiras diferentes nós podemos escolher o peso dos itens de modo que caibam na mochila. Felizmente ainda podemos utilizar uma construção semelhante à do problema da mochila. Assim como no problema da mochila, se dois estados têm o mesmo peso podemos agrupá-los, pois para a resposta final e para a construção de estados seguintes eles se comportam idênticamente. Então para construirmos a DP só precisamos, para cada item, considerar todas as possibilidades que ele pode assumir (cada valor no intervalo $[l_i, r_i]$ ) e continuar nos respectivos estados.

Ao final teremos uma dp da seguinte maneira: $dp(i, p) =$ quantas possibilidades existem utilizando somente itens de 1 a $i$ tal que a soma deles seja igual a $p$ .

Complexidade:
Tempo - $O(N M^2)$ , pois teremos que, para cada estado, considerar cada uma das $r_i - l_i + 1$ possibilidades individualmente.
Memória - $O(N M)$ .

Segue o código com uma possibilidade de implementação (iterativo e pull dp) para melhor entendimento:

Subtarefa 2

Tendo construído a base da DP, precisamos tentar otimizar alguma parte para passar no limite dessa subtask. Uma coisa interessante que podemos perceber é que todas as $O(M)$ possibilidades que nós consideramos em cada estado na realidade só se referem a uma subsequência contínua de estados da dp que já calculamos, mais precisamente ao intervalo $[dp[i-1][p - r_i], dp[i-1][p-l_i]]$ , portanto podemos aplicar a técnica de soma de prefixo e calcular esse valor em $O(1)$ !

Complexidade:
Tempo - $O(N M)$ .
Memória - $O(N M)$ .

Segue o código para melhor entendimento (note que é necessária uma implementação iterativa para resolver essa subtask):

Subtarefa 3

Para resolver essa última subtask precisamos simplesmente aplicar um truque de implementação, chamado popularmente de Memory Saving Trick, no qual basicamente utilizamos uma propriedade da DP para salvar uma dimensão de memória. Essa propriedade é que, para todo conjunto de estados $(i, x)$ com qualquer valor de $x$ , os únicos estados que dependeremos estão dentro do conjunto de estados na forma $(i-1, y)$ com qualquer valor de $y$ possível. Desse modo ao invés de termos que salvar uma matriz $dp[N][M]$ podemos só salvar uma matriz $dp[2][M]$ , onde salvamos somente a coluna anterior e a utilizamos para construir a seguinte, e ao acabarmos de contruir a coluna $i$ apagamos a $i-1$ , sobscrevendo a $i$ no seu lugar e continuamos a construção com a fileira $i+1$ , até termos terminado todos os valores de $i$ entre $1$ e $N$ . Desse modo conseguimos dividir a memória utilizado por $O(N)$ e isso é suficiente para passar no limite de memória estabelecido.

Complexidade:
Tempo - $O(N M)$ .
Memória - $O(M)$ .

Segue o código para melhor entendimento (note que é necessária uma implementação iterativa para resolver essa subtask):

Reforma

Conhecimento prévio necessário:

Subtarefa 1

Há diversas soluções possiveis. Uma delas se resume em escolher as seguintes arestas como não inutilizadas: $(1, 2), (2, 3), ..., (n-1, n)$ . Ou seja, devemos imprimir todas as outras arestas, com exceção dessas. É fácil ver que existe apenas um caminho entre qualquer par de cidades através dessa configuração de estradas, já que o grafo descrito consiste de apenas um caminho, ou seja, não tem ciclos.

Complexidade:
Tempo - $O(N + M)$ , pois teremos que ler a entrada.

Segue um código de exemplo (feito por Leonardo Paes):

Subtarefa 2 - Grafos + Set

Uma maneira possível de resolver o problema é através da DFS. Imagine que iniciamos a DFS em um vértice arbitrário, por exemplo o vértice 1. Seja $u$ o vértice atual do algoritmo da DFS. Há dois tipos de vizinhos $v$ de u.

$v$ ainda não foi visitado pela DFS.
$v$ já foi visitado pela DFS.

No primeiro caso, chamaremos a função da DFS para $v$ , como normalmente fazemos no algoritmo da DFS. Já no segundo caso, note que $v$ já foi visitado pelo algoritmo, ou seja, já existe um conjunto de estradas que, partindo do vértice $1$ chega em $v$ . Portanto, não será necessário manter a aresta de $u$ para $v$ . Então, ela pode ser considarada uma estrada inutilizada.

Para mantermos tais estradas inutilizadas, podemos utilizar um $set<pair<int,int>>$ .

Complexidade:
Tempo - $O(N + M \cdot \log_{} M)$ .

Segue um código de exemplo (feito por Leonardo Paes):

Subtarefa 2 - Union-Find

Outra maneira possível de solucionar o problema é utilizando da estrutura de dados conhecida como Union-Find. Por favor, leia a aula escrita pelo incível Rogério Júnior, linkada na seção "Conhecimento prévio necessário". Para cada aresta do grafo $(u, v)$ , há 2 possiblidades: Ou ambos os vértices estão na mesma componente, ou estão em componentes separadas. No primeiro caso, sabemos que a aresta atual é desnecessária, por criaria mais de um caminho de $u$ para $v$ . No segundo caso, utilizaremos a aresta atual para criar um caminho entre eles, utilizando a função $join$ do Union-Find.

Complexidade:
Tempo - $O(N \cdot \alpha)$ .

Segue um código de exemplo (feito por Luca Dantas):