OBI 2024 Terceira Fase Programação 1

Se você quiser se preparar para a OBI, não deixe de conferir o Roteiro de estudos de informática, e também a página de informática do NOIC, com todos nossos materiais.

Musical

Escrito por Caique Paiva

Conhecimentos Prévios Necessários:

• Algoritimos Gulosos

Vamos resolver o problema caso fosse uma linha ao invés de um loop.

Brincando com o primeiro caso teste, podemos perceber que vale a pena deixar os números em ordem crescente! A intuição para você perceber que isso é verdade é fazendo casos pequenos na mão, como os casos testes, e então, caso eu tenha 3 elementos $a<b<c$, se eu colocar $a, b, c$ nessa ordem, é melhor que colocar eles na ordem $a, c, b$ por exemplo, pois na primeira ordem, a resposta vai ser $b-a+c-b=c-a$, enquanto na outra vai ser $2*c-b-a$, o que é pior.

Veja que, ao colocar os termos em ordem crescente, ou seja, $a_1 \le a_2 \le \cdots \le a_n$, a resposta vai ser $a_n-a_1$, pois os termos que estão no meio vão se cancelar.

Agora para o caso do círculo, podemos ter a mesma intuição, e perceber que a resposta vai ser $2\times (a_n-a_1)$, pois agora adicionamos a diferença entre $a_n$ e $a_1$, as duas pontas da linha. Portanto, o algoritmo vai ser pegar o menor valor e o maior valor do array, e imprimir essa diferença.

Clique aqui para ver o código

Entrevistas

Comentário escrito por Estela Baron

Conhecimento prévio necessário:

• Matriz de adjacência
• DFS
• Set

Subtarefa 2 e 3: N<=500 e K<= 50

Observe que a tabela de amizades nada mais é do que uma matriz de adjacência, ou seja, podemos resolver o problema utilizando o conceito de grafos. Com isso, a amizade entre dois candidatos representa uma aresta que liga os vértices dessas duas pessoas. Logo, para responder cada entrevista, marcamos todos os candidatos presentes por meio de um vetor que indica se o vértice é um candidato ativo ou não. Depois, para cada candidato, fazemos uma dfs a partir dele. Se nessa dfs chegarmos em um vértice que está ativo, quer dizer que pelo menos dois candidatos são amigos e, por isso, a resposta tem que ser  'S'. A complexidade fica $O(E*K*N)$.

Subtarefa 4: Cada candidato possui no máximo um amigo

Como cada candidato possui no máximo um amigo, basta verificarmos, para cada entrevista, se o amigo daquele candidato está presente ou não. Ao ler a entrada da tabela de amizades, vamos criar um vetor para guardar um único valor, que será o índice do amigo daquele candidato.Em seguida, em cada entrevista, vamos marcar em um vetor quais candidatos estão ativos. Daí, para cada candidato, vamos consultar no vetor com o amigo de cada pessoa se o candidato está ativo ou não. Se estiver, quer dizer que tem dois amigos e, por isso, marcamos a resposta como 'S'. A complexidade fica $O(E*K)$.

Subtarefa 5: Sem restrições adicionais

Como visto anteriormente, vamos transformar a tabela de amizades em um conjunto de grafos. Observe que podemos ter vária componentes, ou seja, vários grupos de amigos que não compartilham arestas em comum. Por isso, para resolver o problema, para cada candidato, de 1 até N, vamos verificar se ele já pertence a uma componente ou não, ou seja, se ele já foi visitado anteriormente por uma dfs. Se ele já tiver sido visitado, continuamos. Caso contrário, adicionamos +1 na variável que mostrará quantas componentes já temos. Em seguida, fazemos uma dfs a partir dele. Com isso, todo mundo que é conectado com ele por algum amigo irá pertencer ao mesmo grupo.

