OBI 2023 - Fase 3 - 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.

Pirâmide

Comentário escrito por Murilo Maeda Kataoka

Conhecimento prévio necessário:

• next_permutation

Para esse problema, podemos simplesmente testar todas as possíveis ordens dos 6 números (que são, no total, $6! = 720$) e estabelecer quais posições pertencerão a qual camada. Isto é, guardo os 6 números da entrada em um vetor e determino que as posições $0,1,2$ são a primeira camada, $3,4$ são a segunda e  $5$ é a terceira. Depois, testo todas as ordenações dos 6 números possíveis e checo se em alguma dessas ordenações a condição do enunciado é válida. Se sim, então é possível montar, caso contrário, não é possível montar.

Clique aqui para conferir o código

Transportes

Comentário escrito por Enzo Dantas

Conhecimento prévio necessário:

• Dijkstra com vértices auxiliares
• Análise de complexidade

Subtask 1 (11 pontos): K=1

Como todas as arestas são do mesmo tipo, só precisamos pagar para usar a primeira aresta. Se for possível ir de $A$ a $B$ (checamos isso com uma dfs), printe $P[1]$, caso contrário printe -1.

Subtask 4 (11 pontos): $K \le 100$

Para essa subtask, usaremos uma ideia clássica de Dijkstra com vértices auxiliares.

Defina $dist[u][c]$ = menor distância para chegar no vértice $u$ com a cor $c$.

Transição: estamos no vértice $u$ com a cor $c$ e vamos passar por todas suas arestas. Agora estamos olhando para uma aresta $(u,v,w)$ (ou seja, uma aresta entre $u$ e $v$ de cor $w$). Se a aresta atual é da cor que estamos agora, essa aresta tem custo 0. Caso contrário ele tem o custo definido no input. Ou seja, se $c=w$, então $dist[v][w] = dist[u][c]+0$. Caso contrário, $dist[v][w] = dist[u][c] + P[w]$.

Como o primeiro vértice do Dijkstra não terá cor definida, podemos dizer que ele tem uma cor 0, pois ela será diferente de todas as outras cores.

Complexidade: O grafo auxiliar criado tem $K*N$ vértices e $K+M$ arestas. Pela análise de complexidade normal do Dijkstra, a complexidade final é $O(KM + KNlog)$.

Subtask 5 (11 pontos): $N \le 10^5$, $K \le N$

Para resolver o problema completo otimizaremos a ideia da subtask anterior. Em vez de passar por todas as arestas quando estamos no vértice $(u,c)$, passaremos apenas pelos vértices de cor $c$ (criamos uma lista de adjacência para cada cor). Evidentemente, isso não considera a troca de de cores. Para resolver isso, criamos um vértice auxiliar de cor 0 para todos os vértices, o qual visita todas as arestas do vértice e é visitado com custo 0 quando estamos com alguma cor diferente de 0 no vértice em questão. Assim, passaremos por cada aresta apenas duas vezes (uma vez no vértice de sua cor e outra vez no vértice sem cor), e a complexidade do Dijkstra ficará O(M+Nlog).

Note que, se declarássemos um array global $dist[n][c]$ como fizemos na subtask passada, usaríamos $O(NK)$ de memória, o que passa dos limites de memória. Sendo assim, usaremos um map em vez de um array. Perceba que não passaremos por todos os $NK$ vértices: um vértice $(u,c)$ só pode ser acessado se existir uma aresta de $u$ de cor $c$. Logo, acessaremos apenas $\sum{grau_i}$ vértices no total. Pelo mesmo motivo, também usaremos um map para criar a lista de adjacência de cada cor.

Complexidade: para armazenar e acessar todas as listas de adjacência com map é $O(Mlog)$, o que não ultrapassa a complexidade do Dijkstra comum. Logo, a complexidade final é $O(M+Nlog)$.

Clique aqui para conferir o código

Oficina Mecânica

Comentário escrito por Caique Paiva

Conhecimentos prévio necessários:

• Algoritmos Gulosos
• Priority Queue

