OBI 2023 – Fase 2 – Turno B – Programação Nível Júnior

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 os nossos materiais.

Para conferir a prova na integra, entre no site da OBI.

UPA

Comentário escrito por Estela Baron

Conhecimento prévio necessário:

• Soma de Prefixos

Observe o que o enunciado quer saber o maior espaço destinado aos ônibus, ou seja, queremos saber qual é a maior quantidade de veículos que coexistirão. Para isso, vamos dar uma olhada nas subtarefas.

Subtarefa 1:

Quando a tarefa define que $P_i = C_i + 1$, temos que o ônibus só ocupa a posição $C_i$, ou seja, só precisamos nos preocupar com um ponto. Portanto, basta criarmos um vetor que guarda os instantes e adicionarmos +1 para cada $C_i$. Ao final, queremos saber o maior valor, pois indica a coexistência da quantidade máxima de veículos daquele momento/ponto. Lembre de multiplicar por 20.

Subtarefa 2:

A partir da tarefa 2, passamos a lidar com intervalos, então a nossa ideia anterior não funciona. Porém, como o $N, C_i$ e $P_i$ são menores ou iguais a $1000$, podemos criar um vetor de instantes que guarda a quantidade de ônibus presentes no instante[i]. Com isso podemos adaptar a ideia da tarefa anterior: para todo instante compreendido de $C_i$ e $P_i -1$, adicionamos +1. Da mesma forma, temos que armazenar a maior resposta (podemos criar uma variável que guarda o maior valor e ir atualizando), e multiplicá-la por 20. A complexidade fica $O(N*P) = O(N^2)$. Como $N$ <= 1000, então passa no limite do tempo.

Subtarefa 3:

Observe que, na teoria, não passaria no tempo aplicar a ideia da sub2 nessa tarefa. No entanto, como nos é garantida que a resposta é no máximo 1000, podemos inferir que temos no máximo $1000/20 = 50$ ônibus coexistindo. Ou seja, se analisarmos o nosso vetor de instantes, teríamos que o valor máximo seria $50$. Portanto, só visitaríamos no máximo 50 vezes cada posição. Com isso, a nossa complexidade ficaria $O(P*50)$ = $O(10^6 * 50)$.

Subtarefa 4 – Solução 1:

No intuito de conseguir lidar com valores grandes de $N,C_i, P_i$ e de não depender de uma resposta máxima definida, podemos utilizar a técnica da soma de prefixos. Basicamente, é a mesma ideia da subtarefa 2, no entanto, em vez de ir adicionando um por um no intervalo, vamos adicionar +1 no $C_i$ e adicionar -1 $P_i$. Ao fazer a soma acumulada, cada posição será somada ao valor da anterior. Com isso, o +1 do $C_i$ irá se “propagar” até o final do intervalo. Contudo, como também tem o -1, também propagamos o -1 do $P_i$ até o final, observe que o +1 e o -1 irão resultar em 0, o que possibilita a soma do +1 do $C_i$ até o $P_i -1$ – no instante $P_i$, o ônibus já saiu.

Resumindo, para cada ônibus, iremos adicionar +1 em $C_i$ e -1 em $P_i$. Depois de ter processado todos os veículos, iremos fazer a soma acumulada: adicionar o valor do instante[i-1] ao instante[i]. Em cada instante, teremos a quantidade de ônibus estacionados naquele tempo. Por fim, basta guardar o maior valor encontrado e multiplicar por 20. A complexidade fica $O(max(N, P))$.

Subtarefa 4 – Solução 2:

Outra solução possível é, para cada ônibus, adicionar em um vetor um par com: o instante da entrada e o valor +1 – indicando que o ônibus novo entrou no estacionamento- e um outro par com : o instante da partida e o valor -1 – indicando que o ônibus saiu. Depois de ter colocado todos os valores dos $N$ veículos, vamos ordenar o vetor em ordem crescente do instante.