Depois, para cada entrevista, criamos um set para indicar as componentes do candidatos presentes. Para cada candidato, verificamos se a componente dele está presente no set. Se estiver, quer dizer que alguém do mesmo grupo dele já foi adicionado anteriormente e, por isso, a resposta tem que ser 'S'. Caso contrário, adicionamos o índice da nova componente em nosso set e continuamos. Ao final, se não tiver repetido componentes, a resposta será 'N'.  A complexidade fica $O(N + E*logK)$.

Clique aqui para conferir o código.

Hotel Nlogônia

Comentário escrito por Estela Baron

Conhecimento prévio necessário:

• Soma de Prefixos
• Two Pointers
• Multiset

Subtarefa 2: N <= 400 e W <= 3000

Vamos guardar a soma de prefixos dos preços dos hotéis. Depois, vamos testar todos os intervalos [L,R] para ver se a soma não ultrapassa o limite W. Para isso, vamos percorrer L até R e achar o maior valor para um intervalo de D dias consecutivos. Podemos fazer isso pegando o maior resultado de SomaPrefixo[i] - SomaPrefixo[i-D-1], desde que i - D não seja menor que L. Esse resultado representa a maior quantia de dinheiro que poderá ser economizada. Em seguida, basta verificar se SomaPrefixo[R] - SomaPrefixo[L-1] - maiorValorParaDDias é menor ou igual a W. Ao final, queremos saber qual é o tamanho do maior intervalo válido (R-L+1). A complexidade fica $O(N^3)$.

Subtarefa 3: N <= 3000, W <= 3000 e $p_i$ = 1 ou $p_i$ = W + 1