Para esse problema, uma pessoa pode pensar em vários algoritmos gulosos diferentes, porém a maior parte deles dá errado, então, é importante que você saiba provar que algoritmos funcionam e saber construir exemplos que quebram um algoritmo. Vamos provar uma observação antes de construir o algoritmo. Primeiramente, defina $\{ X_1, X_2, \cdots, X_n \}$ uma permutação de $\{ T_1, T_2, \cdots , T_n \}$ de modo que, quando trocarmos 2 carros $X_i, X_j$ no mecânico, temos que $i < j$, e além disso, a resposta do problema é minima.

Observação: Se $i < j$ e trocamos $X_i$ por $X_j$, então $X_i < X_j$.

Prova: Vamos olhar para um mecânico $M_t$. Seja $P_1, P_2, \cdots, P_l$ os carros que passaram por ele, nessa ordem. Veja que

• $P_1$ esperou 0 segundos para entrar
• $P_2$ esperou $P_1M_t$ segundos para entrar
• $P_3$ esperou $P_1M_t + P_2M_t$ segundos para entrar.
• ...
• $P_l$ esperou $P_1M_t + P_2M_t + \cdots + P_{l-1}M_t$ segundos para entrar

Então, a somas dos segundos esperados para esse mecânico é $((l-1)P_{1} + (l-2)P_2 + \cdots + P_{l-1})M_t$, com isso, se $P_i > P_j$ com $i < j$, então, podemos trocar eles dois de ordem, então conseguimos uma resposta menor, o que é um absurdo, pois essa é a resposta optimal, então $P_i < P_j$ sempre que $i < j$.

 

Com isso, podemos supor que $\{ X_1 < X_2 < \cdots < X_n \}$. Essa observação não é tão importante assim, a parte mais importante é que ela nos mostra a forma da resposta para cada mecânico, que é $((l-1)P_{1} + (l-2)P_2 + \cdots + P_{l-1})M_t$, com $P_1 < P_2 < \cdots < P_{l-1}$. Então, vamos tentar criar o algoritmo guloso colocando os carros no . Vamos olhar para o $X_n$, qual mecânico queremos colocar ele?

Bem, como $X_n$ é maior que todos os outros elementos do vetor, temos que sua contribuição na resposta final vai ser nula, então podemos colocar ele em qualquer mecânico. Sendo mais geral, os últimos $n-m$ carros não contribuirão na resposta, então, seja $X_i$ o primeiro carro em qual colocar ele vai afetar nossa resposta, então, podemos escolher colocar ele no $M_1$, assim aumentando nossa resposta em $X_iM_1$, ou então no $M_2$, assim aumentando em $X_iM_2$, e assim vai. Veja que, gulosamente o optimal é pegar o $j$ tal que $M_j$ é minimo, e assim aumentando nossa resposta em $M_jX_i$!

Agora, vamos olhar para o $X_{i-1}$. Dá mesma maneira do anterior, gulosamente, é melhor pegar o menor $M_k$, mas se pegarmos o mesmo em que colocamos o $X_i$, a nossa resposta vai aumentar em $2X_{i-1}M_j$ ao invés de só $X_{i-1}M_j$, portanto, só vale a pena pegar esse $M_j$ se $2M_j$ ainda for menor que todos os outros $M_k$. Vendo esses casos bases, é fácil de ver qual vai ser nosso algoritmo guloso.

Primeiro, vamos olhar para o nosso vetor em ordem decrescente. Seja $\{ V_1 > V_2 > \cdots > V_n \}$ o nosso vetor $X$ ordenado em ordem decrescente.

• Passo $i$: Para cada mecânico $M_j$, seja $C_j$ a quantidade de elementos que já colocamos nele. Então, vemos qual é o mínimo entre $M_jC_j$, seja ele $M_jC_k$. Adicionamos a nossa resposta $V_iM_kC_k$, e aumentamos $C_j$ em 1.

Para calcular esses mínimos, podemos manter esses valores numa priority_queue, e então, a complexidade do problema fica $O(MlogM + N)$.

Clique aqui para conferir o código

Bonecas

Comentário escrito por Estela Baron

Conhecimento prévio necessário:

• Programação dinâmica (DP)

Uma dica interessante para este problema é ordenarmos os nossos valores, pois a relação entre as alturas importam. Portanto a dica é: se a ordem dos itens não importar, tente ordenar de alguma forma para ver se alguma ideia surge.

