OBI 2023 - Fase 2 - Turno B - Programação Nível 2

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.

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)

Startup

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 $salario[subordinado] > salario[vertice]$, quando isso acontecer, também aumente $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 $i \neq 1 ~\&~ salario[i] \geq salario[chefe[i]] ~\&~ novoSalario > salario[chefe[i]]$
  • $insatisfacoes[chefe[i]]++$
  • Se $insatisfacoes[chefe[i]] = 1$ (novo chefe insatisfeito):
    • $f++$
• Se não se: $salario[i] > salario[chefe[i]] ~\&~ salario[chefe[i]] \geq novoSalario$
  • $insatisfacoes[chefe[i]]--$
  • Se $insatisfacoes[chefe[i]] = 0$ (chefe satisfeito de novo):
    • $f--$
• Para cada subordinado $u$ de $i$:
  • Se $salario[i] \geq salario[u] ~\&~ salario[u] > novoSalario$:
    • $insatisfacoes[i]++$
    • Se $insatisfacoes[i] = 1$ (novo chefe insatisfeito):
      • $f++$
  • Se não se: $salario[u] > salario[i] ~\&~ novoSalario \geq salario[u]$:
    • $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

Corridas

Escrito por Caique Paiva

Conhecimentos Prévios Necessários:

• Básico de Geometria

A principal ideia desse problema é que a solução vai ser um retângulo. Para perceber isso, basta ver que, se temos uma solução ótima, podemos ir "dobrando" a cerca para que ela vire um retângulo. Vamos ver um exemplo para ficar mais claro:

Na primeira figura, temos um caminho que é solução do problema, e então, a ideia é pegar essas pontas que não são um retângulo, e dobrar elas para se tornar um retângulo, e isso não muda o tamanho da cerca, logo podemos fazer isso. Então, fazemos isso até que a figura não tem mais nenhuma ponta.

Agora, dado que a figura é um retângulo, qual é o retângulo que é solução? É o retângulo que abrange a figura toda, ou seja, se olharmos os pontos como coordenadas da forma $(x, y)$, precisamos que o ponto com o menor $x$ do caminho esteja no retângulo, o com maior $x$ também esteja, o com menor $y$ também esteja, e o com maior $y$ também esteja, e veja que essa condição também é suficiente para construir o retângulo. Dito isso, seja $maxx, minx, maxy, miny$ o maior x, menor x, maior y e menor y, então, o perímetro desse retângulo $2*(maxx-minx+2+maxy-miny+2)$.

Com todas essas conclusões, como vamos fazer nossa resposta? Vamos simular o caminho feito no problema (Se estamos no ponto $(x, y)$ e temos que subir $k$ casas, fazemos $(x, y+k)$, e análogos) e vamos salvando qual é o maior x, o menor x, o maior y e o menor y, e no final, calcular a resposta com o que foi dito no paragrafo passado.

Clique aqui para ver o código

Fortunas

Comentário por Murilo Maeda e Henrique Vianna

Conhecimentos Prévios

• Somas em Prefixo
• Binary Lifting
• Busca em Grafos
• Segment Tree com Lazy Propagation ou BIT

Esse é um problema relativamente complicado e descobrir a ideia final requer várias observações. Por isso, vamos comentar todas as parciais do problema, já que elas ajudam a resolver para 100 pontos.

Subtarefa 1: $M = 1$

Já que $M = 1$, haverá uma única reunião. Então, podemos simplesmente fazer uma $DFS$ a partir da anfitriã e ir marcando quem estiver dentro do intervalo estipulado.

Subtarefa 2: $B_i = i - 1$ para todo $i > 1$ – ou seja, a mãe da matriarca $i$ é a matriarca $i-1$

O que essa subtarefa quer dizer é que a árvore vai ser uma linha, ou seja, se tomarmos a matriarca 1 como raíz, todos os vértices (fora a única folha) vão ter exatamente 1 filho. Com isso temos basicamente um vetor no qual os valores das fortunas vão decrescendo conforme o índice aumenta.

Para resolver esse problema, vamos manter um vetor auxiliar $Resp$ de tamanho $N + 1$ que guarde no índice $i$ para quantas reuniões a matriarca $i$ foi convocada. Também vamos representar a árvore como um vetor $V$ que guarde na posição $i$ a fortuna $A_i$ da matriarca $i$. Outra observação importante é que uma convocação $j$ agora se resume a encontrar a matriarca de menor índice $i$ cuja fortuna seja menor ou igual a $D_j$ e a matriarca de maior índice $k$ cuja fortuna seja maior do que $E_j$.

Então, como o vetor está ordenado (do maior para o menor), basta fazermos duas buscas binárias: uma para encontrar a matriarca de maior fortuna que foi convocada e outra para encontrara a matriarca de menor fortuna que foi convocada e depois adicionar 1 no vetor $Resp$ de todo mundo entre essas duas (incluindo elas).