Para cada dia, vamos guardar a quantidade de dias anteriores consecutivos que têm preço igual a 1. Vamos também guardar a quantidade de dias posteriores consecutivos que têm preço 1. Após isso, para cada dia $i$ , vamos ver qual é a quantidade de preços 1 consecutivos antes a ele e a quantidade de dias com preço igual a 1 consecutivos depois do dia $i + D$. Com isso, a nossa resposta será o maior valor de $max(resposta, D + min(W, anterior[i] + posterior[D + i])$. A complexidade fica $O(N)$.

Subtarefa 4: N <= 3000 e W <= 3000

Vamos utilizar a técnica da programação dinâmica para achar a maior quantidade de dias. Os estados da nossa $dp[i][W_j][2]$ serão: dp[posiçao atual][dinheiro restante][0 - se não foi utilizado os D dias gratuitos ou 1 - se os D dias já foram utilizados]. Com isso, as transições serão as seguintes:

• dp[i][$W_j$][1] = max(dp[i-1][ $W_j$ -p[i]][1] + 1, dp[i-D][ $W_j$ ][0] + D)
• dp[i][$W_j$][0] = dp[i-1][$W_j$ - p[i]][0] + 1

Depois de calcular o valor, vamos ver se a maior quantidade de dias é maior que o máximo até aquele momento. Se for, atualizamos a resposta. A complexidade fica $O(N*W)$.

Subtarefa 5: $p_i$ >= $p_(i+1)$

Como os preços vão estar ordenados, vamos começar do final e ir somando os dias até o limite de W. Depois, adicionamos D. Com isso, temos a resposta. A complexidade fica $O(N)$.

Subtarefa 6: Sem restrições adicionais

Vamos manter a ideia de armazenar as somas de prefixos. Além disso, para acharmos a resposta vamos utilizar a técnica de Two Pointers. Basicamente, vamos definir o início do intervalo e ir aumentando o fim do nosso intervalo até que a soma a ser paga seja maior que W. Quando atingir a soma maior que W, avançamos em uma posição o início do nosso intervalo. Toda vez que avançarmos o final, vamos adicionar o preço a uma variável que indica a soma dos preços do intervalo e adicionamos a soma dos últimos D dias que acabam naquele mesmo final em um Multiset. Como queremos maximizar a quantidade de dias, vamos pegar o maior valor do Multiset e ver se a diferença entre a soma do dos preços do intervalo menos esse maior valor é maior que W. Se for não for, o intervalo [L,R] é válido e a quantidade de dias é R-L+1. Daí basta atualizar a resposta se necessário. Se a diferença for menor, vamos avançar o início do intervalo. Ao fazer isso, vamos tirar o preço daquela posição da soma de preços e remover do multiset a soma dos últimos D dias relacionados àquela posição. Atenção para retirar somente uma ocorrência do valor no multiset. Ao final, teremos salva a resposta e é só imprimir. A complexidade é $O(N*logN)$.

Clique aqui para conferir o código disponibilizado no site da OBI.

Brigadeiros

Comentário escrito por João Pedro Castro

Conhecimento prévio necessário:

• Introdução à Programação Dinâmica
• Problema da Mochila

Subtarefa 2: $N \leq 50$, $K \leq 3$, $T \leq 1000$

Vamos brutar tudo (testar todas as possibilidades de algo). Primeiro, vamos brutar as $K$ posições finais, isso é $O({N \choose K})$. Agora, para cada uma dessas possibilidades vamos brutar a ordem que cada um vai (se o primeiro menor das posições iniciais vai com a segunda menor das posições finais, etc), isso é $O(K!)$. Por fim, para cada um desses casos conseguimos calcular em $O(K)$ (mas até $O(N)$ passaria) o $t$ mínimo para chegar nessa posição, e se $t \leq T$ falamos que a resposta é o máximo entre a resposta atual e a soma da quantidade de brigadeiros nas posições finais. A complexidade final é $O({N \choose K} \cdot K! \cdot K)$.

Dica de implementação: para brutar todas as possibilidades, você pode criar um vetor de $N$ posições que comece com $N - K$ 0s e depois tenha $K$ 1s. E então, usar next_permutation para ver todas as possibilidades. Em uma dada permutação desse vetor original você pode dizer que se e somente se a i-ésima posição for igual a 1 tem alguém do grupo.

Subtarefa 3: $N \leq 16$, $T \leq 1000$

Podemos fazer a mesma estratégia da parcial anterior mas com uma observação a mais: sejam as posições iniciais do grupo $s_1 < s_2 < ... < s_k$, e as finais $f_1 < f_2 < ... < f_k$: para conseguir o tempo mínimo de chegar nessa posição é ideal dizer que o cara na posição $s_i$ vai para a posição $f_i$ para todo $1 \leq i \leq k$; ou seja, o menor vai com o menor, o segundo menor vai com o segundo menor, etc. A intuição disso é bem simples, e não é difícil "provar" (sem muita formalidade) fazendo umas contas.

Assim, conseguimos só brutar as $O({N \choose K})$ possibilidades de escolhas, e calcular o tempo para chegar lá em $O(K)$. A complexidade final é $O({N \choose K} \cdot K)$.

Dica: o caso onde ${a \choose b}$ é maior é quando $b = \frac{a}{2}$, então nesse caso o pior é ${16 \choose 8} \approx 10^{4.1}$, que ainda passa tranquilamente.

Subtarefa 4 e 5: $N \leq 50$, $T \leq 10^5$

Vamos usar programação dinâmica! Aqui a definição de cada parte:

• Estado: nosso estado vai ser $dp_{i, j, t} = s$, onde:
  • $i$ significa que usamos as posições de 1 até $i$ para as posições finais dos membros do grupo que colocamos até agora.
  • $j$ significa que já colocamos os $j$ primeiros membros do grupo.
  • $t$ significa o tempo máximo que podemos usar para chegar na melhor soma possível.
  • $s$ significa a melhor soma possível que conseguimos dado $i$, $j$ e $k$.
• Caso base: o único caso base necessário é $dp_{0, 0, 0} = 0$. O resto, se não calcularmos, pode ser visto só como $-\infty$.
• Transição: vou colocar várias possibilidades, e vai ser só o máximo entre elas.
  • Podemos só não botar nada em $i$: $dp_{i - 1, j, t}$.
  • Podemos ficar parados sem fazer nada: $dp_{i, j, t - 1}$.
  • Se $j > 0$, podemos botar o $j$-ésimo (do menor para o maior em posição) membro do grupo na posição $i$: $dp_{i - 1, j - 1, t - |i - posicao_j|} + p_i$ (perceba que essa transição só funciona por conta da nossa observação que é sempre melhor colocar o menor com menor, segundo menor com segundo menor, etc.)
• A resposta, dado o estado, é $dp_{N, K, T}$.

A complexidade é $O(N^2 \cdot T)$.

Subtarefa 6: $N \leq 100$

Vamos fazer a mesma DP, só que com uma observação a mais. Responda essa pergunta: se posso fazer trocas de elementos adjacentes, qual o número máximo de swaps para ordenar o vetor?

Se você já viu a técnica de bubble sort, essa pergunta tem uma resposta bem direta: é $O(N^2)$, e na verdade sempre vai ser menor que $N^2$ (não convém mostrar a conta aqui). Logo, posso chegar de qualquer ordenação do vetor para qualquer outra em menos de $N^2$ operações, ou seja, logo após receber o $T$ podemos dizer que $T = min(T, N^2)$ e a resposta ainda estaria certa, pois se existe uma resposta válida fazendo mais que $N^2$ trocas, também existirá uma fazendo menos que $N^2$ trocas.

Assim, tendo que $T \leq N^2$, temos uma complexidade de $O(N^4)$.

Subtarefa 7: Sem restrições adicionais.

Quando você leu o enunciado, idealmente se atentou de um detalhe específico que não seria colocado sem motivo: $0 \leq P_i \ leq 9$. Ou seja, todo prato tem entre $0$ e $9$ brigadeiros, mas o que isso faz a gente pensar? Se você já está acostumado com problemas de DP, é direto: a soma máxima é $O(N)$.

E uma técnica legal de problemas de DP, é que em diversos problemas se você tem algo como $dp_{a, b, c} = d$ (ou em um caso geral com quantas variáveis você quiser), você pode dizer que $dp_{a, b, d} = c$, ou qualquer outra troca. Ou seja, se você tem $X$ variáveis que indicam seu estado, e mais $1$ que indica sua resposta, você pode trocar qualquer uma das que indicam o estado com a da resposta que o estado ainda vai ser perfeitamente expressado. Claro que varia de problema a problema, e vai ter trocas melhores que outras, mas em problemas de DP sempre pense em qual a maneira com menos possibilidades de guardar esse estado.

No nosso caso, ao invés de fazer a $dp_{i, j, t} = s$, vamos fazer a $dp_{i, j, s} = t$. Já que o máximo de $t$ é $O(N^2)$ e o máximo de $s$ é $O(N)$. Agora a DP significa: colocando os $j$ primeiros do grupo em algumas das $i$ primeiras posições, qual o menor tempo $t$ para atingir a soma $s$? Se for impossível podemos só dizer que $dp_{i, j, s} = \infty$.

O estado foi explicado acima, o caso base é o mesmo, e o resto fica assim:

• Transição: de novo, colocarei várias coisas aqui, e agora só pegue o mínimo entre elas.
  • Não colocamos nada em $i$: $dp_{i - 1, j, s}$.
  • Colocamos o $j$-ésimo do grupo em $i$: $dp_{i - 1, j - 1, s - P_i} + |i - posicao_j|$.
• A resposta vai ser o maior $S$ tal que existam quaisuer $x$ e $y$ com $dp_{x, y, S} \leq T$.

Temos $O(9 \cdot N^3)$ estados, cada transição é $O(1)$, logo a complexidade final é $O(9 \cdot N^3) = O(N ^3)$.

OBS: A complexidade acaba ficando apertada, então para ficar tranquilo você tem que fazer pequenas "otimizações" (basicamente não passar por estados impossíveis), veja o código abaixo para ver as que fiz.

Clique aqui para conferir o código.