Subtarefa 1 <= $T_i$ <= 2

Vamos ordenar os valores de T em ordem crescente. Após isso, o nosso vetor pode ficar:

• 111...111 ou 222...222

Observe que, nos dois casos, a resposta vai ser 0. Para os outros casos, vamos separar os valores em triplas. Quando os valores passam de 1 para 2, temos: ou ...112..., ou ...122... (para todos os outros casos, temos uma tripla só de 1 seguida de uma só de 2). Para ...112... a diferença continua sendo 0 (entre os dois menores). Para ...122.. temos dois casos: se tivermos outra tripla antes só de 1, podemos "trocar" o 1 da última posição com o 2 que está na segunda, ficando com (1,1,2) e (1,1,2). Assim, a diferença continua 0. O problema é se não tivermos uma tripla só de 1 antes. Por isso, devemos analisar se o N é maior que 3K. Se for, então podemos simplesmente "excluir" o 1 e ficar com 1,2,2,2...2,2,2, tornando a diferença 0. Caso contrário, a resposta vai ser 1.

Subtarefa N <= 30

Vamos fazer duas observações: se ordenarmos em ordem decrescente, podemos manter o número de bonecas com valores menores e isso irá auxiliar o cálculo da nossa resposta - vamos utilizar uma dp. Além disso, suponha que temos selecionamos quatro bonecas cujos valores serão usados na diferença, sendo x,y,z a diferença entre cada valor:

Como eles serão valores que serão contados em nossa resposta, veja que é sempre melhor agrupar as bonecas mais próximas uma das outras (T_a e T_b) e (T_c e T_d), pois ficamos com a soma dos balanceamentos igual a $x^2 + z^2$. Com as outras configurações, teríamos (T_a e T_c) e (T_b e T_d): $(x + y)^ 2 + (y + z)^2$ ou (T_a e T_d) e (T_b e T_c): $(x + y + z)^2 + y^2$.

Com isso, vamos utilizar uma dp para calcularmos as respostas com os seguintes parâmetros: dp[posição que estamos analisando para ser ou não a boneca com o menor valor do trio][quantidade de trios já formados][quantas bonecas não foram utilizadas] = menor valor de balanceamento possível ( dp[pos][i][j]). Observe que o parâmetro das bonecas não utilizadas servirá para guardar quantos valores maiores que T_pos estão disponíveis para ser a boneca de maior valor do trio - só podemos fazer isso porque os valores estão ordenados em ordem decrescente. Para calcular cada estado dp[pos][i][j], fazemos o mínimo entre:

• dp[pos-1][i][j-1] (caso não utilizarmos a boneca com aquele valor para ser a menor do trio)
• caso a boneca daquela posição for a menor do trio, vamos iterar por todas as bonecas das posições menores que pos para ser a segunda boneca maior- vamos definir a posição da outra boneca como l: dp[l-1][i-1][j - (pos - l - 1)] + (T_l - T_pos)$^2$

Iniciamos todos os estados da dp com um valor muito grande para indicar que não foi calculado - também para dizer que é impossível. Temos dp[0][0][0] = 0 como caso base. A complexidade dessa ideia é $O(N^3 * K)$.

Subtarefa N <= 1000 e K <= 100

Para esta tarefa, vamos utilizar a mesma ideia da anterior. No entanto, vamos remover um dos parâmetros: quantas bonecas não foram utilizadas. Observe que esta informação nos é útil para garantir que há bonecas maiores em um número suficiente para formar a quantidade de trios que queremos. Porém, podemos suprimir este parâmetro. Em vez de guardá-lo, vamos verificar se a quantidade de bonecas já vistas é maior ou igual a 3 vezes o número de trios (ou seja, se pos >= 3*i). Se não for, marcamos que o estado não é possível. Caso contrário, prosseguimos com o cálculo da dp vendo os estados anteriores. Vamos continuar escolhendo de forma quadrática qual a menor e a segunda menor boneca. A complexidade da ideia é $O(N^2 * K)$.

Solução Completa:

A observação essencial que devemos fazer é que, se escolhemos a boneca com T_x para ser a menor do trio, devemos também escolher a boneca com o menor valor maior ou igual a T_x, ou seja, T_x-1. Suponha que temos os valores em ordem decrescente T_a, T_b, T_c, T_d e T_e. Digamos que a resposta é (T_a e T_b) e (T_c e T_e) para k = 2. Veja que podemos melhorar a resposta pois T_d está mais próximo de T_c do que T_e está de T_c (também poderíamos falar que T_d está mais perto de T_e). Logo, se for para fixar uma boneca como a menor do trio, temos que selecionar a boneca imediatamente maior para ser a segunda para minimizar o valor. Com isso transformamos a nossa dp em: dp[posição][quantidade de trios já formados] = menor valor (dp[pos][i]). Para calcular os estados:

• verificamos se posição >= 3*quantidade de trios formados. Caso a condição não seja cumprida, dp[pos][i] = inf (valor muito grande)
• fazemos o mínimo entre dp[pos-1][i] e dp[pos-1][i-2] + (T[pos -1] - T[pos])$^2$

O caso base é dp[1][0] = 0 e a resposta vai estar armazenada em dp[N][k]. A complexidade fica $O(N*K)$.

Clique aqui para conferir o código

Fastfood

Comentário escrito por Arthur Lobo

Conhecimento prévio necessário:

• Busca Binária
• Grafos Bipartidos

O problema pede para que minimizemos o máximo. Essa expressão "minimizar o máximo" é comumente associada à busca binária na resposta. A base para todo o problema aqui vai ser que fazer fazer uma busca binária vendo se é possível formar os grupo de modo que a a distância máxima seja no máximo $D$. Mas como fazer essa busca?

Obs: $dist(i,j)$ vai ser a distaância entre os pontos $i$ e $j$, ou seja, $dist(i,j) = |X_i-X_j| + |Y_i-Y_j|$.

Subtask 2 ($N \leq 2000$)

Depois de fixar um $D$ na busca binária, vamos transformar o problema em um grafo. Vamos ligar uma aresta entre todos os pares de vértices que não podem estar no mesmo grupo, ou seja, criamos uma aresta entre $i$ e $j$ se $dist(i,j) > D$.

Agora temos um grafo em que queremos pintar cada vértice de azul ou vermelho e uma aresta significa que os vértices não podem ter a mesma cor. Isso é exatamente a descrição de um Grafo Bipartido.

Podemos checar se um grafo é bipartido tentando colorir ele usando uma dfs. Quando estamos um vértice azul, colorimos todos os seus vizinhos de vermelho e vice-versa. Se um vértice já está colorido de uma cor e tentamos colorir ele com outra, então é impossível bicolorir o grafo.

Essa solução funciona em $O(N^2)$ por checada da busca binária, então $O(N^2logD)$.

Subtask 3 ($N \leq 10^5$)