Com isso, vamos percorrer o vetor e vamos criar uma variável para guardar a quantidade de veículos. Toda vez que o instante indica a entrada de algum ônibus, vamos adicionar +1 na quantidade e ,toda vez que algum ônibus sai, vamos adicionar -1 na quantidade. Com isso, conseguimos ter a quantidade de veículos no estacionamento entre cada “evento novo” (chegada ou saída). De novo, vamos guardar o maior valor da quantidade e multiplicar por 20. Complexidade: $O(N*logN)$.

Clique aqui para conferir a solução 1 e a solução 2.

Empresa

Comentário escrito por João Pedro Castro

Conhecimento prévio necessário:

• Árvores

Podemos visualizar a hierarquia dessa empresa como um grafo, onde os vértices (funcionários) tem outros vértices se ligando à ele (os subordinados). Além da estrutura do grafo, para cada funcionário vamos guardar seu chefe, salário, e a quantidade de subordinados com os quais ele está insatisfeito. Também é necessário guardar a quantidade de funcionários insatisfeitos no total, chamaremos esse valor de $f$.

Após montar o grafo (feito com as arestas sendo: $\text{chefe} \rightarrow \text{subordinado}$), receber o chefe de cada um e o salário, para preencher a quantidade de insatisfações basta percorrer o grafo começando do vértice 1 e aumentando o valor de $insatisfacoes[vertice]$ em uma unidade toda vez que $f$ em 1 caso $insatisfacoes[vertice] = 0$, já que o estado do $vertice$ vai mudar de satisfeito para insatisfeito.

Para todo funcionário $i$ atualizado a ideia é checar se o “estado” (satisfeito ou insatisfeito) de seu chefe e dele mesmo (em relação ao seus subordinados) foram alterados, já que eles são os únicos com os quais isso pode ter acontecido. E isso pode ser feito com uma série de estruturas condicionais, que se resumem à:

• (chefe insatisfeito antes com o funcionário) e (chefe satisfeito agora)
• (chefe satisfeito antes com o funcionário) e (chefe insatisfeito agora)

Agora, para achar o valor de $f$ (a resposta) atualizado, é só seguir o seguinte algoritimo:

• Se $insatisfacoes[chefe[i]]++$
• Se $insatisfacoes[chefe[i]] = 1$ (novo chefe insatisfeito):
  • $f++$

Se não se: $insatisfacoes[chefe[i]]--$

Se $insatisfacoes[chefe[i]] = 0$ (chefe satisfeito de novo):

• $f--$

Para cada subordinado $u$ de $i$:

• Se $insatisfacoes[i]++$
• Se $insatisfacoes[i] = 1$ (novo chefe insatisfeito):
  • $f++$

Se não se: $insatisfacoes[i]--$

Se $insatisfacoes[i] = 0$ (chefe satisfeito de novo):

• $f--$

$salario[i] = novoSalario$

$imprimir~f$

Assim você também garante que os valores de $insatisfacoes$ e $f$ sempre permanecem atualizados. Segue a solução em C++:

Clique aqui para ver o código

Brincadeiras de Roda

Comentário escrito por Enzo Dantas

Conhecimento prévio necessário:

• Congruências

Imagine um círculo com 5 pessoas. Se o professor bate palma 5 vezes, percebemos que todas as pessoas dão uma volta completa e continuam no mesmo lugar, e percebemos que isso também vale para qualquer número múltiplo de 5. Sendo assim, em um círculo com $n$ pessoas, vamos nos importar apenas com a quantidade de palmas $P$ módulo $n$. É fácil ver que uma pessoa qualquer que começa na posição $x$ vai terminar aproximadamente na posição $(x+P) (mod$ $n)$. Trabalhando com casos pequenos chegamos na fórmula exata $(x+P-1) (mod P) + 1$, e essa é a solução em $O(1)$.

Além disso, os limites pequenos do problema permitem uma solução ainda mais direta: simular cada palma do professor. Se a posição atual é igual a $n$, então a posição depois da palma é 1. Caso contrário apenas adicionamos 1 à posição. Complexidade: O(P).

Clique aqui para conferir o código (Solução 1)

Clique aqui para conferir o código (Solução 2)