Para adicionar 1 em todos os elementos do vetor $Resp$, vamos usar um truque de somas parciais. Para esse truque, se quisermos adicionar 1 nos elementos do intervalo $[i,j]$, basta irmos no vetor $Sparcial$, que guarda as somas parciais de prefixo do vetor $Resp$, e somarmos 1 no índice $i$ e -1 no índice $j+1$. dessa forma, somente os elementos no intervalo que queremos serão afetados quando calcularmos a soma daquele intervalo usando somas parciais.

Para a resposta, basta pegar a soma parcial de cada matriarca individualmente.

Subtarefa 3: $E_j = 1$  e $D_j = A_{o_j}$

Ao que essa tarefa se resume é que todo mundo na subárvore da anfitriã vai ser vai ser chamada. Ou seja, para cada das reuniões que forem feitas, basta somar 1 no vetor de resposta de todo mundo que está na subárvore da anfitriã. Para fazer isso, podemos linearizar a árvore e utilizar o mesmo truque de somas parciais que usamos na parcial anterior.

Para linearlizar a árvore, podemos utlizar a técnica "Euler Tour". Para melhor compreensão, analise o código a seguir:

Na implementação acima, temos: $timer$ guarda o "tempo" atual da $dfs$, $tin[i]$ guarda o tempo em que se "entra" no vértice $i$ , ou seja, o valor de $timer$ quando $dfs(i, pai(i))$ foi chamada e $tout[i]$, que representa o tempo em que se "sai" do vértice $i$, ou seja, o maior valor de $tin[j]$ para algum $j$ na subárvore de $i$. Sendo assim, a subárvore de qualquer vértice pode ser representada por um intervalo continuo $(tin[i], tout[i])$, daí o nome "linearização".

Subtarefa 4: $D_j =A_{o_j}$ e $A_i \leq 200$

Note que nessa tarefa ainda mantemos a característica da subtarefa anterior de que quando uma reunião acontece, somente a subárvore da anfitriã é convidada. Mas, agora, a característica que não está presente é a de que todos vão ser chamados. Como isso acontece, não podemos mais utilizar o truque de somar 1 em todos os elementos do intervalo, já que podem haver "buracos" nos segmentos.

O que a outra condição que o enunciado nos dá, o limitante de fortuna, garante é que a altura máxima da árvore vai ser 200, já que há uma diferença de pelo menos 1 da fortuna de uma matriarca mais velha para outra mais nova. Então, podemos simplesmente marcar cada uma das anfitriãs e qual é o intervalo da reunião que elas fizeram. Para calcular a resposta pegamos um vértice por vez e subimos até a raiz, calculando para cada um dos vértices no caminho em quantas festas que ele foi anfitrião o vértice do qual nós partimos participou. Mas, note que, uma única matriarca pode ser anfitriã de várias festas com vários intervalos diferentes, então temos que encontrar uma maneira de guardar e checar a quais intervalos uma determinada fortuna pertence quando estamos subindo pela árvore.

Para fazer isso podemos simplesmente guardar um vetor de marcação para cada um dos vértices que indica para cada fortuna quantas festas ela participou com aquele vértice de anfitrião. Isto é, se um vértice $i$ é anfitrião de uma festa de intervalo $E_j$ e $D_j$, basta somarmos 1 no intervalo $[E_j,D_j]$ do vetor de marcação do vértice $i$. Quando formos calcular a resposta para um vértice $k$ de fortuna $A_k$ e estivermos passando pelo vértice $i$, somamos o número guardado no vetor de marcação do vértice $i$ na resposta do vértice $k$.

Subtarefa 5: Sem restrições adicionais

Para resolver o problema completamente deve-se perceber que é válido simplesmente “transferir” uma reunião de um vértice para o seu último ancestral que tem fortuna dentro do intervalo, ou seja, o ancestral $j$ de $O_i$ de menor profundidade na árvore que satisfaz $fortuna[j] \leq D_i$. Para achar esse ancestral rapidamente, basta usarmos a técnica de binary lifting. Chamaremos esse vértice de $T_i$. Tendo isso feito, para cada reunião $i$, só precisamos considerar os descendentes de $T_i$, não mais os ancestrais.

Tendo isso feito, podemos finalizar o problema de diversas maneiras. O jeito mais prático é fazer uma $dfs$, mantendo alguma estrutura que permita somas e consultas (range sum, point query) em tempo logarítmico, como uma BIT ou uma Segment Tree. Pense nessas estruturas como um “vetor de frequência”, capaz de nos informar em quantas das reuniões que estão “ativas” (para um dado vértice $u$, por conta da $dfs$, só estarão “ativas” as reuniões que tem como $T_i$ um dos ancestrais de $u$ ou o próprio $u$) uma dada fortuna idade está contida. Quando “entrarmos” num vértice, somaremos, $1$ na nossa estrutura, no intervalo $[E_i, D_i]$ para toda reunião que tem como $T_i$ o nó atual. Para acharmos a resposta de um dado vertice $u$, basta fazermos uma consulta na estrutura,  obtendo a quantidade de reuniões em que está contida sua fortuna. Quando “sairmos” do nó, devemos desativar essas reuniões, subtraindo $1$.

Clique aqui para ver o código