Primeiro, digamos que temos uma função $MaxDist(A,B)$ em que, dado dois conjuntos de pontos $A$ e $B$, retorna o par $(i,j)$, com $i \in A$ (está contido) e $j \in B$, com maior distância de manhattan, e também retorna essa distância $dmax$ ($MaxDist(A,B) = (dmax,i,j)$. Suponha também que essa função funciona em $O(logN)$ ou $O(1)$. No final eu explico como fazer isso, por enquanto só imagine que podemos fazer isso.

Vamos dividir os pontos em $3$ conjuntos:

• Conjunto $A$ dos pontos azuis. Começa apenas com o ponto $1$ (pois, sem perda de generalidade, podemos falar que o ponto $1$ é azul).
• Conjunto $V$ dos pontos vermelhos. Começa vazio.
• Conjunto $B$ dos pontos brancos (ainda não coloridos). Começa com todos os pontos menos o ponto $1$.

Agora vamos, aos poucos, colocar os pontos de $B$ em $A$ e $V$. Se tiver algum ponto $i$ em $B$ que está mais longe do que $D$ de $1$, então obrigatoriamente esse ponto é vermelho, certo? Porque se ele fosse pintado de azul, então teriam dois pontos no mesmo conjunto com uma distância maior do que $D$.

A ideia é repetidamente colocar pontos brancos que "não podem" estar no grupo azul no grupo vermelho e vice-versa. Vamos repetidamente fazer esses dois passos.

• Não pode estar no conjunto azul -> vai pro vermelho: Seja $MaxDist(B,A) = (dmax,i,j)$, se $dmax > D$, então o ponto $j$ deve ser pintado de vermelho. Tiramos ele do conjunto $B$ e colocamos no $V$.
• Não pode estar no conjunto vermelho -> vai pro azul: Seja $MaxDist(B,V) = (dmax,i,j)$, se $dmax > D$, então o ponto $j$ deve ser pintado de azul. Tiramos ele do conjunto $B$ e colocamos no $A$.

Mas e se em algum momento nenhuma das duas condições acontecerem, ou seja, se não tiver nenhuma obrigatoriedade a ser feita? Podemos pegar qualquer ponto em $B$ e mandar ele tanto para $A$ quanto para $V$, tanto faz (a prova do porque pode fica como um exercício para o leitor, não é difícil).

No final basta checar se $MaxDist(A,A)$ ou $MaxDist(V,V)$ é maior que $D$ (sim, a função funciona entre dois conjuntos iguais). Se algum for, então é impossível colorir os pontos com a distância $D$ e temos que pegar uma distância maior do que $D$ na busca binária.

Função mágica de maior distância.

Digamos que temos dois pontos, $(X_1,Y_1),(X_2,Y_2)$ e queremos saber a distância de manhattan deles, mas vamos tentar encontrar outro jeito de representá-la sem usar os módulos.

Primeiro, vamos lembrar que $|a-b| = max(a-b,b-a)$, mas podemos expandir isso ainda mais, transformando a soma de dois módulos em apenas um máximo: $|a-b|+|c-d| = max(a-b,b-a) + max(c-d,d-c) = max(a-b+c-d, a-b-c+d, -a+b+c-d, -a+b-c+d)$.

Dessa maneira, podemos representar $dis(1,2)$ como máximo entre esses 4 valores:

1. $(X_1+Y_1) - (X_2+Y_2)$
2. $(X_1-Y_1) - (X_2-Y_2)$
3. $(X_2+Y_2) - (X_1+Y_1)$
4. $(X_2-Y_2) - (X_1-Y_1)$

Vamos fazer isso com dois conjunto $A$ e $B$ agora. Já que só precisamos pegar o maior entre esses 4 valores, é isso que vamos fazer, vamos ver cada um dos casos. Com $i \in A$ (está contido) e $j \in B$:

1. $(X_i+Y_i) - (X_j+Y_j) \rightarrow i$ vai ser o ponto em $A$ com maior $(X+Y)$ enquanto $j$ vai ser o ponto em $B$ com menor $(X+Y)$.
2. $(X_i-Y_i) - (X_j-Y_j) \rightarrow i$ vai ser o ponto em $A$ com maior $(X-Y)$ enquanto $j$ vai ser o ponto em $B$ com menor $(X-Y)$.
3. $(X_j+Y_j) - (X_i+Y_i) \rightarrow i$ vai ser o ponto em $A$ com menor $(X+Y)$ enquanto $j$ vai ser o ponto em $B$ com maior $(X+Y)$.
4. $(X_j-Y_j) - (X_i-Y_i) \rightarrow i$ vai ser o ponto em $A$ com menor $(X-Y)$ enquanto $j$ vai ser o ponto em $B$ com maior $(X-Y)$.

Para manter os maiores e menores valores de $X+Y$ e $X-Y$ enquanto colocamos/tiramos pontos dos conjunto, podemos usar dois sets do C++, um para $X+Y$ e outro para $X-Y$. Dessa maneira, para cada iteração da busca binária nosso algoritmo de checar funciona em $O(NlogN)$, deixando uma complexidade de $O(NlogNlogD)$ para a nossa solução. Dependendo da implementação e da constante, essa solução pode ou não passar no tempo limite.

Já que apenas adicionamos pontos em $A$ e $V$ e apenas removemos pontos de $B$, é possivel evitar o uso dos sets deixar a solução $O(NlogD)$. Isso será deixado como um exercício para o leitor. O código do site apresenta essa solução em $O(NlogD)$.

Clique aqui para conferir o código